在一个图中找到访问特定节点的最短路径。

Question

我有一个大约有100个节点和200条边的无向图。其中一个节点标记为“起点”，一个标记为“终点”，还有大约十几个节点被标记为“必经之路”。

我需要找到通过这个图的最短路径，从“起点”开始，以“终点”结束，并且经过所有“必经之路”的节点（无论顺序如何）。

(该图代表了宾夕法尼亚州兰开斯特的一个玉米迷宫。 图片链接：http://3e.org/local/maize-graph.png，文本链接：http://3e.org/local/maize-graph.dot.txt)

- dmd

Answer 1

如果有人把这个问题和旅行商问题进行比较，那他们可能没有仔细阅读你的问题。在旅行商问题中，目标是找到访问所有顶点的最短循环（哈密顿环）——它对应于每个节点都被标记为“必经之路”。

在您的情况下，由于您只有大约十几个标记为“必经之路”的点，并且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³)，对于所有排列部分是O(k!n)，100^3+(12!)(100)基本上是小菜一碟，除非你有一些非常严格的限制要求]

- ShreevatsaR

---

鉴于输入规模较小，我同意这个答案。但我想知道为什么您拒绝其他人认为这是TSP问题的说法。据我理解，您可以提取所有必须经过的节点并将其用于创建一个子图。子图中的节点之间的边缘具有与原始图上APSP解决方案相对应的权重。那么问题不就变成了在子图上的TSP实例吗？您的解决方案似乎是针对那个问题的暴力解决方案（这很好）。 - maditya

首先，我希望您同意（引用Steven A Lowe在另一个答案中的评论）“像‘TSP很难，哈哈哈’这样的答案对于有真正问题需要解决的人不是适当的答案，尤其是能够在过去几十年的任何计算机上轻松解决问题。” 其次，由于输入格式不同，它并不完全等同于TSP，因此包含的小实例是针对小图而非大小为N的输入。因此，NP完全性取决于渐近有多少个“必须通过”节点：如果始终为12或O（log N），则不是NP完全问题等。 - ShreevatsaR

我不确定结果是否为路径。想象一下，需要通过 b 从 a 到 c。可能最短的从 b 到 a 和 c 的路径共享一条边。在这种情况下，该边将重复两次。其中一条路径需要比最优解更差，以避免生成循环。 - Pietro Saccardi

从问题描述来看，目标似乎是找到穿过所有这些节点的最短“路径”，如果一些边被重复使用也没有关系。也就是说，“路径”在这里使用得很宽泛。实际上，如果不允许重复边，可能根本没有答案（例如，考虑一个图B-A-C，要求您从A到C通过B：没有办法不重复B-A边）。 - ShreevatsaR

弗洛伊德-沃尔什算法在这里没有正确实现：由于数组的所有单元格都被初始化为INF，所以行d[i][j] = min(d[i][j], d[i][k] + d[k][j])变为d[i][j] = min(INF, INF + INF)，所有单元格始终保持等于INF。您需要添加一步，将该数组填充为来自图形的边长。 - Stef

实际上有一种更优的方法。为了避免考虑每个排列，我们可以为每个必经节点的子集和S中每对可能的起点和终点定义 dp[S][a][b]。这将表示从a开始并以b结束访问S中所有节点的最优方式。总共有(2^12 * 12^2)个状态，为了计算每一个状态，我们只需要考虑在子集中访问第二个节点的12种可能性。总体而言，我们的时间复杂度是O(2^K * K^3)，其中K是必经节点的数量（包括起点和终点）。 - Mushegh

Answer 2

运行Dijkstra算法，以找到所有关键节点（起点、终点和必经点）之间的最短路径，然后进行深度优先遍历，可以告诉你通过接触所有节点从起点到达终点的最短路径。

- Steven A. Lowe

---

这似乎有潜力比所选解决方案更有效。我敢打赌，如果你再深入研究一下，它的得分会更高。我首先需要考虑的是，是否所有对之间的最短路径都保证了所有必需节点之间的路径..但我相信它会（假设是无向的）。 - galactikuh

我认为如果路径不能重复边，则此方法不起作用。 - tuket

深度优先遍历如何在Advent of Code day 24的示例中找到最短路径？http://adventofcode.com/2016/day/24 - user2609980

Answer 3

这涉及到两个问题... Steven Lowe指出了这一点，但是没有充分重视问题的后半部分。

首先，您应该发现所有关键节点（起点、终点、必经之路）之间的最短路径。一旦这些路径被发现，您可以构建一个简化图，其中新图中的每条边都是原始图中从一个关键节点到另一个关键节点的路径。有很多可用于查找最短路径的路径规划算法。

然而，一旦您拥有了这个新图，您就会遇到旅行商问题（几乎相同，不需要回到起点）。关于此问题的任何帖子，如上所述，都将适用。

- Andrew Top

Answer 4

实际上，您发布的问题类似于旅行商问题，但我认为更接近简单的路径查找问题。与需要访问每个节点不同，您只需要在最短时间（距离）内访问特定的一组节点。

原因是，与旅行商问题不同，迷宫不允许您直接从地图上的任何一个点到达另一个点，而无需通过其他节点进行通行。

我实际上建议考虑使用A *路径查找技术。您可以通过决定哪些节点直接访问其他节点以及每个特定节点的“成本”来设置此功能。在这种情况下，由于您的节点相对较近，每个“跳跃”可能具有相等的成本。 A *可以利用此信息找到任何两点之间的最低成本路径。由于您需要从A点到B点，中间还要访问约12个点，即使使用路径查找的蛮力方法也不会有任何影响。

只是值得考虑的另一种选择。它看起来非常像旅行商问题，阅读这些论文很有好处，但仔细观察，您会发现这只是过度复杂化了事情。 ^ _ ^这是来自曾经处理过这些问题的电子游戏程序员的想法。

- Nicholas Flynt

---

+1 - 这个回答比“旅行商问题很难，哈哈哈”要好得多。 - Steven A. Lowe

Answer 5

这不是旅行商问题，也不是NP难问题，因为原问题并不要求必须经过的节点只被访问一次。这使得答案变得简单，只需通过Dijkstra算法编制所有必须经过节点之间的最短路径列表，然后强制执行即可。可能有更好的方法，但一个简单的方法是将二叉树反向处理。想象一个节点列表[start,a,b,c,end]，求出简单距离和[start->a->b->c->end]，这就是你新的目标距离。现在尝试[start->a->c->b->end]，如果更好，就将其设置为目标（并记住它来自那个节点模式）。倒推排列：

• [start->a->b->c->end]
• [start->a->c->b->end]
• [start->b->a->c->end]
• [start->b->c->a->end]
• [start->c->a->b->end]
• [start->c->b->a->end]

其中一个将是最短的。

(如果有"被多次访问"的节点在哪里？它们只是隐藏在最短路径初始化步骤中。a和b之间的最短路径可能包含c，甚至是终点。你不需要关心)

- bjorke

---

只访问一次是最短路径条件所要求的。 - Aziuth

哦，我之前还挺确定的，但是没错，你说得对。显然不是在有几个分支的树中。但是问题在于，如果我们将问题抽象化成一个新图，该图仅包含必须经过的节点，并且这些节点之间完全相连，节点之间的距离为原始图中的最短路径，则我们会得到TSP问题。所以，你确定它不是NP难问题吗？我认为在一般情况下，必须经过的节点数量取决于总节点数，例如，如果总节点数是必须经过节点的多项式，那么我们就会得到NP难度问题，对吧？ - Aziuth

从a到b的路径可能会经过c，因此没有任何分支会阻止其他分支。这只是排列组合。 - bjorke

是的？但是如果我们假设必须经过节点的数量与总节点数有某种联系，比如“总节点数是必须经过节点的多项式”，那么排列就是O(n!)。你刚刚通过蛮力法解决了TSP问题。 - Aziuth

Answer 6

Andrew Top有正确的想法：

1）Djikstra算法 2）一些TSP启发式算法。

我推荐Lin-Kernighan启发式算法：它是任何NP完全问题中最知名的之一。唯一需要记住的是，在步骤2扩展图形后，您可能会在扩展路径中遇到环路，因此应该绕过这些环路（查看路径上沿着顶点的度数）。

实际上，我不确定相对于最优解而言，这种解决方案有多好。可能存在一些与短路有关的病态情况。毕竟，这个问题看起来非常像Steiner树：http://en.wikipedia.org/wiki/Steiner_tree，你绝不能仅通过收缩图形并运行Kruskal等算法来近似Steiner树。

- Ying

Answer 7

考虑到节点和边的数量是相对有限的，您可以计算每条可能的路径并选择最短的一条。

通常称为旅行商问题，无论使用什么算法，它都具有非确定性多项式运行时间。

http://en.wikipedia.org/wiki/Traveling_salesman_problem

- Rafe

Answer 8

该问题涉及“任意顺序必过” 。我一直在尝试寻找有关必经节点定义顺序的解决方案。我找到了答案，但由于StackOverflow上没有类似的问题，我在这里发布它，让尽可能多的人从中受益。

如果必经节点的顺序是“定义”的，则可以多次运行狄克斯特拉算法。例如，假设您必须从s开始，通过k1、k2和k3（分别按顺序）并停止在e。那么你可以在每对连续的节点之间运行狄克斯特拉算法。其“成本”和“路径”将由以下公式给出：

dijkstras(s, k1) + dijkstras(k1, k2) + dijkstras(k2, k3) + dijkstras(k3, e)

- Hissaan Ali

Answer 9

有一件事情没有在任何地方提到，那就是在路径中同一个顶点是否可以被访问多次。这里大部分的答案都假设同一个边可以被多次访问，但是根据问题（路径不应该重复访问同一个顶点！），我的看法是不能重复访问同一个顶点。

因此，暴力方法仍然适用，但在尝试计算路径的每个子集时，您必须删除已经使用过的顶点。

- kirsch

Answer 10

在十二个“必游”节点上使用蛮力算法如何？您可以轻松地覆盖所有可能的12个节点组合，这将为您留下一个最优电路，您可以按照它来覆盖它们。

现在，您的问题简化为从起始节点到电路找到最佳路径，然后沿着它走到覆盖它们，然后找到从那里到终点的路径。

最终路径由以下组成：

起点 -> 通往电路的路径* -> 必游节点电路 -> 通往终点的路径* -> 终点

您可以像这样找到我标记为*的路径

从起始节点开始进行A *搜索，直到电路上的每个点 对于每个电路上的点，从电路上的下一个和上一个节点到终点进行A *搜索（因为您可以按任意方向跟随电路） 最终您会得到许多搜索路径，您可以选择成本最低的路径。

通过缓存搜索，有很大的优化空间，但我认为这将生成良好的解决方案。

它并没有接近寻找最优解，因为这可能涉及在搜索中离开必游电路。

- justinhj