Best First Search

In this section ,we discuss a new method, best-first search, which is a way of combining the advantages of both Depth and Breadth First Search

OR Graph

We will call a graph as an OR - graph,since each of its branches represents alternative problem solving path.The Best First Search, selects the most promising of the nodes we have generated so far.This can be achieved by applying appropriate Heuristic function to each of them.

Heuristic function:
f(n) = h(n) 

where,
h(n) - estimated straight line distance from node n to goal

To implement the graph search procedure ,we will need to use two list of nodes.

OPEN- nodes that have been generated but have not been visited yet

Closed - nodes that have been already visited

Algorithm: 

1. The 1^st step is to define the OPEN list with a single node, the starting node.
2. The 2^nd step is to check whether or not OPEN is empty. If it is empty, then the algorithm returns failure and exits.
3. The 3^rd step is to remove the node with the best score, n, from OPEN and place it in CLOSED.
4. The 4^th step “expands” the node n, where expansion is the identification of successor nodes of n.
5. The 5^th step then checks each of the successor nodes to see whether or 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, proceeds to the sixth step.
6. In 6^th 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.
7. Finally, the 7^th step establishes a looping structure by sending the algorithm back to the 2^nd step. This loop will only be broken if the algorithm returns success in step 5 or failure in step 2.

 
 Consider the following graph as an example,

 

S: Initial state, G: goal.

Table shows the heuristic estimates:

node	h(n)	node	h(n)	node	h(n)
A	11	E	4	I,J	3
B	5	F	2	S	15
C,D	9	H	7	G	0

 

Initialization

S (15)

Expand the nodes of S and add S into CLOSED

Iteration 1:

1)Add the successors of node s into OPEN and compute f(n)

2)Choose the most promising node (min h(n))

3)Remove the node from OPEN and add it into the CLOSED

Iteration 2:

1)Add the successors of node B  into OPEN and compute f(n)

2)Choose the most promising node (min h(n))

3)Remove the node from OPEN and add it into the CLOSED

 

Iteration 3:

1)Add the successors of node F  into OPEN and compute f(n)

2)Choose the most promising node (min h(n))

3)Remove the node from OPEN and add it into the CLOSED

The shortest path form S -> G is S -> B -> F -> G
Total cost:

1+3+1=4