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

1) Suppose we have a network of four nodes A,B,C,D connected by links and we know the time it takes to travel from one link to the other. We can easily find the shortest path by comparing the time taken to reach source node A to destination node B, through all possible paths i.e, A-D; A-B-D; A-C-D; A-B-C-D; and A-C-B-

The Traveling Salesman Problem:

In case of TSP, we need to find the shortest route, such that it starts at some node A, covers all other nodes in the network without visiting any of them twice, and finally returns to A. For TSP, we need to compare the travel time taken for following possible routes: A-B-C-D-A; A-B-D-C-A; A-C-B-D-A; A-C-D-B-A; A-D-B-C-A; and A-D-C-B-A. The route that takes the least amount of time, is the shortest route. However, if we have a large number of nodes, we can make use of Djikstra's Algorithm. It begins with the start node A, looks at all its immediate neighbors, then moves on to the nearest neighbor, and from there updates travel times to other unvisited nodes. This process is repeated until we get the shortest path.

2) In order to know if a particular node(city) is already visited or not, flags are used to mark the visited cities on the map or graph.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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