A * алгоритм открывает вершины

Question

Рассмотрим следующий псевдокод для A* search algorithm:

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 * (включая допустимую эвристику), при первом извлечении узла назначения из очереди с приоритетами у вас будет кратчайший путь к нему.