11

我需要通过一个无向图找到一条最短路径，该图的节点是实数（正负）加权。这些权重就像您可以通过进入节点获得或失去的资源。

路径的总成本（资源总和）不是很重要，但它必须大于 0，并且长度必须尽可能短。

例如考虑如下图：

A-start node; D-end node

A(+10)--B( 0 )--C(-5 )
     \     |    /
       \   |  /
D(-5 )--E(-5 )--F(+10)

最短路径是 AEFED

Dijkstra 的算法本身并不能解决问题，因为它不能处理负值。所以，我想到了几个解决方案：

第一个使用 Dijkstra 算法计算从每个节点到出口节点的最短路径的长度，而不考虑权重。这可以像 A* 中的某种启发式值一样使用。我不确定这个解决方案是否可行，而且成本很高。我也想过实现 Floyd–Warshall 的算法，但我不确定如何实现。

另一种解决方案是不考虑权重，用Dijkstra算法计算最短路径，如果计算出路径的资源总和小于零，则通过每个节点找到一个可以快速增加资源总和的相邻节点，并将其添加到路径（如果需要，可以多次）。如果存在足以增加资源总和但距离计算出的最短路径较远的节点，则此解决方案将不起作用。

例如：

A- start node; E- end node
A(+10)--B(-5 )--C(+40)
      \
        D(-5 )--E(-5 )

你能帮我解决这个问题吗？

编辑：如果在计算最短路径时，您到达资源总和为零的点，则该路径无效，因为如果没有更多汽油，您将无法继续。

4

4 回答 4

4

编辑：我没有很好地阅读这个问题；该问题比常规的单源最短路径问题更高级。我暂时不写这篇文章，只是为了给你提供另一种你可能会觉得有用的算法。

Bellman-Ford 算法解决了单源最短路径问题，即使存在具有负权重的边。但是，它不处理负循环（图中权重和为负的循环路径）。如果您的图表包含负循环，您可能会遇到麻烦，因为我相信这会使问题成为 NP 完全问题（因为它对应于最长的简单路径问题）。

于 2012-01-06T17:05:04.967 回答
2

这似乎不是一个优雅的解决方案，但考虑到创建循环路径的能力，我看不到解决它的方法。但我只会迭代地解决它。使用第二个示例 - 从 A 处的一个点开始，给它 A 的值。移动一个“转弯” - 现在我有两个点，一个在 B 处的值为 5，另一个在 D 处的值也为 5。再次移动 - 现在我有 4 个点要跟踪。C: 45, A: 15, A: 15, E: 0。可能是 E 处的那个可以振荡并变为有效，所以我们还不能把它扔掉。移动和累积等。当您第一次到达带有正值的结束节点时，您就完成了（尽管可能有其他等效路径在同一回合进入）

显然有问题，因为要跟踪的点数会很快增加，我假设您的实际图表比示例复杂得多。

于 2012-01-06T16:29:38.830 回答
1

我会像 Mikeb 建议的那样做：对可能的状态图进行广度优先搜索，即（位置，燃料左）-对。

使用您的示例图：

从您的示例图产生的状态图

  • 八边形：燃料耗尽
  • Boxes：由于空间原因省略了子节点

如果存在这样的路线，则可以保证以广度优先搜索此图为您提供实际到达目标的最短路线。如果没有，您将不得不在一段时间后放弃（在搜索 x 个节点之后，或者当您到达一个分数大于所有负分数总和的绝对值的节点时），因为该图可能包含无限循环。

如果您也想找到最便宜的路径（燃料方面），您必须确保在找到目标时不要立即中止，因为您可能会找到多个相同长度但成本不同的路径。

于 2012-01-07T10:46:48.817 回答
0

尝试将最小权重的绝对值（在本例中为 5）添加到所有权重。这将避免负面循环路径

当前的最短路径算法需要计算到每个节点的最短路径，因为它结合了某些节点上的解决方案，这将有助于调整其他节点中的最短路径。没有办法只为一个节点制作它。

祝你好运

于 2012-01-06T15:19:51.633 回答