使用没有距离的*算法

Question

编辑

我写问题的方式很混乱，所以我会改写它：

我有一个节点列表及其所有邻居节点。我正在尝试使用 a* 以最短路径从节点 X 到节点 Y。 我应该使用什么紧急措施？

Answer 1

如果只有邻域关系而没有其他，那么唯一可用的启发式函数是 h(X,Y) = 0。在这种情况下，A* 本质上变成了 Dijkstra 搜索。

请注意，在此设置中，您的成本函数也会降级为 c(x,y) = 1，其中 x 和 y 是邻居。

如果您的目标 Y 始终相同，或者至少在多次搜索中保持相同，那么您可以通过在没有明确目标的 Y 处启动 Dijkstra 搜索并记录成本来预先计算每个节点 X 到目标的跳数由 Dijkstra 计算的每个节点的 g(Y,X)。这个成本将成为你理想的启发式 h(X,Y)。