在图表中查找访问某些节点的最短路径

我有一个带有大约100个节点和大约200个边的无向图.一个节点标记为"开始",一个节点标记为"结束",并且大约有十几个标记为"必须通过".

我需要找到通过此图表的最短路径,该路径从'start'开始,在'end'结束,并通过所有'mustpass'节点(以任何顺序).

(http://3e.org/local/maize-graph.png/http://3e.org/local/maize-graph.dot.txt是有问题的图表 - 它代表宾夕法尼亚州兰开斯特的一个玉米迷宫)

1> ShreevatsaR..：

---

将此与旅行商问题进行比较的其他人可能都没有仔细阅读您的问题.在TSP中,目标是找到访问所有顶点的最短循环(哈密顿循环) - 它对应于将每个节点标记为"必须".

在你的情况下,鉴于你只有十几个被标记为'mustpass',并给出了12!相当小(479001600),你可以简单地尝试只有'mustpass'节点的所有排列,并查看从'start'到'end'的最短路径,它按顺序访问'mustpass'节点 - 它只是是该列表中每两个连续节点之间的最短路径的串联.

换句话说,首先找到每对顶点之间的最短距离(你可以使用Dijkstra算法或其他算法,但是使用那些小数字(100个节点),即使是最简单的代码Floyd-Warshall算法也会及时运行).然后,一旦你在表中有这个,尝试你的'mustpass'节点的所有排列,其余的.

像这样的东西:

//Precomputation: Find all pairs shortest paths, e.g. using Floyd-Warshall
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
    for i=1 to n:
        for j=1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
//That *really* gives the shortest distance between every pair of nodes! :-)

//Now try all permutations
shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
    shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest

(当然这不是真正的代码,如果你想要实际路径,你必须跟踪哪个排列给出最短距离,以及所有对最短路径是什么,但你明白了.)

它将在任何合理的语言上运行最多几秒:)
[如果你有n个节点和k'必须'节点,它的运行时间为Floyd-Warshall部分的O(n ³)和O(k!n )对于所有排列部分,100 ^ 3 +(12!)(100)实际上是花生,除非你有一些非常严格的约束.

---

@maditya:首先,我希望你同意(引用Steven A Lowe对另一个答案的评论)像"TSP很难,bwahahaha"这样的答案对于那些有真正需要解决的问题的人来说并不是一个合适的答案,特别是一个很容易解决的问题.在过去的几十年中解决了任何计算机问题.其次,由于微不足道的原因(不同的输入格式),这与TSP不同:它包含的TSP的微小实例是用于较小的图形,而不是输入大小N.因此NP完全性取决于有多少"必须"节点渐近地:如果它总是12,或者O(log N),它不是NP完全等等.

---

鉴于输入的小小,我同意答案.但我很感兴趣为什么你拒绝别人的断言,这是TSP的一个例子.我理解它的方式,您可以提取所有必须传递的节点并使用它来创建子图.子图中节点之间的边具有与原始图上的APSP解相对应的权重.那问题不会成为子图上的TSP实例吗？你的解决方案似乎是**问题的蛮力解决方案(这很好).

2> Steven A. Lo..：

---

运行Djikstra的算法来查找所有关键节点(开始,结束和必须通过)之间的最短路径,然后深度优先遍历应该告诉您通过触发所有节点的结果子图的最短路径开始.必须......结束

3> Nicholas Fly..：

---

实际上,你发布的问题类似于旅行推销员,但我认为更接近一个简单的寻路问题.您只需在尽可能短的时间(距离)内访问特定的节点集,而不需要访问每个节点.

这样做的原因是,与旅行商问题不同,玉米迷宫不允许您直接从任何一个点旅行到地图上的任何其他点,而无需通过其他节点到达那里.

我实际上建议将A*寻路作为一种技术来考虑.您可以通过确定哪些节点可以直接访问哪些其他节点以及来自特定节点的每个跃点的"成本"来进行设置.在这种情况下,看起来每个"跳"可能具有相同的成本,因为您的节点看起来相对紧密.A*可以使用此信息查找任意两点之间的最低成本路径.因为你需要从A点到达B点并且访问中间约12个,所以即使使用寻路的蛮力方法也不会受到伤害.

只是另一种考虑因素.它确实看起来非常像旅行推销员的问题,这些都是很好的论文,但是看得更近,你会发现它只是过于复杂的事情.^ _ ^这来自一个视频游戏程序员的头脑,他之前处理过这些事情.

---

+1 - 这是一个比'旅行销售员问题很难,bwahahaha'更好的答案

4> 小智..：

---

这是两个问题...... Steven Lowe指出了这一点,但没有对问题的后半部分给予足够的尊重.

您应该首先发现所有关键节点之间的最短路径(开始,结束,必须).一旦发现了这些路径,您就可以构建一个简化的图形,其中新图形中的每个边缘都是原始图形中从一个关键节点到另一个关键节点的路径.您可以使用许多寻路算法来查找此处的最短路径.

但是,一旦你有了这个新的图表,你就会遇到旅行销售员的问题(好吧,几乎......不需要回到你的起点).上述任何与此相关的帖子都将适用.

---

+1谢谢你的澄清,你是绝对正确的

5> Ying Xiao..：

---

Andrew Top有正确的想法:

1)Djikstra的算法2)一些TSP启发式算法.

我推荐Lin-Kernighan启发式:它是任何NP Complete问题中最着名的之一.唯一要记住的是,在第2步之后再次展开图形后,您可能在扩展路径中有循环,因此您应该绕过那些(看看路径上的顶点的程度).

我实际上不确定这个解决方案相对于最佳解决方案有多好.可能存在一些与短路有关的病理情况.毕竟,这个问题看起来很像Steiner Tree:http://en.wikipedia.org/wiki/Steiner_tree,你绝对不能通过收缩图表和运行Kruskal来近似Steiner Tree.