This is a java program to solve TSP using MST.
Here is the source code of the Java Program to Solve TSP Using Minimum Spanning Trees. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
package com.maixuanviet.hardgraph; import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.util.StringTokenizer; public class TSPUsingMST { // Arrays to keep track of info. related to each city private String[] cityName; private String[] cityState; private int[] cityLat; private int[] cityLong; private int[] cityPop; // 2-D array to keep track of pairwise distances between cities private int[][] distances; // number of cities private static int numCities; public TSPUsingMST(int n) { numCities = n; // Allotting the space for each 1-D array cityName = new String[numCities]; cityState = new String[numCities]; cityLat = new int[numCities]; cityLong = new int[numCities]; cityPop = new int[numCities]; // Allocate space for each 2-D array. These arrays have 0 elements in // row 0, // 1 element in row 1, 2 elements in row 2, etc. distances = new int[numCities][]; for (int i = 0; i < numCities; i++) distances[i] = new int[i]; try { // Construct a buffered reader object and connect it to the files // "miles.dat" BufferedReader in = new BufferedReader(new FileReader("miles.dat")); // A counter that keeps track of the index of the current city being // read int cityNumber = 0; // While-loop for reading in data from "miles.dat." At the beginning // of the while-loop // the expectation is that we'll be reading a line containing the // city name. Instead, // if we encounter a line that starts with "*" then we skip to the // next line while (cityNumber < numCities) { // Read in a line String line = in.readLine(); // Skip the rest of the loop if line starts with a "*" if (line.charAt(0) == '*') continue; // Otherwise tokenize the line StringTokenizer tokenizedLine = new StringTokenizer(line, ",[]"); // Putting actual data into correct position in the array cityName[cityNumber] = tokenizedLine.nextToken(); cityState[cityNumber] = (tokenizedLine.nextToken()).trim(); // trim() // gets // rid // of // leading/trailing // blanks cityLat[cityNumber] = Integer.parseInt(tokenizedLine .nextToken()); cityLong[cityNumber] = Integer.parseInt(tokenizedLine .nextToken()); cityPop[cityNumber] = Integer.parseInt(tokenizedLine .nextToken()); // while loop to put distances in the array; this may need to // read several lines int mileNumber = 0; while (mileNumber < cityNumber) { // Read a mileage line and tokenize it String mileage = in.readLine(); StringTokenizer tokenizedMileage = new StringTokenizer( mileage, " "); // Read all the mileage data in this line into row // cityNumber; increment // mileNumber after each read while (tokenizedMileage.hasMoreTokens()) { distances[cityNumber][cityNumber - mileNumber - 1] = Integer .parseInt(tokenizedMileage.nextToken()); mileNumber++; } } // end of while reading distances cityNumber++; } // end of while reading cities in.close(); } // end of try catch (IOException e) { System.out.println("File not found."); } } // end of TSPTester() constructor // A simple getIndex method to help test the constructor int getIndex(String city, String state) { int location; for (location = 0; location < numCities; location++) if ((cityName[location].equals(city)) && (cityState[location].equals(state))) return location; return -1; } // Print information about a city, given a city index void printCityInfo(int index) { System.out .println(cityName[index] + " " + cityState[index] + " " + cityLat[index] + " " + cityLong[index] + " " + cityPop[index]); } // Print distance information between a given pair of cities void printDistanceInfo(int i, int j) { if (i < j) System.out.println(distances[j][i]); else System.out.println(distances[i][j]); } int getDistance(int i, int j) { if (i < j) return distances[j][i]; else if (j < i) return distances[i][j]; else return 0; } int[] greedyTSP() { // Find a cheapest triangle // Load triangle 0-1-2 into the the first 3 slots of the greedy array int[] greedy = new int[numCities]; int currentDistance; greedy[0] = 0; greedy[1] = 1; greedy[2] = 2; int currentBestDistance = getDistance(0, 1) + getDistance(1, 2) + getDistance(2, 0); for (int i = 0; i < numCities; i++) for (int j = 0; j < i; j++) for (int k = 0; k < j; k++) if ((currentDistance = getDistance(i, j) + getDistance(j, k) + getDistance(i, k)) < currentBestDistance) { greedy[0] = i; greedy[1] = j; greedy[2] = k; currentBestDistance = currentDistance; } // Try greedily to add a city that yields the smallest increase // in the cost of the tour int partialTourSize = 3; boolean[] visited = new boolean[numCities]; for (int i = 0; i < numCities; i++) visited[i] = false; visited[greedy[0]] = true; visited[greedy[1]] = true; visited[greedy[2]] = true; // Main loop: keep repeating until partial tour covers all cities while (partialTourSize < numCities) { int smallestIncrease = Integer.MAX_VALUE; int increase = 0; int bestInsertionPoint = 0; int bestCity = 0; // Scan through all cities, stopping at unvisited cities for (int i = 0; i < numCities; i++) { if (!visited[i]) { // Consider all possible positions of inserting city i into // the tour // and record the smallest increase for (int j = 0; j < partialTourSize; j++) { increase = getDistance(greedy[j], i) + getDistance(i, greedy[(j + 1) % numCities]) - getDistance(greedy[j], greedy[(j + 1) % numCities]); if (increase < smallestIncrease) { smallestIncrease = increase; bestCity = i; bestInsertionPoint = j; } // end of if we have found a smaller increase } // end of for-j } // end of if not visited } // end of for-i // Now we are ready to insert the bestCity at the bestInsertionPoint for (int j = partialTourSize - 1; j > bestInsertionPoint; j--) greedy[j + 1] = greedy[j]; greedy[bestInsertionPoint + 1] = bestCity; visited[bestCity] = true; partialTourSize++; } // end-while return greedy; } void copy(int[] source, int[] dest) { for (int i = 0; i < dest.length; i++) dest[i] = source[i]; } void TSP(int[] R, int partialTourSize, boolean[] visited, int[] T) { // Base case: we have discovered a tour better than T if ((partialTourSize == numCities) && (cost(R) < cost(T))) { System.out.println("Base case. Tour cost is " + cost(R)); copy(R, T); return; } // Another base case: our partial tour is not worth completing if (cost(R, partialTourSize) >= cost(T)) return; // Recursive case: R is not complete and is currently better than T // and is therefore worth completing for (int i = 0; i < numCities; i++) { if (!visited[i]) { // System.out.println("Appending " + i); visited[i] = true; R[partialTourSize++] = i; TSP(R, partialTourSize, visited, T); partialTourSize--; visited[i] = false; // System.out.println("Deleting " + i); } } // end of for-loop } // end of TSP double cost(int[] tour) { return cost(tour, tour.length); } double cost(int[] tour, int tourSize) { double c = 0; for (int i = 0; i < tourSize - 1; i++) c = c + getDistance(tour[i], tour[i + 1]); c = c + getDistance(tour[tourSize - 1], tour[0]); return c; } // Main method public static void main(String[] args) { int n = 15; TSPUsingMST T = new TSPUsingMST(n); // Initialize the list of vertices in the tree // Initially, no one except vertex 0 is in the tree boolean[] visited = new boolean[n]; for (int i = 0; i < n; i++) visited[i] = false; visited[0] = true; // Initialize the int[] that maintains the tree to default values // No vertices have parents set, except vertex 0 whose parent is itself int[] tree = new int[n]; for (int i = 0; i < n; i++) tree[i] = -1; tree[0] = 0; for (int i = 1; i <= n - 1; i++) { long minWeight = Long.MAX_VALUE; int bestVertex = -1; int bestParent = -1; for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { if ((visited[j]) && (!visited[k])) { if (T.getDistance(j, k) < minWeight) { minWeight = T.getDistance(j, k); bestVertex = k; bestParent = j; } // end if better distance is found } // end if an edge between a visited and an unvisited is // found } // end for-k } // end for-j // Update visited and tree visited[bestVertex] = true; tree[bestVertex] = bestParent; } // end for-i // Printing the MST for (int i = 1; i < n; i++) System.out.println(T.cityName[i] + " " + T.cityState[i] + ", " + T.cityName[tree[i]] + " " + T.cityState[tree[i]]); // Compting the MST cost long cost = 0; for (int i = 0; i < n; i++) cost += T.getDistance(i, tree[i]); System.out.println("The cost of the minimum spanning tree is " + cost); } // end main method } // end class
Output:
$ javac TSPUsingMST.java $ java TSPUsingMST Yankton SD, Wisconsin Dells WI Yakima WA, Williston ND Worcester MA, Wilmington DE Wisconsin Dells WI, Youngstown OH Winston-Salem NC, Winchester VA Winnipeg MB, Yankton SD Winchester VA, Wilmington DE Wilmington NC, Winston-Salem NC Wilmington DE, Williamsport PA Williston ND, Winnipeg MB Williamsport PA, Youngstown OH Williamson WV, Winston-Salem NC Wichita Falls TX, Wichita KS Wichita KS, Yankton SD The cost of the minimum spanning tree is 5461
Related posts:
Đồng bộ hóa các luồng trong Java
Java Program to Find Minimum Element in an Array using Linear Search
Java Program to Implement Vector API
Posting with HttpClient
Java Program to Implement Interval Tree
Java Program to Emulate N Dice Roller
New in Spring Security OAuth2 – Verify Claims
Java Program to Generate All Possible Combinations of a Given List of Numbers
Biến trong java
Hashtable trong java
Java Program to Implement Segment Tree
Java Program to Implement HashTable API
Anonymous Classes in Java
Extract network card address
Java Program to Implement PrinterStateReasons API
Documenting a Spring REST API Using OpenAPI 3.0
Java program to Implement Tree Set
Setting Up Swagger 2 with a Spring REST API
Java Program to Perform Finite State Automaton based Search
Lập trình hướng đối tượng (OOPs) trong java
Java Program to Implement AVL Tree
Summing Numbers with Java Streams
Java Program to Describe the Representation of Graph using Incidence Matrix
Custom Cascading in Spring Data MongoDB
Java Program to Represent Graph Using Adjacency Matrix
Comparing getPath(), getAbsolutePath(), and getCanonicalPath() in Java
Java Program to Implement Sorted Vector
Quick Guide on Loading Initial Data with Spring Boot
Giới thiệu Java Service Provider Interface (SPI) – Tạo các ứng dụng Java dễ mở rộng
Java Program to Implement Min Heap
Jackson – Marshall String to JsonNode
Hướng dẫn sử dụng Lớp FilePermission trong java