非循环路径的所有节点 [英] Non-cycle path to all nodes

问题描述

有一个算法或一组算法，将让你找到最短的步行距离从任意起始节点，这样每个节点被访问过的重量，无向图？这不是很旅行商，因为我不关心，如果一个节点被访问超过一次。 （它甚至没有如果你把它返回到开始关系 - 漫步者可以结束在一些遥远的节点，只要它是需要访问所有节点的最后一个），这不是很最小生成树，因为它可能是去甲 - >乙 - ç - > A - > D的访问A，B，C和D（非唯一的）最短路径我的直觉说，这ISN Ť相当一个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.

推荐答案

维基百科对旅行商问题< /一>：

From Wikipedia's article on Travelling Salesman Problem:

删除您参观每个城市的只有一次的条件不会删除NP难度，因为它很容易看出，在平坦的情况下，存在着访问每个城市只有一次（否则，由三角不等式的最佳之旅，即跳过重复访问的快捷方式不会增加游览长度）。

Removing the condition of visiting each city "only once" does not remove the NP-hardness, since it is easily seen that in the planar case there is an optimal tour that visits each city only once (otherwise, by the triangle inequality, a shortcut that skips a repeated visit would not increase the tour length).

这篇关于非循环路径的所有节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！