Best First Search & A-Star Algorithm

BEST-FIRST SEARCH
 Combines the advantages of both DFS and BFS into a single method.
 Depth-first search: not all competing branches having to be expanded.
 Breadth-first search: not getting trapped on dead-end paths.

 Combining the two is to follow a single path at a time, but switch paths
whenever some competing path look more promising than the current one.
1
BEST-FIRST SEARCH
 At each step of the BFS search process, we select the most
promising of the nodes we have generated so far.
 This is done by applying an appropriate heuristic function to each of

them.
 We then expand the chosen node by using the rules to generate its
successors
 This is called OR-graph, since each of its branches represents an

alternative problem solving path
2
BEST-FIRST SEARCH
A A A
B C D B C D
3 5 1 3 5
E F
4 6
A A
B C D B C D
5 5
G H E F G H E F
6 5 4 6 6 5 6
I J
3
2 1
BEST FIRST SEARCH VS HILL CLIMBING
 Similar to Steepest ascent hill climbing with two exceptions:
 In hill climbing, one move is selected and all the others are
rejected, never to be reconsidered. In BFS, one move is
selected, but the others are kept around so that they can be
revisited later if the selected path becomes less promising
 The best available state is selected in the BFS, even if that
state has a value that is lower than the value of the state that
was just explored. Whereas in hill climbing the progress stop
if there are no better successor nodes.
4
BEST-FIRST SEARCH
 OPEN: nodes that have been generated, but have not examined.
This is organized as a priority queue.
 CLOSED: nodes that have already been examined.

Whenever a new node is generated, check whether it has been generated
before.
5
Algorithm : Best-First Search
1. Start with OPEN containing just the initial state.
2. Until a goal is found or there are no nodes left on OPEN do:
(a) Pick them best node on OPEN.

(b) Generate its successors.
(c) For each successor do:
(i) If it has not been generated before, evaluate it, add it to OPEN, and
record its parent.
(ii) If it has been generated before, change the parent if this new path
is better than the previous one. In that case, update the cost of
getting to this node and to any successors that this node may
already, have.
54
7
A* ALGORITHM
 Best First Search is a simplification of A* Algorithm
 Algorithm uses:
 f’: Heuristic function that estimates the merits of each node we
generate. This is sum of two components, g and h’
 f’ represents an estimate of the cost of getting from the initial state to a
goal state along with the path that generated the current node.
 g : The function g is a measure of the cost of getting from initial
state to the current node.
 h’ : The function h’ is an estimate of the additional cost of
getting from the current node to a goal state.
 OPEN
 CLOSED
8
ALGORITHM A*
 Algorithm A* (Hart et al., 1968):
f(n) = g(n) + h(n)
h(n) = cost of the cheapest path from node n to a goal state.
g(n) = cost of the cheapest path from the initial state to node n.
 Algorithm A*:
f*(n) = g*(n) + h*(n)
h*(n) (heuristic factor) = estimate of h(n).
g*(n) (depth factor) = approximation of g(n) found by A* so far.
9
A* ALGORITHM
1. Start with OPEN containing only initial node. Set that node’s g
value to 0, its h’ value to whatever it is, and its f’ value to h’+0
or h’. Set CLOSED to empty list.
2. Until a goal node is found, repeat the following procedure:

1. If there are no nodes on OPEN, report failure.
2. Otherwise pick the node on OPEN with the lowest f’ value.
Call it BESTNODE. Remove it from OPEN. Place it in
CLOSED.
1. See if the BESTNODE is a goal state. If so exit and report
a solution.
2. Otherwise, generate the successors of BESTNODE but do
not set the BESTNODE to point to them yet.
A* ALGORITHM ( CONTD….)
 For each of the SUCCESSOR, do the following:
a. Set SUCCESSOR to point back to BESTNODE. These backwards

links will make it possible to recover the path once a solution is
found.
a. Compute g(SUCCESSOR) = g(BESTNODE) + the cost of getting

from BESTNODE to SUCCESSOR
a. See if SUCCESSOR is the same as any node on OPEN. If so call

the node OLD.
a. If SUCCESSOR was not on OPEN, see if it is on CLOSED. If so, call

the node on CLOSED OLD and add OLD to the list of BESTNODE’s
successors.
a. If SUCCESSOR was not already on either OPEN or CLOSED, then

put it on OPEN and add it to the list of BESTNODE’s successors.
Compute f’(SUCCESSOR) = g(SUCCESSOR) + h’(SUCCESSOR)
OBSERVATIONS ABOUT A*
 Role of g function: This lets us choose which node to expand next on the
basis of not only of how good the node itself looks, but also on the basis of
how good the path to the node was.
 h, the distance of a node to the goal. If h’ is a perfect estimator of h, then
A* will converge immediately to the goal with no search.
55
56
16

Best First Search & A-Star Algorithm

Uploaded by

Copyright:

Available Formats

Best First Search & A-Star Algorithm

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Best First Search & A-Star Algorithm

Uploaded by

Copyright:

Available Formats

BEST-FIRST SEARCH

 Depth-first search: not all competing branches having to be expanded.

 Breadth-first search: not getting trapped on dead-end paths.

 This is done by applying an appropriate heuristic function to each of

 This is called OR-graph, since each of its branches represents an

 CLOSED: nodes that have already been examined.

2. Until a goal is found or there are no nodes left on OPEN do:

(a) Pick them best node on OPEN.

f(n) = g(n) + h(n)

h(n) = cost of the cheapest path from node n to a goal state.

f*(n) = g*(n) + h*(n)

h*(n) (heuristic factor) = estimate of h(n).

g*(n) (depth factor) = approximation of g(n) found by A* so far.

2. Until a goal node is found, repeat the following procedure:

a. Set SUCCESSOR to point back to BESTNODE. These backwards

a. Compute g(SUCCESSOR) = g(BESTNODE) + the cost of getting

a. See if SUCCESSOR is the same as any node on OPEN. If so call

a. If SUCCESSOR was not on OPEN, see if it is on CLOSED. If so, call

a. If SUCCESSOR was not already on either OPEN or CLOSED, then

You might also like

f(n) = g(n) + h*(n)

g(n) (depth factor) = approximation of g(n) found by A so far.