algorithm - 我可以在一致的启发式/统一成本/Dijkstra 搜索下修改标准 A*(A 星)，以便它不必更新边界吗？

Question

标准方法如下:AI:一种现代方法

function UNIFORM-COST-SEARCH

node <- INITIAL-STATE
frontier <- priority queue ordered by PATH-COST, with node as the only element
explored <- an empty set
loop do
    if frontier is empty then return failure
    node <- POP frontier  /* chooses the lowest-cost node in frontier */
    if GOAL-TEST(node) then return SOLUTION(node)
    add node to explored
    for each action in ACTIONS(node) do
        child <- CHILD-NODE(problem, node, action)
        if child is not in explored or frontier then
            frontier.INSERT(child)
        else if child is in frontier with higher PATH-COST then
            replace that frontier node with child

这里这一步实现起来比较复杂，普通的优先级队列无法有效地更新某个元素的优先级。

        else if child is in frontier with higher PATH-COST then
            replace that frontier node with child

我正在考虑按以下方式修改算法:

function UNIFORM-COST-SEARCH-Modified

node <- INITIAL-STATE
frontier <- priority queue ordered by PATH-COST, with node as the only element
explored <- an empty set
loop do
    if frontier is empty then return failure
    node <- POP frontier  /* chooses the lowest-cost node in frontier */
  > if node is in explored then continue
    if GOAL-TEST(node) then return SOLUTION(node)
    add node to explored
    for each action in ACTIONS(node) do
        child <- CHILD-NODE(problem, node, action)
  >     if child is not in explored then
            frontier.INSERT(child)

所以我不关心边界是否包含重复状态。我只扩展边界中重复状态中的第一个。由于路径成本是一致的，并且边界是使用优先级队列实现的，因此忽略其他具有更高成本的重复状态是无害的。

合理吗？

更新

抱歉，我忘了说我对一致性启发式案例特别感兴趣。

Answer 1

思路在原理上是正确的，但是有一个bug:

  > if node is in explored then continue

如果启发式函数不是单调的(与可接受性不矛盾)，此行可能会导致失败。

如果新成本比之前找到的更好，A* 允许重新探索节点。这些情况发生在非单调启发式函数中。

只有当新成本比 explored 中附加到顶点的成本“更大”时，您才应该继续，而不是如果它只存在于那里。

---

编辑:(基于评论和问题编辑的问题)

对于 h=0，A* 实际上会衰减到 Dijkstra 算法中，并且由于 Dijkstra 算法从不需要修改已经“探索过”的节点(当然假设权重为正)- 该算法对于这些案例。

一般来说，在单调启发式函数中不会发生重新访问已经访问过的节点，所以这不是问题，并且该方法对于这些情况是正确的 - 但请注意不要将其应用于非单调启发式函数。