Menu
Can we solve the Traveling Salesman Problem by finding the Minimum Spanning Tree?
843
The 'Travelling salesman problem' is very similar to the assignment problem except that in the former, there are additional restrictions that a salesman starts from his city, visits each city once and returns to his home city, so that the total distance (cost or time) is minimum.
Minimum spanning tree is based on cut property whereas Shortest path is based on the edge relaxing property. A cut splits a graph into two components. It may involve multiple edges. In MST, we select the edge with the least weight.
The traveling salesman problem (TSP) is an algorithmic problem tasked with finding the shortest route between a set of points and locations that must be visited. In the problem statement, the points are the cities a salesperson might visit.
The Brute Force approach, also known as the Naive Approach, calculates and compares all possible permutations of routes or paths to determine the shortest unique solution. To solve the TSP using the Brute-Force approach, you must calculate the total number of routes and then draw and list all the possible routes.
The Minimum Spanning Tree problem asks you to build a tree that connects all cities and has minimum total weight, while the Travelling Salesman Problem asks you to find a trip that visits all cities with minimum total weight (and possibly coming back to your starting point).
If you're having trouble seeing the difference, in MST, you need to find a minimum weight tree in a weighted graph, while in TSP you need to find a minimum weight path (or cycle / circuit). Does that help?
88
It's the difference between
Finding an acyclic connected subgraph T of G with V(T) = V(G) and Weight(T) is minimal
and
Finding a cycle C in G such that V(C) = V(G) and Weight(C) is minimal
where Weight(X) = Sum of edges of X. As you can see these two problems are pretty different.
Yet, there is a relation between the two. If the graph weights satisfies the triangle inequality, one can use the MST to approximate the TSP within a factor of x2: compute the MST, then traverse it (from any root) and return the vertices in a pre-order. You can find the detailed analysis of this approximation (as well as other approximations) in The traveling salesman problem: An overview of exact and approximate algorithms by G Laporte - European Journal of Operational Research, 1992 - Elsevier.
34
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
