Lecture Notes: Heuristic Search

1. Survey of Basic Search:

A. Follow Search-Summary Handout

B. For each method, number nodes in order on depth-3 binary tree

2. A* Search

A. Goal: Be more "intelligent" (i.e. look at less nodes) than BF but still have best solution first.

B. Idea of g and h
g is exact distance from root (function of node)
h is interpreted as distance left to goal (function of position only)
f=g --> BF
f = -g --> DF
f = h --> greedy

C. A* = best first search with restriction that f = g+h, plus ("admissible")

i. h(node) <= h*(node) - "non overestimating"

ii. h(solution) = 0 [but not necessarily vice versa]

iii. h(position) unchanging

Note that this algorithm assumes that the "Node" object incorporates the current position/state as well as f, g, h, and a pointer to the parent Node. Thus, the same position/state may appear in more than one Node, but there is no need for the more complicated A* algorithm (presented in some texts) that keeps track of the "best" packpointer for a position/state. Also note that these repeated positions are eliminated with the monotonic algorithm anyhow.

D. A* Example

E. Example with word ladders. Perform A* search, going from HATE to LOVE, using the heuristic of the number of incorrect letters (wrt goal word), and the following dictionary: HATE, LATE, HAVE, LANE, RATE, RAVE, HIVE, PANE, LINE, RATS, RITE, ROVE, RACE, LIVE, DIVE, ROPE, LOVE. Note that some words appear in more than once place in the tree.

F. Idea of Monotonic h: F value never decreases along any path. I.e. go 1 step in direction of solution, and h decreases by at most 1. It is possible to have admissible but non-monotonic h. Benefit: 1st time a position is generated, it is the best. Introduce idea of a closed list.

G. Pseudo Code: Monotonic Case

           A*-Monotonic(Root)
             Open={Root}
             Closed={}
             loop
               if Open={} then return failure
               Node = pop(Open)
               if solution(Node) then return Node
               add Node to Closed
               remove from Open all nodes that terminate in the same position as Node
               Put new(*) children(Node) on Open
               sort Open by minimum f
           (*) new = positions not already on Closed

H. Showing Heuristics are Monotonic
i. Observation

ii. Exact solution to problem with constraint(s) relaxed (Pearl)
Eg1: Manhattan Distance is exactly right if you relaxed "move to empty square" rule
Eg2: Incorrect letters is exactly right if you relax rule that intermediate "words" be legal

I. Advantages:
i. Less duplicates on Open (i.e. less work expanding). Effective branching factor reduced.

ii. Node only needs to point to parent position

J. Time/Space Complexity of A* (monotonic or Otherwise)
i. Perfect h - O(D)

ii. Otherwise O(BD) [worst case] but hopefully (B/K)D on average. Space problems dominate large instances.

3. Lisp Facilities for Word Ladders:

A. (setq test "foo"), (aref "foo" 0) --> #\f (Case matters!)

B. (setf (aref test 0) #\b), test --> "boo"

C. COPY-SEQ: returns a copy of a string (or other sequence -- lists and strings are both sequences).

           (setq Test1 "Foo")
           (setq Test2 Test1)            ; Test2 now points where Test1 pointed
           (setq Test3 (copy-seq Test1)) ; Test3 is a whole new string
           (setf (aref Test2 0) #\B)

D. (setq *Table* (make-hash-table :test #'equal))
See the sections in Steele, clman, or Norvig on hash tables for more details.

E. (setf (gethash "boo" *Table*) t)

F. (gethash "boo" *Table*)

G. Example of hash tables:

           (setq *Numerals* (make-hash-table :test #'equal))
           (loop for I from 1 to 500 do
             (setf (gethash (format nil "~R" I) *Numerals*)
                   I))
           (gethash "twenty-three" *Numerals*) --> 23

H. (setq <List> (sort <List> <Predicate>)) The <Predicate> is a function of 2 arguments that accepts entries of the type in <List> and returns T/NIL depending if they are in order.
(setq <List> (sort (copy-list <List>) <Predicate>)) is safest if any other variable shares structure with <List>. You may also want to look at the MERGE function as a possible faster alternative to SORT in this context.

Table of contents

1. - Survey of Basic Search:

2. - A* Search

3. - Lisp Facilities for Word Ladders: