CMSC 25000 - Artificial Intelligence
Winter 2004
Homework #2: Solutions

Problem 1

What problem you observe?

>  (step-by-step '(chicago-midway))
The path (chicago-midway)
Extending the path (chicago-midway)
 can be extended to get(indianapolis chicago-midway)
Continue? [y or n]:y
Extending the path (chicago-midway)
The path (indianapolis chicago-midway)
Extending the path (chicago-midway indianapolis)
 can be extended to get(chicago-midway indianapolis chicago-midway)
Continue? [y or n]:y
Extending the path (chicago-midway indianapolis)
The path (chicago-midway indianapolis chicago-midway)
Extending the path (chicago-midway indianapolis chicago-midway)
 can be extended to get(indianapolis chicago-midway indianapolis chicago-midway)
Continue? [y or n]:

The  function  gets  stuck  in  a  cycle when  processing  cyclic  graphs. The  problem  may  be  fixed  by
excluding  cities already in  the path while extending it  in  the  extend-path  function.

(define (extend-path path)
  ;;; note that this version uses a filter  to fix the bug to deal with cyclic graphs
  "
  Purpose:  Extend a path to the neighbors of the terminal airport
  Returns:  A list of extended paths
  "
  (display* "Extending the path " (reverse-path path))
  (map (lambda (nextairport)
     (cons nextairport path))
       (filter  (lambda (x) (boolean?  (member  x  path)))
                (get-neighboring-airports (first-airport path)))))

 >(step-by-step '(chicago-midway))
The path (chicago-midway)
Extending the path (chicago-midway)
 can be extended to get(indianapolis chicago-midway)
Continue? [y or n]:y
Extending the path (chicago-midway)
The path (indianapolis chicago-midway)
Extending the path (chicago-midway indianapolis)
 can be extended to get(ft-lauderdale indianapolis chicago-midway)
Continue? [y or n]:y
Extending the path (chicago-midway indianapolis)
The path (ft-lauderdale indianapolis chicago-midway)
Extending the path (chicago-midway indianapolis ft-lauderdale)
 can be extended to get(charlotte ft-lauderdale indianapolis chicago-midway)
Continue? [y or n]:

Problem 2

;;;;  DEPTH-FIRST SEARCH
 (define (combine-paths new-paths old-paths finish)
    "
    Purpose:    Define a queue constructor specific to depth-first search.
                Note that the finish argument does not need to be used.
    "
  
   (append new-paths old-paths) ;;; DFS  uses  a last-in-first-out queue
   
)

(define (depth-first originairport destnairport)
  "
  Purpose:    Perform depth-first search
  Remark:     Uses generalized search function
  "
 
  ;; Fire up generalized search using queue constructor defined above:
  (generalized-search originairport destnairport (make-finish-test destnairport)
              combine-paths 1 extend-path))

The  output  of  DFS  on  (depth-first 'newark 'san-francisco ) can  be  seen here .

Problem 3

;;;;  BREADTH-FIRST SEARCH
 (define (combine-paths-1 new-paths old-paths finish)
    "
    Purpose:    Define a queue constructor specific to depth-first search.
                Note that the finish argument does not need to be used.
    "
  
   (append old-paths new-paths) ;;; BFS  uses  a first-in-first-out queue
   
)

(define (depth-first originairport destnairport)
  "
  Purpose:    Perform depth-first search
  Remark:     Uses generalized search function
  "
 
  ;; Fire up generalized search using queue constructor defined above:
  (generalized-search originairport destnairport (make-finish-test destnairport)
              combine-paths-1 1 extend-path))

The  output  of  BFS  on  (breadth-first 'newark 'san-francisco) can  be  seen here.

Problem 4

The new data abstractions are required to implement path costs.

In terms of the notation used in the book:  f(n) = g(n) + h(n) ; g(n) is the sum of the straight-line distances  for each
leg traversed to get to node n; h(n) is the straight-line distance to get to the goal node from n. 

The modified  code  is in this file (one can use a hash table to make straight-line distance computations more efficient; this is not done here): airsearchnew.scm

With path costs, the output of the three search algorithms to go from newark to san-francisco can be  seen  here.  

It can be seen that A* search gives the  cheapest solution.   This solution requires  6 hops.  Breadth first search takes half the number of  hops but returns a much more expensive solution that requires a visit  to  Beijing (!) along the way. Depth first search gives the most expensive solution.