Search code examples
a-startraveling-salesman

Traveling Salesman with MST and A*?

I was learning for my Exams and I think im missing out on Something about the Traveling Salesman Problem, maybe some of you Guys can help me out

I was wondering If you couldn't use a MST to first find all the Vertices and afterwards use A* to get back to the starting point ? would that be polynomial complexity or am I missing out on Something.

edit: or use any other point-to-point shortest path algorithm

I appreciate any help or answers

Solution

  • The MST doesn't give you a single path containing all the vertices. Also the TSP asks you to find the shortest path, not just any path.