1

我有一个无环有向图，有一个开始顶点和一个结束顶点，中间有一些未知数量的顶点。路径从起始顶点开始，在结束顶点结束。已知起始顶点和结束顶点之间的任意路径上的顶点数<100，但可能的顶点数可能非常大。每个顶点都有一个分配给它的成本，路径的成本是中间顶点成本的总和。有没有办法使用随机游走或任何其他方式（这是为了避免探索所有顶点）来找到成本最高（或接近最高）的路径？

4

1 回答 1

2

这个问题在 Geekviewpoint.com 上得到了详细的解释。它增强了 Dijkstra 的算法。http://www.geekviewpoint.com/java/graph/dijkstra_constrained

编辑：占每条路径之间的 100 个顶点。

最初你的问题是在开始和结束顶点之间有 100 条路径。但是通过您的更正，它实际上是路径上的 100 个顶点。在这种情况下，使用 DFS 可以直接进行优化。

当您尝试组装路径时，请跟踪您看到的顶点数。如果数字达到 99 并且没有从头到尾链接，请中止该路径并尝试另一个单元，如果存在，您会得到答案。您需要修改的算法是用于循环检测的 DFS。任何算法教科书都会有其中之一。由于您还需要在找到的路径中选择最佳路径，因此您还应该查看http://www.geekviewpoint.com/java/graph/count_paths。

我不知道我是否应该告诉您如何做显而易见的事情，但是您将跟踪您找到的过去路径，类似于您如何找到数组中的最大元素。代码不难，你只要结合几个小想法：

  • DFS（类似于循环检测和计数路径，两者重叠）

  • 跟踪你见过的最佳路径：一个入口地图，其中的想法是地图，如果你找到更短的路径，你会不断替换它。

于 2013-01-26T19:02:52.183 回答