algorithm - 是否可以使用 A* 搜索非网格图

Question

我知道 A* 是寻找最短路径的最佳算法，但我看不出任何启发式算法如何适用于非格图？这让我想知道 A* 实际上是否能够用于无向图或有向图。如果 A* 能够做到这一点，那么可以使用什么样的启发式算法呢？如果不是 A*，那么在有向或无向非点阵图上计算最短路径的当前最快算法是什么？如果需要更多信息，请发表评论。

Answer 1

可能是的，但 A* 是一种流行的算法，用于在类似图形的网格中查找最短路径。对于一般的图形，还有许多其他算法可以更好地匹配您的情况。使用哪一个取决于您的设置。

如果您计划执行单源最短路径 (SSSP)，您可以在其中尝试找到从一个节点到另一个节点的最短路径并且您的图表未加权，您可以使用呼吸优先搜索。该算法的双向版本在实践中表现良好。如果您执行 SSSP 并且您的图表是加权的，Dijkstra 算法是一个常见的选择，也可以使用双向版本。对于所有对最短路径，其他算法(如 Floyd-Warshall 或 Johnson 算法)也很有用。

如果您想使用启发式方法并在搜索完成之前估计距离，您可以进行预计算，这对上述每种算法都适用。一些例子:

• 快捷方式计算(ARC-Flags、SHARC、KFlags)
• hub identification (also transite nodes): 预先计算所有 hub 节点之间的距离(在非动态图中只需要做一次)，找到下一个 hub 的 source 和 sink，例如与迪杰斯特拉。将集线器和源之间的距离加到下一个集线器和汇到下一个集线器
• 结构化查找表，例如集线器之间的距离以及特定距离内集线器与节点之间的距离。预计算后，您无需再次遍历图形，而您的最短路径计算是多次查找。这会导致高内存消耗但性能强劲。您可以使用距离计算的上近似值来调整内存。

我强烈建议您确定您的确切案例，并对非常适合该案例的图形算法进行一些研究。数十个应用领域在最短路径方面做了大量研究。