Best-first Search - Algorithm

Algorithm

OPEN = while OPEN is not empty or until a goal is found do 1. Remove the best node from OPEN, call it n. 2. If n is the goal state, backtrace path to n (through recorded parents) and return path. 3. Create n's successors. 4. Evaluate each successor, add it to OPEN, and record its parent. done

Note that this version of the algorithm is not complete, i.e. it does not always find a possible path between two nodes even if there is one. For example, it gets stuck in a loop if it arrives at a dead end, that is a node with the only successor being its parent. It would then go back to its parent, add the dead-end successor to the OPEN list again, and so on.

The following version extends the algorithm to use an additional CLOSED list, containing all nodes that have been evaluated and will not be looked at again. As this will avoid any node being evaluated twice, it is not subject to infinite loops.

OPEN = CLOSED = while OPEN is not empty do 1. Remove the best node from OPEN, call it n, add it to CLOSED. 2. If n is the goal state, backtrace path to n (through recorded parents) and return path. 3. Create n's successors. 4. For each successor do: a. If it is not in CLOSED: evaluate it, add it to OPEN, and record its parent. b. Otherwise: change recorded parent if this new path is better than previous one. done

Also note that the given pseudo code of both versions just terminates when no path is found. An actual implementation would of course require special handling of this case.