到所有节点的非循环路径
是否有一种算法或一组算法可以让您找到距任意起始节点的最短步行距离，以便在权重无向图中访问每个节点？它不完全是旅行推销员，因为我不关心一个节点是否被多次访问。 （即使你回到起点也没关系——步行者可以在某个遥远的节点结束，只要它是访问所有节点所需的最后一个。）它不是最小生成树，因为走 A-->B-->C-->A-->D 可能是访问 A、B、C 和 D 的（非唯一）最短路径。我的直觉是这不完全是一个 NP 问题，因为它没有使 NP 问题如此棘手的限制。当然，我可能完全错了。
Is there an algorithm or set of algorithms that would let you find the shortest walking distance from an arbitrary start node so that every node gets visited in a weight, undirected graph? It's not quite Traveling Salesman, because I don't care if a node is visited more than once. (It doesn't even matter if you make it back to the start -- the walker can end up in some far-off node as long as it was the last one needed to visit all nodes.) It's not quite minimum spanning tree, because it may be that going A-->B-->C-->A-->D is a (non-unique) shortest path to visit A, B, C, and D. My intuition says that this isn't quite an NP problem, because it doesn't have the restrictions that make NP problems so tricky. I could, of course, be completely wrong.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
来自维基百科关于旅行推销员问题的文章：
From Wikipedia's article on Travelling Salesman Problem:
不确定向已接受答案的问题添加答案的礼仪是什么。
我添加这个答案只是为了不必跳到另一页，不必处理平面图和三角形不等式，而且事实上这很简单，可能更容易理解。
哈密顿路径问题可以简化为：
假设我们有一个多项式时间算法来解决找到访问所有顶点的最小权重游走的问题。
给定一个我们需要确定是否存在哈密顿路径的图，我们只需将其按原样提供给手头的问题算法，设置边权重 = 1。 n-1，则原图中不存在哈密顿路径，否则存在。
所以这个问题是NP-Hard问题。
Not sure what the etiquette is to add an answer to a question with an already accepted answer.
I am adding this answer just for the sake of not having to jump to another page, to not have to deal with planar graphs and triangle inequality and the fact that this is simple and probably easier to understand.
Hamiltonian Path problem can be reduced to this:
Suppose we had a polynomial time algorithm to solve our problem of finding a least weight walk which visits all vertices.
Given a graph of which we need to decide a hamiltonian path exists or not, we just feed it as it is, to the problem algorithm at hand, setting edge weights = 1. If the algorithm returns a value > n-1, then there is no hamiltonian path in the original graph, else there is.
So this problem is NP-Hard.