当前位置: 动力学知识库 > 问答 > 编程问答 >

search - A* algorithm reopen vertices

问题描述:

Consider the following pseudocode for the 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

Now - do I understand correctly that if we want to find a path from the source vertex (s) to some destination vertex (let's name it d) then we can simply add a check right after the u := EXTRACT-MIN(Q) statement like this:

 u := EXTRACT-MIN(Q)

if (u = d) RETURN PATH

This is obviously correct in case we don't need to reopen vertices (else if (color[v] = BLACK), but is it correct in case we have to reopen them (for example, if the heuristic function is not monotonic)?

网友答案:

This is correct. If you find the destination node, then you'll never have to reopen anything; you can just return the path. By the properties of the A* algorithm (including an admissible heuristic), the first time you pop the destination node off the priority queue, you'll have a shortest path to it.

分享给朋友:
您可能感兴趣的文章:
随机阅读: