2

我们可以假设所有边的权重都是正的，并且您可以在 O(1) 时间内枚举从顶点向外引导的边，以及向内引导的边。

例如，您可以执行 Dijkstra 遍历（或 A*，具有可接受的启发式）并标记每个顶点从起点到终点的距离，然后在这些标记上反向递归，因为它们描述了最佳路径上的可能前任. 也就是说，对于每个可能的前任，如果标记距离之间的差异等于连接它们的边的权重，您可以确定它是否在贪婪的最佳路径上找到。

在查看可能的前辈时，传入边的成本加上到每个顶点的最佳距离之间的差异等于在解决方案中包含这条边所导致的最优性损失（最优路径上的边为零）。所以也许问题变成了：如何最好地扩展它以产生所有可能的路径，通过递减最优性排序？有没有一种干净的方法来对这种元图执行最佳优先遍历？

这似乎是寻求有用解决方案的正确方向。也许需要记住的有用的事情是，如果您到目前为止探索的路径部分可能是至少x次优的解决方案的一部分，则只需沿着最后访问的x距离进行循环检查（任何x次优的路径不可能包含比x更长的循环）。

有没有更有效的方法？

作为一个额外的问题，是否也可以在具有负边权重的图（已知大小）上执行此操作？如果引入负循环会变得更加困难吗？（请记住，由于我们只在寻找非循环路径，这并不一定意味着最优解会消失。）

4

2 回答 2

0

归功于 nm：关于K 最短路径路由的 Wikipedia 文章描述了各种现代方法，包括用于泛化 Dijkstra 的伪代码，以及 2011 年关于 K* 的论文的链接，该论文也使用了启发式算法。

于 2016-11-23T05:12:20.523 回答
0

对于 N 个节点的完整图，大小为 (N-2)！从节点 A 到节点 B 的可能非循环路径。想想看……这应该是一个巨大的数字，如果你只需要 K（足够大，但数量合理）的路径，你最好在评论中提到 K-shortest_path。

如果您可以管理足够的内存来保存所有可能的方式，那么有一个明显的解决方案 - 生成所有可能的方式并按重量排序。如果没有，您必须将答案转储到磁盘然后收集它们。

您可以使用修改后的 BFS 枚举所有可能的方式 - “已访问”数组被传递给递归调用，而不是全局布尔数组。当您访问目的地时，将其添加到全局解决方案地图（键 - 权重，值 - 具有此权重的路径列表）。

如果您无法将所有路径保存在内存中，则可以将它们转储到临时文件中。天真的解决方案：打开名称为 0 的文件，最多填充 10 位数字 - 或任何适合您需要的 - 重量，并为路径添加一行。收集完所有路径后，以适当的顺序读取文件并形成最终结果。

注意如果可以的话，最好不要打开/附加/关闭文件。例如，当路径总数超过某个限制时，您可以收集地图中的路径并仅转储最长的列表。

于 2016-11-21T14:45:34.400 回答