小编典典

到所有节点的非循环路径

algorithm

是否有一种算法或一组算法可以让您找到到任意起始节点的最短步行距离,从而使每个节点都能在一个无向权重图中被访问?这不是一个旅行推销员,因为我不在乎节点是否被多次访问。(即使您重新开始也没有关系-
只要行人可以访问所有节点,只要它是最后一个节点,步行者就可以到达某个遥远的节点。)这不是最小的生成树,因为可能是A-> B-> C-> A->
D是访问A,B,C和D的(唯一的)最短路径。我的直觉是,这不是这不是一个NP问题,因为它没有使NP问题变得如此棘手的限制。我当然可以完全错。


阅读 217

收藏
2020-07-28

共1个答案

小编典典

摘自维基百科有关旅行推销员问题的文章:

删除“仅一次访问”每个城市的条件并不会消除NP硬度,因为很容易看出,在平面情况下,有一个最佳游标只能访问每个城市一次(否则,通过三角形不等式,这是一个捷径跳过重复访问不会增加游览时间)。

2020-07-28