问题：我有一个大的点集合。每个点都有一个列表，其中包含对其他点的参考以及计算和存储的距离。我需要确定从起点开始穿过特定数量的点到达任何目的地的最短路径。
例如：我正在度假，我住在一个特定的城市。我要进行单向旅行，去看任何四个城市，并且我想走最短的路线。我不能多次访问同一个城市。
当前解决方案：目前，我只是手动迭代每个可能性并存储最短路径。这种方法能够解决问题，但效率感觉不高。此外，这个问题最终将扩展到搜索从多个起点到多个终点，因此我认为搜索空间可能会爆炸。
什么是更好的寻找最短路径的方法？
算法优化 - 多点之间的最短路径
11
- Chris Douglass
6
这是一个有向图还是无向图？我看不出来。 - James Jones
2这里的一些答案（TSP，Floyd-Warshall，Breadth-First，Branch and Bound）是从对这个问题存在着极不一致和矛盾的解释中得出的，因此我倾向于认为这个问题在表述上并不十分清晰。 - Juliet
让我简要地重新表述一下：比如说我正在度假，我待在一个城市。我想要去看任意四个城市，并且希望旅行的距离最短。我不能重复游览同一个城市。 - Chris Douglass
1你最近的编辑完全改变了我对你问题的理解。 - James Jones
1哦，我的天啊。这使得基于Floyd-Warshall的解决方案变得如此无效，以至于它们看起来相当可笑 :) - P Shved
抱歉！这是我第一次在这里发布... :( - Chris Douglass
7个回答
7
回答更新后的帖子，你检查每种可能性的解决方案是最优的（至少目前没有人发现更好的算法）。是的，这是旅行商问题，其本质不是触及每个城市，而是只触及每个城市一次。如果您不想搜索可能的最佳解决方案，可以使用启发式方法，这些方法工作速度更快，但允许与理想解决方案存在有限差异。
对于未来的回答者：弗洛伊德-沃舍尔算法和所有类似弗洛伊德的变体在这里不适用。
对于未来的回答者：弗洛伊德-沃舍尔算法和所有类似弗洛伊德的变体在这里不适用。
- P Shved
5
5有趣的事实：对于N ≤ 8，O(N^5) > O(N!)。 :) - Juliet
谢谢。我已经优化了一些，通过找到最短的单个路线直达全部路径，然后向上移动一级并搜索，然后再向上移动一级（等等）。我猜那是深度优先搜索？ - Chris Douglass
这可以称为深度优先遍历，而不是搜索。搜索旨在访问每个节点，而您的算法旨在访问每条路径，因此更加昂贵。 - P Shved
2目前没有已知的多项式时间算法。然而，这并不意味着检查每种可能性是最优的。对于旅行商问题和相关问题，有相当复杂的算法可以解决例如包含几千个城市的大规模问题。 - Accipitridae
Pavel使用"最优"这个术语是指它将在任何数据集上找到最佳解决方案（无论运行时复杂度如何）。 - Joe Holloway
3
一般来说，你应该严格限制不良变体...我认为你应该使用分支定界法的一些变体方法。 http://en.wikipedia.org/wiki/Branch_and_bound
- Max
1
是的。这是一道树搜索优化问题，因此可以采用分支定界方法进行求解。这可以通过广度优先或深度优先实现。 - Mike Dunlavey
1
这听起来像旅行推销员问题？一种解决方案是使用优化技术，如进化算法。目前，您正在进行详尽的搜索，这将很快变得非常缓慢。但我认为这基本上是一个旅行推销员问题，已经有几十年甚至几个世纪了，因此有几种可能的攻击方式。谷歌是你的朋友。
- zenna
3
1它不是TSP，因为你可以多次传入同一点。 - Shay Erlichmen
我认为TSP涉及到知道需要触及的每个点？在我的情况下，没有特定的点需要包括，只需要沿着最短路径从起点到达任何点。 - Chris Douglass
1@Shay：TSP 有很多种，包括允许用户多次访问同一顶点的那些。 - Juliet
1
也许这就是原帖作者所说的“手动迭代每个可能性并存储最短路径”的意思，但我想明确表达一下似乎是基线解决方案的内容。
假设您已经有了一个两点最短路径算法——对于各种类型的图形，这都有经典的解决方案。假设所有距离都是非负的，并且d(A->B->C) = d(A->B) + d(B->C)。
关键在于路径从S开始，穿过中间城市“abcd”之一，并以E结束：
例如SabcdE、SacbdE等。
只有4个中间城市，您可以枚举所有24个排列。对于每个排列，使用最短的两点算法计算从头到尾的路径及其总距离。
然后，给定起点和终点，有12种可能性连接到abcd之一，对于内部有两种可能性。您已经计算了这些距离，因此需要添加从S到头部和从尾部到E的距离。选择最小值。因此，一旦您为固定的内部城市集预先计算了中间距离，您需要为任何一对起点和终点执行12个两点最短路径问题。
假设您已经有了一个两点最短路径算法——对于各种类型的图形，这都有经典的解决方案。假设所有距离都是非负的，并且d(A->B->C) = d(A->B) + d(B->C)。
关键在于路径从S开始，穿过中间城市“abcd”之一，并以E结束：
例如SabcdE、SacbdE等。
只有4个中间城市，您可以枚举所有24个排列。对于每个排列，使用最短的两点算法计算从头到尾的路径及其总距离。
然后，给定起点和终点，有12种可能性连接到abcd之一，对于内部有两种可能性。您已经计算了这些距离，因此需要添加从S到头部和从尾部到E的距离。选择最小值。因此，一旦您为固定的内部城市集预先计算了中间距离，您需要为任何一对起点和终点执行12个两点最短路径问题。
随着中间城市数量的增加，这显然会导致规模扩大。除非对图形结构施加更严格的限制（这是在物理欧几里得空间中吗？三角不等式？），否则我不清楚它是否能做得更好。
我的思考例子：假设所有城市之间的中间距离都是O(1)。在没有对图形施加任何限制的情况下，从S到任何中间城市的距离可能为1000，除了一个城市的距离为1。尾部也是一样。因此，您可以强制访问第一个城市成为任何事情。现在，向下走一层，将第一个城市作为“起点”。应用相同的论点：通过操纵图中的距离，您可以使最佳路径经过以下任何一个城市。
因此，似乎在没有额外假设的情况下无法改善复杂性。
- Matt Kennel
1
这是一种非常普遍和实时的情况，任何人都可能遇到。Google地图用户界面会按照您在目的地列表中添加的顺序给出路径，但并不提供最优路径，尽管他们自己的Google地图API可以提供解决方案。
Google地图API为此提供了解决方案。在请求中寻找路径时，您需要提供标志“optimizeWaypoints：true，”。请求将如下所示。
Google地图API为此提供了解决方案。在请求中寻找路径时，您需要提供标志“optimizeWaypoints：true，”。请求将如下所示。
var request = {
origin: start,
destination: end,
waypoints: waypts,
optimizeWaypoints: true,
travelMode: google.maps.TravelMode.DRIVING
};
您可以在查看源代码时看到该实用程序的全部代码，因为该实用程序完全由JavaScript和HTML开发。
希望这能帮到您。
- Abhishek Gahlout
1
你的网站挂了，伙计，链接也是。 - sam
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接