performance - 基于BFS的寻路算法的运行时间

Question

我提出了一种基于 BFS 的寻路算法，旨在替代 Diskjstra 的（老实说，我怀疑其他人过去曾提出过它，但我在任何地方都找不到任何关于它的在线提及）。我试图弄清楚运行时间是多少，但我和我的朋友们正在争论它，并且无法得出一个明确的答案。这是 Go 中算法的描述和实现的链接： https ://github.com/joshlf13/bfspath

我的印象是运行时间是 e + e^2 + e^4 + ... + e^2d 其中 e 是每个顶点的平均边数，d 是最终最短路径的距离（给 O (e^2d))。问题是，这取决于算法的结果，正如我的朋友指出的那样，它不应该包含在运行时间的考虑中。

我的推理是这样的：BFS 的每次传递都会增加 e 的倍数所考虑的顶点数量。此外，每次考虑一个顶点时，它都是 e 操作。因此，每次传递都是 v（传递中的顶点数）乘以 e。如果 v 为 1，则 e 则为 e^2，以此类推，v*e 为 e + e^2 + e^4，以此类推。

另一种方法是根据考虑的边数来考虑运行时间。一条长度为 N 的边需要 N 次操作。因此，对于具有 E 条边且平均边长为 N 的图，它是 O(N*E)。但是，这仅适用于在算法运行期间考虑的图形部分，并且该子集的大小不会随起点和终点之间的距离线性缩放，这使得真正考虑 O() 变得困难.

想法……？

Answer 1

因此，您的算法最基本的问题是，当边具有实值权重/长度时，它不能保证正确答案。除非您完全准备好拥有计算机上可用的最小浮点值的“单位长度”（提示：它非常小），否则您将无法分解每条边。

因此，您的算法甚至只能在可以简化为统一网格的图形上返回正确答案，在这些网格中，您在任何给定时间只能水平或垂直移动。

至于分析运行时，你的朋友是绝对正确的。“真正考虑 O()”并没有什么“困难”。您的算法是复杂性理论中所谓的伪多项式时间。这真正意味着它的输入大小是指数的，但值是多项式的。特别是，它是 O(NE + V)，其中 N 是图中所有边中最大的边权重。

图上的伪多边形算法 / 太慢 / 对于任何现实世界的使用，即使你可以保证整数边长。你真的只能在统一长度的网格上使用它，人们/已经/在统一长度的网格上使用 BFS；这不是“特殊算法”，而是 BFS。