2
$\begingroup$

I've got a question regarding the A* search algorithm's implementation.

According to Wikipedia, one has to use a priority queue for retrieving the next node with the lowest f value, is it possible to skip to a node that is not a direct descendant of the current node?

For example:
Say we start with node S (set f=0), then add nodes A (with f=5) and B (with f=3).
B is obviously picked, then we add its descendant C (with f=4). Since the priority queue holds A(5) and C(4), C is now picked.
With C we encounter two additional nodes, D (with f=7) and E (with f=8).
Clearly A has the lowest f value in the queue, which means it should be picked, however, it does not have a direct connection with C.

Is it possible to continue developing A even though it is not a direct descendant of C? or is it that D should be picked to develop.
Using a naive priority queue would choose A, is that fine?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Yes, you move on with A. You always pick the element in the fringe that minimizes $h(x) = f(x) + g(x)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.