Page 1 of 1
Traveling Salesman Problem .. MST or not?
Posted: Mon Apr 23, 2007 8:24 pm
by LithiumDex
I've heard this problem is NP Complete, but looking at it... it seems like it could be solved with a simple minimum spanning tree algorithm -- can someone explain this?
Posted: Mon Apr 23, 2007 8:34 pm
by sohel
It is an NP complete problem!!
Can you explain your
simple MST approach?
Posted: Mon Apr 23, 2007 8:37 pm
by LithiumDex
Don't we just have an undirected graph of N nodes, each edge having a weight? Why would you think MST would fail for this?
Posted: Mon Apr 23, 2007 8:55 pm
by sohel
Travelling Salesman Problem
Given N nodes and the costs of the edges between every pair of nodes, what is the cheapest round-trip route that visits every node exactly once and then returns to the starting node?
Minimum Spanning Tree
Given a graph consiting of N nodes, find a connected subgraph which has N-1 edges and sum of these edges is minimized.
So these two things aren't exactly identical. The degree of every node in the subgraph of a TSP is exactly 2, but this isn't true for the subgraph of a MST.
Posted: Mon Apr 23, 2007 8:57 pm
by LithiumDex
I understand, thanks.
Posted: Tue Apr 24, 2007 1:35 am
by stubbscroll
Actually, MST can be used (as part of the algorithm) to approximately solve TSP when the triangle inequality holds for the graph.
http://en.wikipedia.org/wiki/Travelling ... cial_cases