algorithm - A*算法重新打开顶点

Question

考虑以下用于A* 搜索算法 的伪代码:

A*(G, s, h)
  for each vertex u in V
    d[u] := f[u] := infinity
    color[u] := WHITE
    p[u] := u
  end for
  color[s] := GRAY
  d[s] := 0
  f[s] := h(s)
  INSERT(Q, s)
  while (Q != Ø)
    u := EXTRACT-MIN(Q)
    for each vertex v in Adj[u]
      if (w(u,v) + d[u] < d[v])
        d[v] := w(u,v) + d[u]
    f[v] := d[v] + h(v)
    p[v] := u
    if (color[v] = WHITE)
      color[v] := GRAY
      INSERT(Q, v)
    else if (color[v] = BLACK)
      color[v] := GRAY
      INSERT(Q, v)
    end if
      else
        ...
    end for
    color[u] := BLACK
  end while

现在 - 如果我们想找到一条从源顶点 (s) 到某个目标顶点(我们将其命名为 d)的路径，我是否理解正确？ ) 然后我们可以在 u := EXTRACT-MIN(Q) 语句之后简单地添加一个检查，如下所示:

    u := EXTRACT-MIN(Q)
    if (u = d) RETURN PATH

如果我们不需要重新打开顶点，这显然是正确的(else if (color[v] = BLACK)，但是它是否正确 以防我们必须重新打开它们(例如，如果启发式函数不是单调的)？

Answer 1

这是正确的。如果您找到了目标节点，那么您将永远不必重新打开任何东西；你可以只返回路径。根据 A* 算法的属性(包括可接受的启发式算法)，您第一次将目标节点从优先级队列中弹出时，您将拥有到它的最短路径。