The Traveling Salesman Problem **************************************** Please c

Question

The Traveling Salesman Problem

****************************************

Please cite your sources and be as detailed as possible. Also, try to explain it in a non-technical

sense that is easy to understand for someone who might not have an extensive CS background.

***************************************

1)How does the traveling salesman problem (TSP) with graphs decide which route is the shortest? please be specific on the process it takes but make it as simple as possible.

2)How does the traveling salesman problem (TSP) know it has already visited a city?

Again please cite your sources and be as detailed as possible when answering the above and describing the process that the program takes.

Explanation / Answer

a,)

1) Consider city 1 as the starting and ending point.
2) Generate all (n-1)! Permutations of cities.
3) Calculate cost of every permutation and keep track of minimum cost permutation.
4) Return the permutation with minimum cost.

b.)

If size of S is 2, then S must be {1, i},

C(S, i) = dist(1, i)

Else if size of S is greater than 2.

C(S, i) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.

For a set of size n, we consider n-2 subsets each of size n-1 such that all subsets don’t have nth in them.
Using the above recurrence relation, we can write dynamic programming based solution. There are at most O(n*2n) subproblems, and each one takes linear time to solve. The total running time is therefore O(n2*2n). The time complexity is much less than O(n!), but still exponential. Space required is also exponential. So this approach is also infeasible even for slightly higher number of vertices

Time Complexity: ?(n!)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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