所有节点的非循环路径

Question

是否有一种算法或一组算法可以让您找到距离任意起始节点最短的步行距离,以便每个节点都能在权重无向图中被访问？这不是旅行推销员,因为我不在乎是否多次访问一个节点.(如果你把它重新开始也没关系 - 只要它是访问所有节点所需的最后一个节点,walker就可以在一些遥远的节点结束.)它不是最小的生成树,因为它可能是A - > B - > C - > A - > D是访问A,B,C和D的(非唯一的)最短路径.我的直觉说这不是'这是一个NP问题,因为它没有限制使NP问题如此棘手.当然,我完全错了.

Answer 1

来自维基百科关于旅行商问题的文章:

去除每个城市"仅一次"的条件并不能消除NP-硬度,因为很容易看出在平面情况下有一个最佳的游览只能访问每个城市一次(否则,通过三角形不等式,一个捷径跳过重复访问不会增加巡回长度).