Best-first search, rather than plunging as deep as possible into the tree (as in depth-first search ), or traversing each level of the tree in succession (as in breadth-first search ), uses a heuristic to decide at each stage which is the best place to continue the search. Best-first search in its most basic form consists of the following algorithm (adapted from Pearl, 1984): The first step is to define the OPEN list with a single node, the starting node. The second step is to check whether or not OPEN is empty. If it is empty, then the algorithm returns failure and exits. The third step is to remove the node with the best score, n, from OPEN and place it in CLOSED. The fourth step “expands” the node n, where expansion is the identification of successor nodes of n. The fifth step then checks each of the successor nodes to see whether of not one of them is the goal node. If any successor is the goal node, the algorithm returns success and the solution, which c...