1. Recall the language TSP = (G, k | k is an integer; G is an undirected, weight

Question

1. Recall the language TSP = (G, k | k is an integer; G is an undirected, weighted, complete graph with non-negative integer weights with a tour of weight k) Note that we require that k be an integer and that G be a complete graph with non-negative integer weights. Suppose that there exists an efficient algorithm ALG that decides TSP. Devise an efficient algorithm which, given an undirected, weighted, complete graph G with non-negative integer weights as input, finds a tour of minimum weight in G. Hint: As a first step, consider finding the minimum weight of a tour in the graph. The first procedure that comes to your mind might not be efficient! You can think about the input G as an array of weights W[1....n] where n is the number of vertices in G.

Explanation / Answer

The first approach that comes to the mind is:

1) let i be the stating city

2) consider all permutations of remaining cities, put it after i and put i further.

3) calculate the cost of travelling in the order in which cities occurs in each of sequence formed above.

4) repeat this replacing i with all other nodes 1 by 1.

5) find minimum of the above weights

for ex- consider a graph with 3 vertices

choose 1 as start point and generate all permutations, and append 1 after it : 1 2 3 1, 1 3 2 1

similarly for 2 : 2 1 3 2, 2 3 1 2

for 3 : 3 1 2 3, 3 2 1 3

total 6 sequence formed.

According to the approach above, time complexity is O(n!)

But there is a better approach using dynamic programming.

To formulate the solution as dynamic programming, we need to find the optimal substructure. We need to find the solution having overlapping subproblem.

Let us try to understand it carefully, what we want is a tour that starts and ends at vertex i. let j be the vertex just before the end or just before the vertex i in our path. for example let tour be 1 2 3 4 5 6 1, then i is 1 and j is 6.

what we need to find is permutation of vertices starting with i and ending with j such that cost of permutation added with W(j, i) is minimum. once the minimum cost path is chosen, we can consider any of the vertex as starting vertex in obtained sequence. So, we will be considering 1 as starting vertex in our tour.

let S be set of vertices , i be stsrting vertex and j be vertex just before i in tour, let C(S,i) be cost of TSP in S

C(S,i) = min { C(S -{i} , j) + W(j,i)} for all vertices j in S and j!=i and j!=1

we can calculate the C(S -{i}, j) in the similar fashion.

Algorithm for the above solution is:

TSPAlgo

C({1}, 1} = 0;

for Ssize = 2 to n

generate all subsets of Ssize i vertices of G having 1 as one of the vertices

Initialise C(S, i) = infinity

for every j in S and j!=1

C(S,i) = min { C(S -{i} , j) + W(j,i)} for all vertices j in S and j!=i and j!=1

end

end

TSP = min { C(G, j) + d(j,1) } for all j in G

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.