Recall that A* search gives us a more guided way to search the graph looking for a shortest path.
Needs an admissible heuristic to get going... that's something that gives us a lower bound on the distance to the target node.
Here, a target node is any complete tour.
What gives us a lower bound on how the partial tour can be extended to form a complete tour? MST!
I actually have no idea if this would be useful... I did see it mentioned in an AI textbook, though.
