Search Methods
Problem Solving as Search

Move disk to peg
to the initial state ((123)()()) a new state is reached ((23)()(1))



Search Methods





* A partial tree search space representation
* A complete direct graph representation
[http://en.wikipedia.org/wiki/Tower_of_Hanoi]
Brute force approach to explore search space
List open, closed, successors={};
Node root_node, current_node;
insertfirst(
root_node,open)
while notempty (open );
N.B.= this version is not saving the path for simplicity
Result is: S>A>B>F
=1 + b + b^{2}+ ......... + b^{m} = O (b ^{m} )



List open, closed, successors={};
Node root_node, current_node;
insertlast(
root_node,open)
while notempty (open );
N.B.= this version is not saving the path for simplicity
Result is: S>A>F
Depthlimited search (DLS) : Impose a cutoff (e.g. n for searching a path of length n 1), expand nodes with max. depth first until cutoff depth is reached (LIFO strategy, since it is a variation of depthfirst search).
Bidirectional search (BIDI) : forward search from initial state & backward search from goal state, stop when the two searches meet. Average effort O(b ^{d/2} ) if testing whether the search fronts intersect has constant effort
In AI, the problem graph is typically not known. If the graph is known, to find all optimal paths in a graph with labelled arcs, standard graph algorithms can be used
Using knowledge on the search space to reduce search costs
Blind search methods take O(b^{m}) in the worst case
May make blind search algorithms prohibitively slow where d is large
Use problemspecific knowledge to pick which states are better candidates
Also called heuristic search
In a heuristic search each state is assigned a “heuristic value” (hvalue) that the search uses in selecting the “best” next step
A heuristic is an operationallyeffective nugget of information on how to direct search in a problem space
Heuristics are only approximately correct
BestFirst Search
A*
Hill Climbing
f(n)=g(n)+h(n)
g(n) the cost (so far) to reach the node n
h(n) estimated cost to get from the node to the goal
f(n) estimated total cost of path through n to goal
List open, closed, successors={};
Node root_node, current_node;
insertlast(
root_node,open)
while notempty (open );
estimationOrderedSuccessorsOf
returns the list of direct
descendants of the current
node in shortest cost order
N.B.= this version is not saving the path for simplicity
In this case we estimate the cost as the distance from the root node (in term of nodes)
Derived from BestFirst Search
Uses both g(n) and h(n)
A* is optimal
A* is complete
List open, closed, successors={};
Node root_node, current_node, goal;
insertback(
root_node,open)
while notempty (open );
totalEstOrderedSuccessorsOf
returns the list of direct
descendants of the current
node in shortest total
estimation order
N.B.= this version is not saving the path for simplicity
In this case we estimate the cost as the distance from the root node (in term of nodes)
Result is: S>B>F!
N.B.= this version is not saving the path for simplicity
In this case we estimate the cost as the distance from the root node (in term of nodes)
Result is: S>A>B>F!
Not optimal, more if at step 1 h(S)=2 we would have completed without funding a solution
Algorithm

Time

Space

Optimal

Complete

Derivative


Best First Search

O(bm)

O(bm)

No

Yes

BFS


Hill Climbing

O(∞)

O(b)

No

No



A*

O(2^{N})

O(b^{d})

Yes

Yes

Best First Search

ILLUSTRATION BY A LARGER EXAMPLE


N.B.: by building the tree, we are exploring the search space!
N.B.: by building the tree, we are exploring the search space!
N.B.: by building the tree, we are exploring the search space!
EXTENSIONS
SUMMARY
REFERENCES
Questions?