Write a short note on Best first search ?

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 consists of a path traced backwards from the goal to the start node. Otherwise, the algorithm proceeds to the sixth step. For every successor node, the algorithm applies the evaluation function, f, to it, then checks to see if the node has been in either OPEN or CLOSED. If the node has not been in either, it gets added to OPEN. Finally, the seventh step establishes a looping structure by sending the algorithm back to the second step. This loop will only be broken if the algorithm returns success in step five or failure in step two.

The algorithm is represented here in pseudo-code:

1. Define a list, OPEN, consisting solely of a single node, the start node, s.

2. IF the list is empty, return failure.

3. Remove from the list the node n with the best score (the node where f is the minimum), and move it to a list, CLOSED.

4. Expand node n.

5. IF any successor to n is the goal node, return success and the solution (by tracing the path from the goal node to s).

6. FOR each successor node:

a) apply the evaluation function, f, to the node.

b) IF the node has not been in either list, add it to OPEN.

7. GOTO 2.

APPLICATIONS

Best-first search and its more advanced variants have been used in such applications as games and web crawlers. In a web crawler, each web page is treated as a node, and all the hyperlinks on the page are treated as unvisited successor nodes. A crawler that uses best-first search generally uses an evaluation function that assigns priority to links based on how closely the contents of their parent page resemble the search query . In games, best-first search may be used as a path-finding algorithm for game characters. For example, it could be used by an enemy agent to find the location of the player in the game world. Some games divide up the terrain into “tiles” which can either be blocked or unblocked. In such cases, the search algorithm treats each tile as a node, with the neighboring unblocked tiles being successor nodes, and the goal node being the destination tile.