A* 是否从边缘以增量成本顺序(如 Dijkstra 的)弹出节点以实现一致的启发式?
Does A* pop node in incremental cost order (like Dijkstra's) from fringe for consistent heuristics?
如果启发式从不高估从 n 到达目标节点的真实成本,则它是 可接受的。
如果启发式一致,则 n 的启发式值永远不会大于其后继者的成本。
对于可接受的启发式算法,虽然它可能已经有一些结果,但后来弹出的节点可以更新目标节点的成本,这就是我们需要运行算法的方式,只要边缘中的其他节点没有更少值然后当前发现成本。对于一致的启发式,这种情况是否有所不同?
对于图的每条边 (x, y),一致的启发式还满足 h(x) ≤ d(x, y) + h(y),其中 d 是边距。
当第一次在 A* 中扩展节点时启发式是一致的,我们找到了到该节点的最佳路径。每个节点只会扩容一次,按照cost的顺序
如果启发式从不高估从 n 到达目标节点的真实成本,则它是 可接受的。
如果启发式一致,则 n 的启发式值永远不会大于其后继者的成本。
对于可接受的启发式算法,虽然它可能已经有一些结果,但后来弹出的节点可以更新目标节点的成本,这就是我们需要运行算法的方式,只要边缘中的其他节点没有更少值然后当前发现成本。对于一致的启发式,这种情况是否有所不同?
对于图的每条边 (x, y),一致的启发式还满足 h(x) ≤ d(x, y) + h(y),其中 d 是边距。
当第一次在 A* 中扩展节点时启发式是一致的,我们找到了到该节点的最佳路径。每个节点只会扩容一次,按照cost的顺序