我有一个大约 100 个节点和大约 200 条边的无向图。一个节点标记为“开始”，一个节点标记为“结束”，大约有十几个标记为“必须通过”。
我需要找到从“开始”开始，在“结束”结束，并通过所有“必须通过”节点（以任何顺序）的最短路径。
（http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt是有问题的图表 - 它代表宾夕法尼亚州兰开斯特的玉米迷宫）
dmd
问问题
86585 次
10 回答
79
将其与旅行推销员问题进行比较的其他人可能没有仔细阅读您的问题。在 TSP 中，目标是找到访问所有顶点的最短循环（哈密顿循环）——它对应于将每个节点标记为“必须通过”。
就您而言，鉴于您只有大约十二个标有“必须通过”的标签，并且有 12 个！相当小（479001600），您可以简单地尝试仅“必须通过”节点的所有排列，并查看从“开始”到“结束”按该顺序访问“必须通过”节点的最短路径 - 它只会是该列表中每两个连续节点之间的最短路径的串联。
换句话说，首先找到每对顶点之间的最短距离（您可以使用 Dijkstra 算法或其他算法，但是对于那些小数字（100 个节点），即使是最简单的代码Floyd-Warshall 算法也会及时运行）。然后，一旦你把它放在一个表中，尝试你的“必须通过”节点的所有排列，其余的。
像这样的东西：
//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) 实际上是花生，除非你有一些真正的限制性约束。]
于 2008-10-23T01:50:29.360 回答
29
运行Djikstra 算法以找到所有关键节点（开始、结束和必须通过）之间的最短路径，然后深度优先遍历应该告诉您通过结果子图的最短路径，该路径触及所有节点 start .. . 必须通过 ... 结束
于 2008-10-21T16:05:41.697 回答
18
这是两个问题... Steven Lowe 指出了这一点，但没有对问题的后半部分给予足够的尊重。
您应该首先发现所有关键节点（开始、结束、必须通过）之间的最短路径。一旦发现这些路径，您就可以构建一个简化图，其中新图中的每条边都是从原始图中的一个关键节点到另一个关键节点的路径。您可以使用许多寻路算法在这里找到最短路径。
但是，一旦有了这个新图表，您就完全遇到了 Traveling Salesperson 问题（嗯，几乎……无需返回您的起点）。上面提到的任何与此相关的帖子都将适用。
于 2008-10-21T17:24:33.160 回答
14
实际上，您发布的问题类似于旅行推销员，但我认为更接近于一个简单的寻路问题。无需访问每个节点，您只需在尽可能短的时间（距离）内访问一组特定的节点。
这样做的原因是，与旅行商问题不同，玉米迷宫不允许您直接从地图上的任何一个点前往任何其他点，而无需通过其他节点到达那里。
我实际上会推荐 A* 寻路作为一种需要考虑的技术。您可以通过决定哪些节点可以直接访问哪些其他节点以及来自特定节点的每一跳的“成本”是多少来设置它。在这种情况下，看起来每个“跃点”的成本可能相同，因为您的节点似乎间隔相对较近。A* 可以使用此信息找到任意两点之间的最低成本路径。由于您需要从 A 点到 B 点并在其间访问大约 12 个点，因此即使是使用寻路的蛮力方法也不会受到伤害。
只是一个可供考虑的替代方案。它看起来确实非常像旅行推销员问题，这些都是值得阅读的好论文，但仔细观察，你会发现它只是过于复杂的事情。^_^ 这来自之前处理过这类事情的视频游戏程序员的想法。
于 2008-10-21T17:11:53.467 回答
7
这不是TSP 问题，也不是 NP 难题，因为原始问题不要求必须通过的节点只访问一次。在通过 Dijkstra 算法编译所有必须通过的节点之间的最短路径列表之后，这使得答案变得非常简单。可能有更好的方法，但简单的方法是简单地向后工作二叉树。想象一个节点列表 [start,a,b,c,end]。将简单距离相加 [start->a->b->c->end] 这是您要击败的新目标距离。现在尝试 [start->a->c->b->end] 如果这样更好，请将其设置为目标（并记住它来自该节点模式）。在排列上向后工作：
- [开始->a->b->c->结束]
- [开始->a->c->b->结束]
- [开始->b->a->c->结束]
- [开始->b->c->a->结束]
- [开始->c->a->b->结束]
- [开始->c->b->a->结束]
其中之一将是最短的。
（如果有的话，“多次访问”节点在哪里？它们只是隐藏在最短路径初始化步骤中。a 和 b 之间的最短路径可能包含 c 甚至终点。你不需要关心)
于 2015-07-15T23:29:47.717 回答
6
Andrew Top 的想法是正确的：
1) Djikstra 算法 2) 一些 TSP 启发式算法。
我推荐 Lin-Kernighan 启发式算法：它是任何 NP 完全问题中最著名的算法之一。唯一要记住的另一件事是，在您在第 2 步之后再次展开图形后，您的展开路径中可能有循环，因此您应该绕过这些循环（查看路径上的顶点度数）。
我实际上不确定这个解决方案相对于最佳解决方案有多好。可能有一些病理情况与短路有关。毕竟，这个问题看起来很像 Steiner Tree：http ://en.wikipedia.org/wiki/Steiner_tree并且你绝对不能通过收缩你的图表并运行 Kruskal's 来近似 Steiner Tree。
于 2008-10-21T22:16:40.853 回答
2
考虑到节点和边的数量相对有限，您可能可以计算出每条可能的路径并取最短的一条。
通常这被称为旅行商问题，并且无论您使用什么算法，它都有一个不确定的多项式运行时间。
于 2008-10-21T16:08:47.087 回答
1
这个问题谈到了必须以任何顺序通过。我一直在尝试寻找有关必须通过节点的定义顺序的解决方案。我找到了答案，但由于 StackOverflow 上的任何问题都没有类似的问题，所以我在这里发布以让最多的人从中受益。
如果定义了顺序或必须通过，那么您可以多次运行 dijkstra 算法。例如，假设您必须从spass throughk1和（按相应顺序）开始k2并k3停在e. 然后你可以做的是在每对连续的节点之间运行 dijkstra 算法。成本和路径将由下式给出：
dijkstras(s, k1) + dijkstras(k1, k2) + dijkstras(k2, k3) + dijkstras(k3, 3)
于 2020-08-29T18:20:14.513 回答
0
在十几个“必须访问”的节点上使用蛮力怎么样。您可以轻松覆盖 12 个节点的所有可能组合，这为您提供了一个可以遵循的最佳电路来覆盖它们。
现在您的问题被简化为找到从起始节点到电路的最佳路线之一，然后您沿着路线直到您覆盖它们，然后找到从那里到结束的路线。
最终路径由以下部分组成：
开始 -> 电路路径* -> 必须访问节点的电路 -> 结束路径* -> 结束
你会发现我用 * 标记的路径是这样的
从开始节点到电路上的每个点进行 A* 搜索，从电路上的下一个和上一个节点到结束进行 A* 搜索（因为您可以在任一方向上跟随电路）最终得到的是很多搜索路径，您可以选择成本最低的一个。
通过缓存搜索有很大的优化空间，但我认为这会产生很好的解决方案。
但是，它并没有接近寻找最佳解决方案，因为这可能涉及将必须访问的电路留在搜索中。
于 2009-05-29T15:50:47.787 回答
0
任何地方都没有提到的一件事是，是否可以在路径中多次访问同一个顶点。这里的大多数答案都假设多次访问同一个边是可以的，但我认为这个问题（一条路径不应该多次访问同一个顶点！）是不能访问同一个顶点两次。
所以蛮力方法仍然适用，但是当您尝试计算路径的每个子集时，您必须删除已经使用的顶点。
于 2010-05-10T20:12:11.883 回答