# 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

**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.**

*recTSP* For example, we start with ** recTSP** ({A}). This will have to call

**({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.**

*recTSP*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