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?


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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