拥有 MST 和 A* 的旅行推销员？

Question

我正在为我的考试学习，我想我错过了关于旅行商问题的一些事情，也许你们中的一些人可以帮助我

我想知道您是否不能使用 MST 先找到所有顶点然后使用 A* 返回起点？那会是多项式复杂度还是我错过了什么。

编辑：或使用任何其他点对点最短路径算法

感谢任何帮助或回答

Answer 1

MST 不会为您提供包含所有顶点的单一路径。 TSP 还要求您找到最短路径，而不仅仅是任何路径。