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

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


\begin{document} 
\pagestyle{empty}

\psetheader{Fall Semester, 1996}{Practice Problems -- Oct 10, 1996}

\leftbold{Problem: Search}

You are driving a cab in a weird, unfamiliar city with streets laid out as
shown in the figure.  Streets with arrows are one-way streets in
the indicated direction.

\begin{figure}[hbtp]
%\centerline{\psfig{file=quiz.7,height=3.75in}}
\vspace{2.5in}
\caption {A weird city.}
\end{figure}

At intersection S, a customer says he wants to go to intersection G.

Important special notes:

\begin{itemize}
\item The map is drawn to scale.
\item When you are asked to think about a method that involves a heuristic
   measure of ``goodness,'' you are to use straight-line,
   as-the-crow-flies, distance-to-goal as that heuristic measure.
\item For all searches in which branch order is not defined by a measure of
   ``goodness,'' assume that the search moves down from the branch labeled
   1 before moving down from the branch labeled 2.
\end{itemize}

Part A.

You decide to look for a route using depth-first search.

You encounter \onebox{.7in}{.2in} paths through place I in the search tree before
you find a path from S to G.

Part B.

Later, over coffee, another driver, also MIT educated, says you blundered;
you should have used hill climbing (with backup, the kind of hill climbing
described in the book).  If you had, you would have encountered \onebox{.7in}{.2in}
paths through place I in the search tree before you find a path from S to
G.

Part C.

Your boss says you should have used best first search.  If you had, you
would have encountered \onebox{.7in}{.2in} paths through place I in the search tree
before you find a path from S to G.

Part D.

Your passenger says you should have used breadth-first search.  If you had,
you would have encountered \onebox{.7in}{.2in} paths through place I in the search tree
before you find a path from S to G.

Part E.

Your friend says you should have modified depth-first search to incorporate
something similar to the dynamic programming principle that appears in A*
search.  In the A* context, the dynamic programming principle says that if
you find two paths to the same place, you throw away the longer of the two.
In the modification suggested by your friend, if you find that a
newly-extended path intersects with a previous path, throw away the newly
extended path.

If you had modified depth-first search as described, you would have
encountered \onebox{.7in}{.2in} paths through place I in the search tree before you
find a path from S to G.



\end{document}