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

Answer:1) For finding out which route is shortest we can follow the following given steps. I have tried to write steps in simple language as well as specific.
   i) Suppose we have n cities to travel then let assume that we have city 1 as the starting as well as the ending city.
   ii) Now we will try to generate all the (n-1)! permutations of all the cities.
   iii) Then by getting all the permutations, we will calculate the cost of each permutation.
   iv) Then we will keep on track using the permutation with lowest cost.
   

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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