Traveling Salesman Fact Check ********************************************** Loo

Question

Traveling Salesman Fact Check

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

Looking for Different opinions, please dont asnwer this question twice

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

Please review my below understanding of the traveling salesman problem and let me know if the below is true. If what I state below is not true please provide the correct answer and where you found it.

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

1. Generally the travelisng salesman problem is best represented through the use of graphs but not always.

2. Generally the main goal of the TSP is to visit each data point in the graph once and return to the origin spot returning the shortest or cheapest available path.

3. It does this one path at a time each time finding the cheapest or shortest path available. It then compares the value of its finished route to the value of alternate possible routes and with its algorithm it returns the cheapest or shortest route available.

4. The Value of the route is based on a value obtained by combining all of the weights, costs or distances between the paths chosen for each route compared.

5. Generally there are two ways that the TSP algorithm is generated. One is the naïve the other is through Dynamic Programming.

6. The Naive way way thought of as the brute force way and is the more basic in which there is a starting point which is also the ending point and each point is visited once and the cost of the trip is saved and compared to other possible routes or permutations and the cheapest one is returned.

7. The dynamic programming way is where you start at a point and then immediately find the next lowest point and so on so forth until you are back at your starting point and have visited each point once.If there are enough points the process becomes less accurate and it is not considered to be efficiently feasible due to recursive relationships.

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

Please just review my above statements and let me know if these are accurate and factual statements. If they are not please let em know what the correct statement is.

Explanation / Answer

Hello , all the Travelling Salesman Fact you have mentioned above are accurate and factual and are explained in a very simple language.
But I would like to modify the last or 7 statement .

7. In dynamic programming way , we choose a starting point and the starting point is also the ending point .For all the vertices other then the starting vertex(starting point) , the minimum cost path is found with starting vertex as starting point , other vertices as the ending point and all vertices appearing exactly once. And finally minimum of all values are returned .The dynamic programming way uses recursive relationship which makes this approach infeasible even for slightly higher number of vertices.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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