need java code that uses text files so like it needs to be able to just take files a 5152822
need java code that uses text files.— so like it needs to be able to just take files and use them. unable to load files here so as long as it can grab text files itll work
Traveling Salesperson Problem with Depth First Search
We will explore depth-first search algorithm for solving the very famous traveling salesperson problem.
Consider a graph of cities. The cost on an edge represents the cost to travel between two cities. The goal of the salesperson is to visit each city once and only once, and returning to the city he/she originally started at. Such a path is called a “tour” of the cities.
How many tours are there? If there are N cities, then there can be N! possible tours. If we tell you which city to start at, there are (N-1)! Possible tours. For example, if there are 4 cities (A, B, C, D), and we always start at city A, then there are 3! possible tours:
(A, B, C, D) (A, B, D, C) (A, C, B, D) (A, C, D, B) (A, D, B, C) (A, D, C, B)
It is understood that one travels back to A at the end of the tour.
The traveling salesperson problem consists of finding the tour with the lowest cost. The cost includes the trip back to the starting city. Clearly this is a horrendously difficult problem, since there are potentially (N-1)! possible solutions that need to be examined. We will consider DFS algorithms for finding the solution.
The DFS algorithm is exhaustive – it will attempt to examine all (N-1)! possible solutions. This can be accomplished via a recursive algorithm (call it recTSP). This function is passed a “partial tour” (a sequence of M cities (M recTSP will have to call itself recursively M-N times, adding each of the M-N cities to the current partial tour out of the remaining cities. If M=N we have a complete tour.
For example, we start with recTSP ({A}). This will have to call recTSP ({A, B}), recTSP ({A, C}, and recTSP ({A, D}). Generate a recursion tree to see how this work . This tree is not something you build explicitly – it arises from your function calls. You traverse this tree in a “depth-first” manner.
Each leaf node in recursion tree is a complete tour, which you will compute the cost of. Note that each non-leaf node is an incomplete tour, which you can also compute the cost of. If the cost of an incomplete tour is greater than the best complete tour that you have found thus far, you clearly do not have to continue working on that incomplete tour. Thus you can “prune” your search.
Just how hard are these problems? For example, if there are 29 cities, how many possible tours are there? If you can check 1,000,000 tours per second, how many years would it take to check all possible tours? Has the universe been around that long?
Since this program may take too long to complete, be sure to output the tour and its cost when it finds a new best tour.
We have to first develop the distance matrix, also called adjacency matrix. This adjacency matrix is populated using a given data file. You will run your program to find the best tours for 12
, 13, 14, 15, 16, 19 and 29 cities. Download all the data files in Files/Module4/Lab4.
Here is a sample code to populate the distance matrix
public void populateMatrix(int[][] adjacency){ //CITI is the number of cities and it is a constant
int value, i, j;
for (i = 0; i
for (j = i; j
if (i == j) {
adjacency[i][j] = 0;
}
else {
value = input.nextInt();
adjacency[i][j] = value;
adjacency[j][i] = value;
}
}
}
}
Here is an algorithm to compute tour cost
Algorithm computeCost (ArrayList tour)
Set totalcost = 0
For (all cities in this tour)
totalcost += adjacency [tour.get(i)][ tour.get(i+1)]
EndFor
If (tour is a complete tour)
totalcost += adjacency [tour.get(tour.size()-1)][0]
EndIf
return totalcost
End computeCost
Here is the DFS algorithm
Use ArrayList for “partialTour” and “remainingCities” – This implementation is inefficient due to higher space complexity.
/* requies : partialTour = , remainingCities = <1,2, 3, ….N-2, N-1>
ensures: partialTour = where n E {1,2,3, …, N-1} &&
cost(partialTour) is the absolute minimum cost possible.
*/
Algorithm recDFS (ArrayList partialTour, ArrayList remainingCities )
If (remainingCities is empty)
Compute tour cost for partialTour
If (tour cost is less than best known cost)
Set best known cost with tour cost
Output this tour and its cost
EndIf
Else
For (all cities in remainingCities)
Create a newpartialTour with partialTour
Add the i_th city of remainingCities to newpartialTour
Compute the cost of newpartialTour
If (newpartialTour cost is less than the best known cost) // pruning
Create newRemainingCities with remainingCities
Remove the i_th city from newRemainingCities
Call recDFS with newpartialTour and newRemainingCities
EndIf
EndFor
EndIf
End recDFS
The minimal cost path for 12 cities is 821, and the minimal cost path for 29 cities is 1610, but 29! = 8841761993739700772720181510144 (!!!!!)
Turn in your source program(.java file) and outputs(PDF) as an attachment of this assignment.
tsp12.txt—
97 205 139 86 60 220 65 111 92 122 154
129 103 71 105 258 154 112 79 145 59
219 125 175 386 269 134 129 167 151
208 39 102 227 60 78 90 89
51 296 150 42 99 231 166
279 114 56 210 165 216
78 328 121 345 78
169 189 76 188
87 45 123
23 361
111
tsp13.txt—
97 205 139 86 60 220 65 111 92 122 154 125
129 103 71 105 258 154 112 79 145 59 156
219 125 175 386 269 134 129 167 151 89
208 39 102 227 60 78 90 89 241
51 296 150 42 99 231 166 79
279 114 56 210 165 216 197
78 328 121 345 78 257
169 189 76 188 179
87 45 123 213
23 361 302
111 316
124
tsp14.txt–
97 205 139 86 60 220 65 111 92 122 154 125 234
129 103 71 105 258 154 112 79 145 59 156 34
219 125 175 386 269 134 129 167 151 89 233
208 39 102 227 60 78 90 89 241 176
51 296 150 42 99 231 166 79 215
279 114 56 210 165 216 197 216
78 328 121 345 78 257 342
169 189 76 188 179 265
87 45 123 213 123
23 361 302 231
111 316 123
124 121
176
We were unable to transcribe this imageWe were unable to transcribe this imageWe were unable to transcribe this imageWe were unable to transcribe this imageWe were unable to transcribe this imageWe were unable to transcribe this imageWe were unable to transcribe this image