\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{3}

% title command
\newcommand{\mytitle}[1]{\begin{center} {\Large Artificial Intelligence -- 
6.034 Problem Set \psnum \\ Juliet Bourne -- Section R1 -- #1} \\ 
\vspace{-.1in}
\rule{6in}{.5mm} \end{center}}
% problem command
\newcommand{\prob}[1]{\vspace{.15in}\noindent{\fbox{\large\bf Problem #1}}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}
% newpage setup command 
\newcommand{\mynewpage}{\newpage\noindent
\begin{center}
{\Large 6.034 Problem Set \psnum -- Juliet Bourne -- {\bf Page \thepg}}
\rule{6in}{.5mm}
\end{center}
\addtocounter{pg}{1}}
% see-page command
\newcommand{\seepage}{\noindent See page \rule{.2in}{.1mm} for the
computer output.}

\begin{document}

\mytitle{10/05/90}

\prob{1}

The major changes are as follows (complete code is attached):

\begin{verbatim}
(defun aux-search-bb+dp (queue finish-node graph)
  (format t "~% Sorted Queue is ~s" queue)
  (if queue
      (if (eq finish-node (last-node-in-path (queue-head queue)))
          (let ((path (queue-head queue)))
            (cons (path-length path) (reverse (path-in-reverse path))))
          (aux-search-bb+dp
           (delete-redundant (sort-and-merge
                              (extend (queue-head queue) graph)
                              (queue-tail queue)))
           finish-node graph))))

;; delete-redundant takes a sorted queue and returns a sorted queue
;; minus any paths (except the least-cost one) that reach a common node.
;; it does this recursively.
(defun delete-redundant (queue)
  (if queue
      (let* ((new-queue (make-queue (queue-head queue)))
             (end-node (last-node-in-path (queue-head new-queue)))
             (rest-queue (queue-tail queue)))
        (if rest-queue
            (if (not (eq end-node (last-node-in-path (queue-head rest-queue))))                (append new-queue (delete-redundant rest-queue))
                (append new-queue (delete-redundant (queue-tail rest-queue))))
            queue))))

;; takes a list of paths, sorts them with SHORTERP, putting least cost
;; paths first, and then merges them into the queue. returns the new
;; queue
(defun sort-and-merge (new-paths queue)
  (let ((sorted-paths (sort new-paths #'shorterp)))
    (merge 'list sorted-paths queue #'shorterp)))

\end{verbatim}

The output looks like (again, see attached for full output):

\begin{verbatim}
 Sorted Queue is ((0.0 S))
 Sorted Queue is ((20.0 D S) (60.0 B S) (100.0 A S))
 Sorted Queue is ((50.0 B D S) (100.0 A S))
 Sorted Queue is ((60.0 C B D S) (90.0 A B D S))
 Sorted Queue is ((70.0 A C B D S))
 Sorted Queue is ((140.0 E A C B D S))
(140.0 S D B C A E)
\end{verbatim}

\mynewpage

\prob{2}

\subprob{A} See the attached sheets for the full code and output.

My procedure {\bf search-A*} run on {\bf *P2*} results in a stack
overflow error, even if the code is compiled and optimized. This is
probably because my procedure {\bf delete-redundant} is recursive, not
just tail-recursive. The compiler apparently doesn't optimize for
recursive code as it does for tail-recursive code. Therefore, near as
I can figure, the queue generated when running {\bf search-A*} on {\bf
*p2*} is too large for the stack. I've included the output containing
the error. If I had more time, I would have changed my algorithm for
{\bf delete-redundant} to be iterative so that it didn't have problems
with large queues.

\subprob{B} An A* search with e(board position) = 0 as the estimate of
the remaining distance would just be the branch and bound search with 
dynamic programming as in problem 1.

\subprob{c} An A* search with just misplaced-tiles estimate and not
the accumulated cost so far would resemble a minimax search.

\subprob{D} A more informed estimate than the misplaced-tiles estimate
would be summing how many moves it would take for each tile to reach
its goal state, if the rest of the board was empty. Obviously, this is
a lower-bound estimate since it is going to take more moves for a tile
to reach its goal position when all the other tiles are in the way.

Using arrays, this would be done by adding absolute values of the
differences of the array subscripts of a tile in its goal position and
in its current position. The procedure {\bf new-estimate-cost}
implements this algorithm.

When run on {\bf *P1*}, {\bf new-search-A*} finds the same path as
{\bf search-A*}. For {\bf *P2*} however, the difference the {\bf
new-estimate-cost} makes is striking. Using {\bf new-search-A*}, the
queue size reaches only 35, as compared to 155+ with {\bf search-A*}.

\end{document}


