dmd*_*dmd 72 algorithm graph-theory
我有一个带有大约100个节点和大约200个边的无向图.一个节点标记为"开始",一个节点标记为"结束",并且大约有十几个标记为"必须通过".
我需要找到通过此图表的最短路径,该路径从'start'开始,在'end'结束,并通过所有'mustpass'节点(以任何顺序).
(http://3e.org/local/maize-graph.png/http://3e.org/local/maize-graph.dot.txt是有问题的图表 - 它代表宾夕法尼亚州兰开斯特的一个玉米迷宫)
Shr*_*saR 72
将此与旅行商问题进行比较的其他人可能都没有仔细阅读您的问题.在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 3)和O(k!n )对于所有排列部分,100 ^ 3 +(12!)(100)实际上是花生,除非你有一些非常严格的约束.
Nic*_*ynt 14
实际上,你发布的问题类似于旅行推销员,但我认为更接近一个简单的寻路问题.您只需在尽可能短的时间(距离)内访问特定的节点集,而不需要访问每个节点.
这样做的原因是,与旅行商问题不同,玉米迷宫不允许您直接从任何一个点旅行到地图上的任何其他点,而无需通过其他节点到达那里.
我实际上建议将A*寻路作为一种技术来考虑.您可以通过确定哪些节点可以直接访问哪些其他节点以及来自特定节点的每个跃点的"成本"来进行设置.在这种情况下,看起来每个"跳"可能具有相同的成本,因为您的节点看起来相对紧密.A*可以使用此信息查找任意两点之间的最低成本路径.因为你需要从A点到达B点并且访问中间约12个,所以即使使用寻路的蛮力方法也不会受到伤害.
只是另一种考虑因素.它确实看起来非常像旅行推销员的问题,这些都是很好的论文,但是看得更近,你会发现它只是过于复杂的事情.^ _ ^这来自一个视频游戏程序员的头脑,他之前处理过这些事情.
小智 14
这是两个问题...... Steven Lowe指出了这一点,但没有对问题的后半部分给予足够的尊重.
您应该首先发现所有关键节点之间的最短路径(开始,结束,必须).一旦发现了这些路径,您就可以构建一个简化的图形,其中新图形中的每个边缘都是原始图形中从一个关键节点到另一个关键节点的路径.您可以使用许多寻路算法来查找此处的最短路径.
但是,一旦你有了这个新的图表,你就会遇到旅行销售员的问题(好吧,几乎......不需要回到你的起点).上述任何与此相关的帖子都将适用.
这不是TSP 问题，也不是 NP-hard 问题，因为原始问题不要求必须通过的节点只访问一次。在通过 Dijkstra 算法编译所有必须通过的节点之间的最短路径列表后，这使得答案变得更加简单。可能有更好的方法，但一个简单的方法是简单地向后处理二叉树。想象一个节点列表 [start,a,b,c,end]。将简单距离相加 [start->a->b->c->end] 这是您要击败的新目标距离。现在尝试 [start->a->c->b->end] ，如果这样更好将其设置为目标（并记住它来自该模式的节点）。逆向排列排列：
其中之一将是最短的。
（如果有的话，“多次访问”节点在哪里？它们只是隐藏在最短路径初始化步骤中。a 和 b 之间的最短路径可能包含 c 甚至终点。您不需要关心)
Andrew Top有正确的想法:
1)Djikstra的算法2)一些TSP启发式算法.
我推荐Lin-Kernighan启发式:它是任何NP Complete问题中最着名的之一.唯一要记住的是,在第2步之后再次展开图形后,您可能在扩展路径中有循环,因此您应该绕过那些(看看路径上的顶点的程度).
我实际上不确定这个解决方案相对于最佳解决方案有多好.可能存在一些与短路有关的病理情况.毕竟,这个问题看起来很像Steiner Tree:http://en.wikipedia.org/wiki/Steiner_tree,你绝对不能通过收缩图表和运行Kruskal来近似Steiner Tree.