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 (Menczer, Pant, Ruiz, and Srinivasan, 2001). 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 neighbouring unblocked tiles being successor
nodes, and the goal node being the destination tile (Koenig, 2004).

Q
http://rohitwagdarikar.blogspot.in

ReplyDeleteprogram of Best First Search