基于BFS的路径寻找算法的运行时间

Question

我想出了一个基于BFS的路径寻找算法，作为Diskjstra的替代方案（老实说，我怀疑其他人在过去提出过，但我在任何地方都找不到任何提及）。我试图找出运行时间是什么，但我和我的朋友正在辩论它，并没有能够拿出明确的答案。这里有一个链接，描述和执行算法在Go中： https://github.com/joshlf13/bfspath

我感觉运行时间是e + e^2 + e^4 + ... + e^2d其中e是每个顶点的平均边数和d是最终最短路径的距离（给出O（e^2d））。问题是，这依赖于算法的结果，正如我的朋友指出的那样，不应该考虑运行时间。我的推理是这样的：BFS的每次通过增加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。