CSE 150 LECTURE NOTES

Wednesday September 29, 2004
 
 

ANNOUNCEMENTS 

I'm handing out the first assignment today. It's due in two weeks, on October 13.  You may work by yourself, or with one partner.  Be sure to watch the class web page for changes and clarifications.

Our discussion board is up and running at http://webct.ucsd.edu/.  Your login is your UCSD email username, and your password is your PID number.


OUR GENERAL SEARCH ALGORITHM

This algorithm is:

fringe := make-queue(initial-node)
loop
   if empty?(fringe) then return FAIL
   else

     X := remove-front(fringe)
     if satisfies-goal(state(X)) then return X
     else
        fringe := insert(fringe,expand(X))
 end loop

We call this algorithm "general" because different algorithms are different special cases of it.  These different algorithms use varying insert functions, but always remove nodes one by one from the front of the fringe.


NOTES

(1) The search algorithm needs an efficient representation of the fringe.  We use a priority queue, i.e. a special list where you can remove one  element from the front, and you can insert new elements anywhere.  The "priority" of an element indicates where it goes in the queue (front, middle, back).

(2) We will represent a node as a tuple with the following components:

(3) The depth of a node is the number of edges on the path to this node from the root.  The depth of the root is 0 by this definition.

(4) Expanding a node may lead to a child node that represents the same state represented by another node.  The general search algorithm generates a tree of nodes, not the search space directly: compare the pictures on pages 63 and 70.

(5) Normally the agent does not "know" the entire set of states.  "Know" means "have available an explicit representation of".  What is called a "representation" in AI is often called a data structure elsewhere in computer science.


BREADTH-FIRST (BFS) VERSUS DEPTH-FIRST (DFS) SEARCH

BFS is the general search algorithm where nodes discovered by expansion are added to the fringe at the end.  This implies that they are expanded after all the nodes already in the fringe.

DFS is the general search algorithm where nodes discovered by expansion are added to the fringe at the beginning.  This implies that they are then expanded immediately, before all the nodes already in the fringe.

BFS first considers all paths of length 1, then all paths of length 2, and so on.  This is why it is called "breadth-first".

DFS goes down a path until it reaches a node that has no children.  Then DFS "backtracks" and expands a sibling of the node that had no children.  If this node has no siblings, then DFS looks for a sibling of the grandparent, and so on.

The pictures on page 74 and 76 show intuitively how BFS and DFS work.

 

ANALYZING VARIANTS OF THE GENERAL SEARCH ALGORITHM

We can evaluate alternative algorithms according to: Definition: The branching factor of a search tree is the average number of children.

To simplify analysis, we often consider a search tree where expanding a node always gives exactly b children, so the branching factor is b.  

Definition:  The root is at depth 0.

With the assumptions above, the number of nodes at depth n or less is N = 1 + b + b^2 + ... + b^n.

Somewhat surprisingly, N = (b^(n+1) - 1)/(b-1) which is O(b^n).  Intuitively, almost all the nodes are at the deepest level, and the number of shallower nodes is negligible in comparison, if b >= 2.


ANALYSIS OF BFS AND DFS

For a problem with branching factor b where the first solution is at depth k, the time complexity of BFS is O(b^k), and its space complexity is also O(b^k).

The big problem with breadth-first search is that it uses about as much space as it uses time.  Any real computer will run out of space before it runs out of time, if the amount of space used is linearly proportional to the amount of time used.  See the table on page ? for a numerical example.

The major advantage of DFS is that it only uses O(bm) space if the branching factor is b and the maximum depth is m.  Explanation: there are m nodes on the longest path, and for each of these b-1 siblings must be stored.

No matter how deep the current node is, DFS will always go deeper if it has a child.  The major weakness of DFS is that it will fail to terminate if there is an infinite path "to the left of" the path to the first solution.  So DFS is not complete.


DEPTH-LIMITED SEARCH

Depth-limited search is the same as DFS except a nodes of depth equal to a fixed maximum (say M) are not expanded.

If a solution exists at depth M or less, then M-limited DFS will find it, and this algorithm is very space-efficient, since it uses only O(b*M) space.
 
If a solution exists but only at depth greater than M, then depth-limited DFS is still not complete.


ITERATIVE DEEPENING

Iterative deepening is a very simple, very good, but counter-intuitive idea that was not discovered until the mid 1970s.  Then it was invented by many people simultaneously.

The idea is to depth-limited DFS repeatedly, with an increasing depth limit, until a solution is found.

Intuitively, this is a dubious idea because each repetition of depth-limited DFS will repeat uselessly all the work done by previous repetitions.  But, this useless repetition is not significant because a branching factor b >= 2 implies that

 number of nodes at depth k > number of nodes at depth k-1 or less
Therefore, iterative deepening simulates BFS with linear space complexity.

For a problem with branching factor b where the first solution is at depth k, the time complexity of iterative deepening is O(b^k), and its space complexity is O(b*k).