Page 53 - DCAP506_ARTIFICIAL_INTELLIGENCE

Unit 4: Heuristic Search Techniques

Notes

Notes Hill climbing turns out to be incompetent in large problem spaces, and when
combinatorial explosion appears. But it is a functional when combined with other methods.

Task Illustrate the problems that occur in hill climbing technique.
Self Assessment

Fill in the blanks:

5. In .............................. the test function is offered with a heuristic function which offers an
estimate of how close a known state is to goal state.
6. A “.............................. ’’ which is a flat area of the search space, in which adjacent states have
the similar value.
7. A “.............................. ” which is an area in the search that is superior than the surrounding
areas, but can not be looked in a simple move.

4.4 Best First Search

The general strategy of heuristic search is best-first search (BeFS)
 a node is chosen for expansion based on an evaluation function, f(n).

 expand the node with the lowest “evaluation” – the one that “appears” to be best as per the
evaluation function
 algorithm uses a heuristic function, h(n):
h(n) = estimated cost of cheapest path from node n to a goal node.

!
Caution Evaluation gauges the distance to the goal.
Best First Search is a amalgamation of depth first and breadth first searches.

Depth first is good since a solution can be located without calculating all nodes and breadth first
is good since it does not get trapped in dead ends. The best first search permits us to switch
among paths thus gaining the advantage of both approaches. At every step the most promising
node is selected. If one of the nodes selected produces nodes that are less promising it is probable
to select another at the similar level and in effect the search alters from depth to breadth. If on
analysis these are no better then this beforehand unexpanded node and branch is not forgotten
and the search technique reverts to the descendants of the first option and proceeds, backtracking
as it were.
This process is very alike to steepest ascent, but in hill climbing once a move is selected and the
others are rejected the others are not at all reconsidered even as in best first they are saved to
allow revisits if an impasse appears on the evident best path. Also the best obtainable state is
chosen in best first even its value is inferior than the value of the node just discovered while in
hill climbing the progress stops if there are no healthier successor nodes. The best first search
algorithm will engross an OR graph which averts the problem of node duplication and presumes
that every node has a parent link to provide the best node from which it came and a link to all

LOVELY PROFESSIONAL UNIVERSITY 47