\input{/home/sc/yip/cs201-macro.tex}
\input{psfig}

\setlength{\textwidth}{6.25 in}
\setlength{\textheight}{10.0 in}
\setlength{\topmargin}{-.6 in}


\begin{document} 
\pagestyle{empty}

\psetheader{Fall Semester, 1996}{Practice Problems -- Sep 19, 1996}

\leftbold{Problem}

In this problem, we consider the implementation of a variety of searches
in terms of two generic procedures.  

\beginlisp
(define (tree-search paths goal? successors combiner bound)
  "Find a path that satisfies goal?.  
   Successors extend a path into new paths.
   Combiner merges old and new paths.
   Bound is the upper bound for the length of a path."
  (cond ((null? paths) fail)
        ((goal? (first paths)) (first paths))
        ((> (path-length (first paths)) bound)
         (tree-search (rest paths) goal? successors combiner bound))
        (else (tree-search
               (combiner (successors (first paths))
                         (rest paths))
               goal? successors combiner bound))))

(define (sorter cost-fn before-sort after-sort)
  "Return a combiner function that sorts the combined new and old paths
   according to cost-fn.
   Before-sort is a procedure of two arguments; it operates on old
   and new paths before the sorting is done.
   After-sort is a procedure of three arguments; it operates on the
   sorted paths, the old path, and the new path after the sorting is done.
   Sort takes 3 arguments: a list to be sorted, a comparator, and a cost 
   function."
  (lambda (new old)
    (after-sort
     (sort (before-sort new old) < cost-fn)
     new
     old)))

(define (filter-duplicates l test keep)
  "Remove all but one of the duplicates. Allows you the flexibility
  to decide which of the duplicates to keep.  The default is the first one."
  (define (helper head-seq e tail-seq)
    (if (null? tail-seq)
        (append head-seq (list e))
        (let ((dup (find-if (lambda(x)(test e x))
                            tail-seq)))
          (if (null? dup)
              (helper (append head-seq (list e)) (car tail-seq) (cdr tail-seq))
              (cond ((eq? (keep e dup) e)
                     (helper head-seq e
                             (remove-if (lambda(x)(test e x)) tail-seq)))
                    (else
                     (helper head-seq
                             (car tail-seq)
                             (cdr tail-seq))))))))
      (helper nil (car l) (cdr l))))
\endlisp

\clearpage

With these procedure, we can rewrite depth-first search as:

\beginlisp
(define (depth-first start goal-p successors bound)
  (tree-search (list (list start)) goal-p successors append bound))
\endlisp



Fill in the definition for each of the following searches:

A. Breadth-first

\beginlisp
(define (breadth-first start goal-p successors bound)
\vspace{.6in}
\endlisp


B. Best-first

\beginlisp
(define (best-first start goal-p successors bound cost-fn)
\vspace{.6in}
\endlisp


C. Iterative Deepening

\beginlisp
(define (iterative-deepening start goal-p successors bound)
\vspace{.6in}
\endlisp


D. Hill-climbing

\beginlisp
(define (hill-climbing start goal-p successors bound cost-fn)
\vspace{.6in}
\endlisp


E. Branch-and-bound

\beginlisp
(define (branch-and-bound start goal-p successors bound cost-fn)
\vspace{.6in}
\endlisp


F. Branch-and-bound with Dynamic Programming

\beginlisp
(define (branch-and-bound-DP start goal-p successors bound cost-fn)
\vspace{.6in}
\endlisp

G. A*  (This part is more difficult.)

\beginlisp
(define (A* start goal-p successors bound cost-fn1 cost-fn2)
\vspace{.6in}
\endlisp


\end{document}