## Programming Assignment 1

## The Traveling Salesperson Problem (TSP)

A set of

ncities along with the costsd(i,j) of traveling between citiesiandjare given. Assume that the cost function is symmetric, that is,d(i,j) =d(j,i) for alliandj. Assume also thatd(i,i) = 0 for alli. The task is to find a closed route (cycle) through the cities such that each city is visited once and only once, and the total cost of travel in the route is minimized. Since the salesperson is making a closed tour, there is no harm in assuming that the tour starts (and ends) at City 0.The TSP is a difficult computational problem. In your second algorithms course, you would learn that no polynomial-time algorithms exist for solving TSP (unless P = NP, an unresolved question which is popularly believed to be false). In this exercise, you are supposed to implement several algorithms to solve the TSP. These algorithms are of two types. First, you implement two algorithms that compute the exact minimum cost (along with a shortest route). These algorithms are slow, and cannot handle a large number of cities. Algorithms of the second type are fast but are not guaranteed to supply the minimum possible solution. They instead supply only close-to-best (suboptimal) solutions.

Before implementing the algorithms for TSP, you need to prepare data for

ncities. Readnfrom the user, and generate each city as a point (x,y) in the plane. You may take a random value between 0 and 999 (both inclusive) as each of the coordinates. After the cities are generated, store in a two-dimensional (nxn) table the distancesd(i,j) between pairs of cities. You may store these distances as integers (truncated or rounded values of Euclidean distances). For a reason that will be clear soon, it would be worthwhile to sort the cities initially with respect to theirx-coordinates, before the distances are computed and stored in the 2-d matrix.## The Exact Solution

Generate (recursively, perhaps) all the (

n- 1)! cyclic permutations of thencities. Each such permutation would be of the form 0,i_{1},i_{2},...,i_{n-1}, wherei_{1},i_{2},...,i_{n-1}is a permutation of 1,2,...,n- 1. For each cyclic permutation, compute the cost of the round trip 0,i_{2},i_{2},...,i_{n-1},0, and determine the minimum over all these permutations. This gives you the exact minimum cost, but takes O(n!) running time. The implication is that this algorithm can handle only small vales ofn(liken<= 15) in a reasonable amount of time.## A Divide-and-conquer Algorithm

Suppose that the cities are sorted with respect to their

x-coordinates. We recursively compute a shortest tour through the leftn/2 cities, and also a shortest tour through the rightn/2 cities. In the merging step, we identify the edgertin the left tour and the edgeuvin the right tour such that replacing these edges byrvandutgives the cheapest tour among all choices ofrandu. The situation is depicted in the following figure.This divide-and-conquer algorithm runs in O(

n^{2}) time and can handle large values ofn. However, this does not look at all possible tours throughncities, and so the solution computed by this algorithm is usually not optimal.## A Greedy Algorithm

A possible greedy approach to construct a suboptimal TSP tour is to iteratively add one city at a time to the tour. The initial tour starts and ends at a specified start city (say, City 0) without visiting any other city. When the partially constructed tour coverskcities, we identify an edgeuvin the tour and a yet unvisited citywsuch that replacinguvby the two-leg traveluwvleads to the minimum possible increase in the cost. Here, the minimum is taken over all choices ofuandw.After

n- 1 iterations, all cities are included in the tour. The greedy algorithm runs in O(n^{3}) time.## The Bellman-Held-Karp Dynamic-programming Algorithm

A dynamic-programming algorithm proposed independently by Bellman and by Held and Karp is now explained. This algorithm outputs a shortest tour in less than O(n!) time.Let

Cdenote the set of cities, and letsbe any specific start city. A natural choice isC= {0,1,2,...,n- 1}, ands= 0. Lettbe a city other thans, and letXbe any subset ofCnot containingsandt. ByB(s,X,t), we denote the cost of a shorteststpath that goes through each city inXonce and only once. The best costsB(s,X,t) can be inductively defined as follows. IfXis the empty set, thenB(s,X,t) is the distanced(s,t). Otherwise,B(s,X,t) is the minimum ofB(s,X- {x},x) +d(x,t), taken over all choices of the cityxin the subsetXofC.For each

tnot equal tos, the best costb_{t}=B(s,C- {s,t},t) is computed by dynamic programming. Finally, the minimum ofb_{t}+d(t,s) (over all choices oftdifferent froms) is the cost of the shortest TSP tour.Subsets of

Ccan be represented byn-bit integers. Thei-th city is present in a subset if and only if thei-th bit is 1. Sincesis always the first argument inB, it suffices to maintainBas a two-dimensional array indexed by a subset number and a target cityt. Setting to zero a one-bit in an integer standing for a subset indicates removal of a city from the subset. This new integer is certainly smaller than the original integer.So far, we have computed the cost of the best TSP tour through the

ncities. The corresponding tour can be computed with only a little amount of extra effort. In addition to the two-dimensional arrayB(s,X,t), we maintain another two-dimensional arrayL(s,X,t) indexed by the subsetXand the target cityt.L(s,X,t) stands for the city visited just before reachingtfollowing the shortestsXtpath. IfXis the empty set,L(s,X,t) iss. Otherwise, we computeB(s,X,t) as the minimum ofB(s,X- {x},x) +d(x,t) over all possible choices ofxinX. That particular choice ofxwhich yields the minimum value is stored asL(s,X,t). The tablesBandLare updated simultaneously. At the final stage, we find the besttfor whichb_{t}+d(t,s) is minimized. Thisthappens to be the source of the last leg of the TSP tour (the destination is the start citys). The cityxvisited just beforetin the best TSP tour is stored asL(s,C-{s,t},t). The cityyvisited just before reachingxis stored asL(s,C-{s,t,x},x), and the city just beforeyisL(s,C-{s,t,x,y},y), and so on. In this way, we generate the optimal TSP tour backward until we discover the start citysas the last city visited.The Bellman-Held-Karp algorithm runs in O(2

^{n}n^{2}) time. This expression, although exponential inn, is better than O(n!). In fact, the dynamic-programming algorithm gives the optimal solution in a reasonable amount of time even fornas large as 25.## Sample Output

Present your output as in the following format.( 21,993) ( 36,490) ( 59,101) ( 87,740) (193,997) (286, 19) (561,131) (737,100) (821,614) (856,246) (958,136) (962,967) Exact TSP : 0-3-1-2-5-6-7-10-9-8-11-4. cost = 3683 Divide-and-Conquer TSP : 0-1-2-5-6-7-9-10-11-8-3-4. cost = 4350 Greedy TSP : 0-1-2-5-6-7-10-9-8-11-3-4. cost = 4082 Dynamic programming TSP : 0-4-11-8-9-10-7-6-5-2-1-3. cost = 3683## Submission site