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

Let us first try to understand what the problem is. Suppose you are a salesman who is given a job to visit 10 locations and make the sell. But in order to finish the task efficiently (in time with less travel) you need to find the best route.

Now to understand this let us just consider 3 cities (locations) you need to visit. Possible routes(combination) will be 3*2*1 (as we will make starting point from all three place, then we are left with 2 choices for second location and effectively 1 for third location) which means a factorial of 3.Now this is a small number so easy to calculate and define which one is shortest route. Consider 10 factorial (3628800 which is huge) and in real time scenario the number would be even big.

Now to solve such problem we need to have an efficient algorithm in place. An algorithm/solution where every location is covered and at most once and make sure such requirement is fulfilled and to do so proper mutation and crossover methods are required. Mutation methods are used to shuffle the route (no addition/removal of a location) and one such is swap mutation(which just randomly picks two location and swap them to create a different order and it make sure every time a different order because it performs swap operation on the new list). Now once we are done with mutation, we jump to crossover method. One example is ordered cross over method. Here a subset is selected from the parent set and then gets added to the offspring subset. And in case there are some missing values then they are added from the second parent found in that order. Combining both methods gives us the optimal route.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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