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?

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

3)Does TSP require a designated starting point, or does it pick one itself?

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.
  
Answer 3) Yes, TSP requires a designated starting point. If we are going with the naive solution then we can chose the starting as well as the destination point.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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