Transcript On Search

On Search
• Search is one of the most common CS
problems.
• There are lots of different algorithms for
searching through a set of alternatives.
• They can be compared in terms of
– Time/number of steps needed to find a solution
– Space needed by the algorithm
– Optimality
Searching Large Structures
• For most interesting problems (game trees, Prolog
rules, route finding, circuit layout, etc) you can’t
keep the entire data structure in memory.
• Instead, we select a set of nodes to examine and
keep in memory.
• For each node in memory, we check to see if there
is other nodes (successors) that we can visit from
this node.
• A node with no successors is called a goal node or
a terminal node.
An Example
father(Father,Son) :parent(Father,Son),male(Father)
parent(marge,bart).
parent(homer,bart).
father(X,Y)
male(homer).
An Example
father(Father,Son) :parent(Father,Son),male(Father)
parent(marge,bart).
parent(homer,bart).
father(X,Y)
male(homer).
parent(X,Y)
An Example
father(Father,Son) :parent(Father,Son),male(Father)
parent(marge,bart).
parent(homer,bart).
father(X,Y)
male(homer).
parent(X,Y)
parent(marge,bart)
{X=marge
Y=bart}
An Example
father(Father,Son) :parent(Father,Son),male(Father)
parent(marge,bart).
parent(homer,bart).
father(X,Y)
male(homer).
parent(X,Y)
male(marge)
Fails!
parent(marge,bart)
{X=marge
Y=bart}
An Example
father(Father,Son) :parent(Father,Son),male(Father)
parent(marge,bart).
parent(homer,bart).
father(X,Y)
male(homer).
parent(X,Y)
parent(X,bart)
male(marge)
{Y=bart}
Fails!
We need to backtrack
And undo the binding
Of X to marge.
An Example
father(Father,Son) :parent(Father,Son),male(Father)
parent(marge,bart).
parent(homer,bart).
father(X,Y)
male(homer).
parent(X,Y)
male(homer)
Success!
parent(homer,bart)
{X=homer,
Y=bart}
Depth-First Search
• Rule:
–
–
–
–
Expand a node.
Choose the “leftmost” child.
If it’s a solution, stop.
Else, expand it. If it has children, follow its
leftmost child.
– Else, back up to the parent and follow the next
leftmost node.
• Pro: Uses a linear amount of memory.
• Con: Not guaranteed to find a solution.
Breadth-first Search
• Rule:
– Expand a node
– Check if any of the children are solutions.
– If not, expand each of these nodes and visit
those children in order.
– Traverse each level of the structure in order.
• Pro: Will find a solution of one exists.
• Con: Requires exponential space.
Search and Priority Queues
• Any search strategy can be implemented with a
priority queue.
• Algorithm:
–
–
–
–
–
–
Dequeue first node, check to see if it’s a solution.
Expand node.
Enqueue children.
If we use a normal queue, we get breadth-first search.
If we use a stack, we get depth-first search.
We can get a hybrid search by assigning priorities to
nodes.