CSE 250A LECTURE NOTES

ANNOUNCEMENTS

Note that most computer science research papers are published on the web in Postscript.  To obtain a Postscript viewer for your operating system and web browser, see here.

There will be no lecture on Monday January 15 because of MLK day.
 
 

THE GENERAL SEARCH ALGORITHM (AGAIN)

 input: a well-formulated search problem
        a function "insert" to place new nodes into a queue

 fringe := make-queue(initial-node)
 loop
   if empty?(fringe) then return FAIL
   else
     X := remove-front(fringe)
     if isa-goal?(state(X)) then return X
     else
        fringe := insert(fringe,expand(X))
 end loop

• initial-node is a node representing the initial state
• isa-goal? tests whether a state is a goal state
• expand applies all the operators of the problem to a node and returns all the successors of this node
• insert includes a set of nodes in the queue in a specific way.

• information about the corresponding real-world state
• the parent node (actually, a pointer to the parent node)
• the operator that was applied to the parent and which generated this node (actually, just its name or a pointer)
• the depth of this node

Note: In the book the authors also talk about the cost of a node, which is the cost of the path from the root to this node.  This is normally the sum of the costs of the operators used along the path to the node.  We assume that all operators have non-negative costs.

Different algorithms use different insert functions, but always remove nodes one by one from the front of the fringe.
 
 

ANALYZING VARIANTS OF THE GENERAL SEARCH ALGORITHM

• completeness: does it always find a solution, if one exists?
• time complexity (= time usage = time consumption)
• space complexity
• optimality: does it find the lowest-cost solution?

Assuming this fixed branching factor,  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.

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 75 for a numerical example.
 
 

DEPTH-LIMITED SEARCH

In other words, for many problems DFS is not complete: a solution exists but DFS cannot find it.

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.

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 not complete.
 
 

ITERATIVE DEEPENING

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

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).
 
 

HEURISTIC "BEST-FIRST" SEARCH

One common type of knowledge is a scoring function that estimates how good a node would be as the next node to expand.

Note the word "estimates".  If the scoring function was perfect, then we wouldn't need any search at all.  The word "heuristic" means trial-and-error, exploratory, unguaranteed, rule of thumb.

The heuristic best-first search algorithm is

 input:(1) a function "eval" that scores nodes according to how
         promising they are for further search (lower is better)
      (2) a function "sorted-insert" that places new nodes into
                   the queue according to their scores

 fringe := make-queue(initial-node)
 loop
   if empty?(fringe) then return FAIL
   else
     n := remove-front(fringe)
     if isa-goal?(state(n)) then return n
     else
        fringe := sorted-insert(fringe,eval(expand(n)))
 end loop

GREEDY SEARCH

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

For each particular problem, the designer must choose an appropriate h function.  For example, for road finding let h(n) be the straight line "as the crow flies" distance from the current state (i.e. geographical position) to the goal position.

Greedy search is called greedy because it always tries to make the biggest jump possible towards the goal, without "thinking" further ahead about what will happen from that point.  See Figure 4.3 in AIMA for an example of how greedy search does not find the optimal path.

In the worst-case, the time and space complexity of greedy search are the same as for breadth-first search.  In the "average" case having a good heuristic function h should make greedy search much better.

Proving that greedy search is better is difficult mathematically.  It is common in AI that a heuristic idea is good but proving that it is good is difficult, precisely because heuristics are not guaranteed.

Here is an important general principle for studying a heuristic:  look for assumptions under which the heuristic is guaranteed to be correct.

Note that this is a global greedy search algorithm: the next node expanded is the one that looks best among all seen so far.  We'll discuss local search methods later.
 
 

MINIMIZING TOTAL PATH COST: A* SEARCH

The idea is that if we want to find the optimal path to the goal, i.e. the shortest or cheapest path, then the next node to explore should be the one that looks like it will yield the overall cheapest path.

The best estimate of the total cost of the path through a candidate node n is f(n) = g(n) + h(n) where h is the same estimator function of remaining distance as above and  g(n) = cost of path from the initial state to state(n).

The names f, g, h, and n are standard, soy should remember to use this notation.   Study the example in Figure 4.4, page 98 carefully.
 
 

ANALYZING THE BEHAVIOR OF A*

We will do an analysis here that shows that A* is optimal.  This analysis is different from a conventional algorithm analysis because

• we are not calculating time or space complexity
• we will make assumptions.

Intuitively, admissible means acceptable or reasonable.  Formally, h(n) is admissible if it is always true that

h(n) = estimated cost of cheapest path from state(n) to goal
        < actual cost of cheapest path from state(n) to goal