; David Golombek (daveg@mit.edu) ; 6.034 pset #4 1) (define (extend-path path) ;;; note that this initial version has a bug you will need to fix " Purpose: Extend a path to the neighbors of the terminal host Returns: A list of extended paths " ;; Following for debugging; delete when debugging is complete: ; (format #t "~%Extending the path ~a." (reverse-path path)) ; first try adding each neighboring host to the path (let ((path-exts (map (lambda (nexthost) (if (not (memq nexthost path)) (cons nexthost path) '())) (get-neighboring-hosts (first-host path))))) ; return those paths where the neighboring host wasn't already passed (list-transform-negative path-exts null?))) 1 ]=> (step-by-step '(mit)) The path (mit) can be extended to get (mt-holyoke mit) Continue? [y or n]: y The path (mt-holyoke mit) can be extended to get (smith mt-holyoke mit) Continue? [y or n]: y The path (smith mt-holyoke mit) can be extended to get (amherst smith mt-holyok\ e mit) Continue? [y or n]: y The path (amherst smith mt-holyoke mit) can be extended to get (dartmouth amher\ st smith mt-holyoke mit) Continue? [y or n]: y The path (dartmouth amherst smith mt-holyoke mit)cannot be extended any further\ . ; David Golombek ; 6.034 pset #4 2) (define (combine-paths new-paths old-paths finish) " Purpose: Define a queue constructor specific to depth-first search; add the new paths in front Note that the finish argument doe not need to be used. " ; simply put new paths in front of old paths (append new-paths old-paths) ) 1 ]=> (depth-first 'mit 'cmu) Extending the path (mit). Extending the path (mit mt-holyoke). Extending the path (mit mt-holyoke smith). Extending the path (mit mt-holyoke smith amherst). Extending the path (mit mt-holyoke smith amherst dartmouth). Extending the path (mit mt-holyoke smith amherst bu). Extending the path (mit mt-holyoke smith amherst bu hahvud). Extending the path (mit mt-holyoke smith amherst bu hahvud wellesley). Extending the path (mit mt-holyoke smith amherst bu hahvud wellesley babson). Extending the path (mit mt-holyoke smith amherst bu hahvud wellesley babson uma\ ss-amherst). Extending the path (mit mt-holyoke smith amherst bu hahvud wellesley babson uma\ ss-amherst penn). Extending the path (mit mt-holyoke smith amherst bu hahvud wellesley babson uma\ ss-amherst penn princeton). Extending the path (mit mt-holyoke smith amherst bu hahvud wellesley babson uma\ ss-amherst penn princeton ga-tech). Extending the path (mit mt-holyoke smith amherst bu hahvud wellesley babson uma\ ss-amherst penn princeton ga-tech tenn). Extending the path (mit mt-holyoke smith amherst bu hahvud wellesley babson uma\ ss-amherst penn princeton ga-tech tenn urbana). Extending the path (mit mt-holyoke smith amherst bu hahvud wellesley babson uma\ ss-amherst penn princeton ga-tech chicago). Extending the path (mit mt-holyoke smith amherst bu hahvud wellesley babson uma\ ss-amherst penn princeton ga-tech chicago columbia). Final path length is 15 Proceed from mit to mt-holyoke then from mt-holyoke to smith then from smith to amherst then from amherst to bu then from bu to hahvud then from hahvud to wellesley then from wellesley to babson then from babson to umass-amherst then from umass-amherst to penn then from penn to princeton then from princeton to ga-tech then from ga-tech to chicago then from chicago to columbia then from columbia to cmu. ;Value 8: ((cmu columbia chicago ga-tech princeton penn umass-amherst babson we\ llesley hahvud bu amherst smith mt-holyoke mit)) ; David Golombek ; 6.034 pset #4 3) (define (breadth-first originhost destnhost) " Purpose: Perform breadth-first search Remark: Uses generalized search function " (define (combine-paths new-paths old-paths finish) " Purpose: Define a queue constructor specific to breadth-first search; add the new paths in back Note that the finish argument doe not need to be used. " (append old-paths new-paths) ) ;; Fire up generalized search using queue constructor defined above: (generalized-search originhost destnhost (make-finish-test destnhost) combine-paths 1 extend-path)) 1 ]=> (breadth-first 'mit 'cmu) Extending the path (mit). Extending the path (mit mt-holyoke). Extending the path (mit amherst). Extending the path (mit bu). Extending the path (mit hahvud). Extending the path (mit wellesley). Extending the path (mit mt-holyoke smith). Extending the path (mit mt-holyoke amherst). Extending the path (mit mt-holyoke bu). Extending the path (mit amherst dartmouth). Extending the path (mit amherst smith). Extending the path (mit amherst mt-holyoke). Extending the path (mit amherst bu). Extending the path (mit amherst hahvud). Extending the path (mit bu mt-holyoke). Extending the path (mit bu amherst). Extending the path (mit bu hahvud). Extending the path (mit bu wellesley). Extending the path (mit hahvud amherst). Extending the path (mit hahvud bu). Extending the path (mit hahvud wellesley). Extending the path (mit wellesley bu). Extending the path (mit wellesley hahvud). Extending the path (mit wellesley babson). Extending the path (mit wellesley princeton). Extending the path (mit wellesley penn). Extending the path (mit mt-holyoke smith amherst). Extending the path (mit mt-holyoke amherst dartmouth). Extending the path (mit mt-holyoke amherst smith). Extending the path (mit mt-holyoke amherst bu). Extending the path (mit mt-holyoke amherst hahvud). Extending the path (mit mt-holyoke bu amherst). Extending the path (mit mt-holyoke bu hahvud). Extending the path (mit mt-holyoke bu wellesley). Extending the path (mit amherst smith mt-holyoke). Extending the path (mit amherst mt-holyoke smith). Extending the path (mit amherst mt-holyoke bu). Extending the path (mit amherst bu mt-holyoke). Extending the path (mit amherst bu hahvud). Extending the path (mit amherst bu wellesley). Extending the path (mit amherst hahvud bu). Extending the path (mit amherst hahvud wellesley). Extending the path (mit bu mt-holyoke smith). Extending the path (mit bu mt-holyoke amherst). Extending the path (mit bu amherst dartmouth). Extending the path (mit bu amherst smith). Extending the path (mit bu amherst mt-holyoke). Extending the path (mit bu amherst hahvud). Extending the path (mit bu hahvud amherst). Extending the path (mit bu hahvud wellesley). Extending the path (mit bu wellesley hahvud). Extending the path (mit bu wellesley babson). Extending the path (mit bu wellesley princeton). Extending the path (mit bu wellesley penn). Extending the path (mit hahvud amherst dartmouth). Extending the path (mit hahvud amherst smith). Extending the path (mit hahvud amherst mt-holyoke). Extending the path (mit hahvud amherst bu). Extending the path (mit hahvud bu mt-holyoke). Extending the path (mit hahvud bu amherst). Extending the path (mit hahvud bu wellesley). Extending the path (mit hahvud wellesley bu). Extending the path (mit hahvud wellesley babson). Extending the path (mit hahvud wellesley princeton). Extending the path (mit hahvud wellesley penn). Extending the path (mit wellesley bu mt-holyoke). Extending the path (mit wellesley bu amherst). Extending the path (mit wellesley bu hahvud). Extending the path (mit wellesley hahvud amherst). Extending the path (mit wellesley hahvud bu). Extending the path (mit wellesley babson umass-amherst). Extending the path (mit wellesley babson princeton). Extending the path (mit wellesley babson penn). Extending the path (mit wellesley babson tenn). Extending the path (mit wellesley princeton babson). Extending the path (mit wellesley princeton penn). Extending the path (mit wellesley princeton ga-tech). Extending the path (mit wellesley princeton tenn). Extending the path (mit wellesley penn babson). Extending the path (mit wellesley penn umass-amherst). Extending the path (mit wellesley penn princeton). Extending the path (mit wellesley penn tenn). Extending the path (mit wellesley penn urbana). Extending the path (mit mt-holyoke smith amherst dartmouth). Extending the path (mit mt-holyoke smith amherst bu). Extending the path (mit mt-holyoke smith amherst hahvud). Extending the path (mit mt-holyoke amherst bu hahvud). Extending the path (mit mt-holyoke amherst bu wellesley). Extending the path (mit mt-holyoke amherst hahvud bu). Extending the path (mit mt-holyoke amherst hahvud wellesley). Extending the path (mit mt-holyoke bu amherst dartmouth). Extending the path (mit mt-holyoke bu amherst smith). Extending the path (mit mt-holyoke bu amherst hahvud). Extending the path (mit mt-holyoke bu hahvud amherst). Extending the path (mit mt-holyoke bu hahvud wellesley). Extending the path (mit mt-holyoke bu wellesley hahvud). Extending the path (mit mt-holyoke bu wellesley babson). Extending the path (mit mt-holyoke bu wellesley princeton). Extending the path (mit mt-holyoke bu wellesley penn). Extending the path (mit amherst smith mt-holyoke bu). Extending the path (mit amherst mt-holyoke bu hahvud). Extending the path (mit amherst mt-holyoke bu wellesley). Extending the path (mit amherst bu mt-holyoke smith). Extending the path (mit amherst bu hahvud wellesley). Extending the path (mit amherst bu wellesley hahvud). Extending the path (mit amherst bu wellesley babson). Extending the path (mit amherst bu wellesley princeton). Extending the path (mit amherst bu wellesley penn). Extending the path (mit amherst hahvud bu mt-holyoke). Extending the path (mit amherst hahvud bu wellesley). Extending the path (mit amherst hahvud wellesley bu). Extending the path (mit amherst hahvud wellesley babson). Extending the path (mit amherst hahvud wellesley princeton). Extending the path (mit amherst hahvud wellesley penn). Extending the path (mit bu mt-holyoke smith amherst). Extending the path (mit bu mt-holyoke amherst dartmouth). Extending the path (mit bu mt-holyoke amherst smith). Extending the path (mit bu mt-holyoke amherst hahvud). Extending the path (mit bu amherst smith mt-holyoke). Extending the path (mit bu amherst mt-holyoke smith). Extending the path (mit bu amherst hahvud wellesley). Extending the path (mit bu hahvud amherst dartmouth). Extending the path (mit bu hahvud amherst smith). Extending the path (mit bu hahvud amherst mt-holyoke). Extending the path (mit bu hahvud wellesley babson). Extending the path (mit bu hahvud wellesley princeton). Extending the path (mit bu hahvud wellesley penn). Extending the path (mit bu wellesley hahvud amherst). Extending the path (mit bu wellesley babson umass-amherst). Extending the path (mit bu wellesley babson princeton). Extending the path (mit bu wellesley babson penn). Extending the path (mit bu wellesley babson tenn). Extending the path (mit bu wellesley princeton babson). Extending the path (mit bu wellesley princeton penn). Extending the path (mit bu wellesley princeton ga-tech). Extending the path (mit bu wellesley princeton tenn). Extending the path (mit bu wellesley penn babson). Extending the path (mit bu wellesley penn umass-amherst). Extending the path (mit bu wellesley penn princeton). Extending the path (mit bu wellesley penn tenn). Extending the path (mit bu wellesley penn urbana). Extending the path (mit hahvud amherst smith mt-holyoke). Extending the path (mit hahvud amherst mt-holyoke smith). Extending the path (mit hahvud amherst mt-holyoke bu). Extending the path (mit hahvud amherst bu mt-holyoke). Extending the path (mit hahvud amherst bu wellesley). Extending the path (mit hahvud bu mt-holyoke smith). Extending the path (mit hahvud bu mt-holyoke amherst). Extending the path (mit hahvud bu amherst dartmouth). Extending the path (mit hahvud bu amherst smith). Extending the path (mit hahvud bu amherst mt-holyoke). Extending the path (mit hahvud bu wellesley babson). Extending the path (mit hahvud bu wellesley princeton). Extending the path (mit hahvud bu wellesley penn). Extending the path (mit hahvud wellesley bu mt-holyoke). Extending the path (mit hahvud wellesley bu amherst). Extending the path (mit hahvud wellesley babson umass-amherst). Extending the path (mit hahvud wellesley babson princeton). Extending the path (mit hahvud wellesley babson penn). Extending the path (mit hahvud wellesley babson tenn). Extending the path (mit hahvud wellesley princeton babson). Extending the path (mit hahvud wellesley princeton penn). Extending the path (mit hahvud wellesley princeton ga-tech). Extending the path (mit hahvud wellesley princeton tenn). Extending the path (mit hahvud wellesley penn babson). Extending the path (mit hahvud wellesley penn umass-amherst). Extending the path (mit hahvud wellesley penn princeton). Extending the path (mit hahvud wellesley penn tenn). Extending the path (mit hahvud wellesley penn urbana). Extending the path (mit wellesley bu mt-holyoke smith). Extending the path (mit wellesley bu mt-holyoke amherst). Extending the path (mit wellesley bu amherst dartmouth). Extending the path (mit wellesley bu amherst smith). Extending the path (mit wellesley bu amherst mt-holyoke). Extending the path (mit wellesley bu amherst hahvud). Extending the path (mit wellesley bu hahvud amherst). Extending the path (mit wellesley hahvud amherst dartmouth). Extending the path (mit wellesley hahvud amherst smith). Extending the path (mit wellesley hahvud amherst mt-holyoke). Extending the path (mit wellesley hahvud amherst bu). Extending the path (mit wellesley hahvud bu mt-holyoke). Extending the path (mit wellesley hahvud bu amherst). Extending the path (mit wellesley babson umass-amherst penn). Extending the path (mit wellesley babson princeton penn). Extending the path (mit wellesley babson princeton ga-tech). Extending the path (mit wellesley babson princeton tenn). Extending the path (mit wellesley babson penn umass-amherst). Extending the path (mit wellesley babson penn princeton). Extending the path (mit wellesley babson penn tenn). Extending the path (mit wellesley babson penn urbana). Extending the path (mit wellesley babson tenn princeton). Extending the path (mit wellesley babson tenn penn). Extending the path (mit wellesley babson tenn ga-tech). Extending the path (mit wellesley babson tenn urbana). Extending the path (mit wellesley princeton babson umass-amherst). Extending the path (mit wellesley princeton babson penn). Extending the path (mit wellesley princeton babson tenn). Extending the path (mit wellesley princeton penn babson). Extending the path (mit wellesley princeton penn umass-amherst). Extending the path (mit wellesley princeton penn tenn). Extending the path (mit wellesley princeton penn urbana). Extending the path (mit wellesley princeton ga-tech tenn). Extending the path (mit wellesley princeton ga-tech chicago). Extending the path (mit wellesley princeton tenn babson). Extending the path (mit wellesley princeton tenn penn). Extending the path (mit wellesley princeton tenn ga-tech). Extending the path (mit wellesley princeton tenn urbana). Extending the path (mit wellesley penn babson umass-amherst). Extending the path (mit wellesley penn babson princeton). Extending the path (mit wellesley penn babson tenn). Extending the path (mit wellesley penn umass-amherst babson). Extending the path (mit wellesley penn princeton babson). Extending the path (mit wellesley penn princeton ga-tech). Extending the path (mit wellesley penn princeton tenn). Extending the path (mit wellesley penn tenn babson). Extending the path (mit wellesley penn tenn princeton). Extending the path (mit wellesley penn tenn ga-tech). Extending the path (mit wellesley penn tenn urbana). Extending the path (mit wellesley penn urbana tenn). Extending the path (mit mt-holyoke smith amherst bu hahvud). Extending the path (mit mt-holyoke smith amherst bu wellesley). Extending the path (mit mt-holyoke smith amherst hahvud bu). Extending the path (mit mt-holyoke smith amherst hahvud wellesley). Extending the path (mit mt-holyoke amherst bu hahvud wellesley). Extending the path (mit mt-holyoke amherst bu wellesley hahvud). Extending the path (mit mt-holyoke amherst bu wellesley babson). Extending the path (mit mt-holyoke amherst bu wellesley princeton). Extending the path (mit mt-holyoke amherst bu wellesley penn). Extending the path (mit mt-holyoke amherst hahvud bu wellesley). Extending the path (mit mt-holyoke amherst hahvud wellesley bu). Extending the path (mit mt-holyoke amherst hahvud wellesley babson). Extending the path (mit mt-holyoke amherst hahvud wellesley princeton). Extending the path (mit mt-holyoke amherst hahvud wellesley penn). Extending the path (mit mt-holyoke bu amherst hahvud wellesley). Extending the path (mit mt-holyoke bu hahvud amherst dartmouth). Extending the path (mit mt-holyoke bu hahvud amherst smith). Extending the path (mit mt-holyoke bu hahvud wellesley babson). Extending the path (mit mt-holyoke bu hahvud wellesley princeton). Extending the path (mit mt-holyoke bu hahvud wellesley penn). Extending the path (mit mt-holyoke bu wellesley hahvud amherst). Extending the path (mit mt-holyoke bu wellesley babson umass-amherst). Extending the path (mit mt-holyoke bu wellesley babson princeton). Extending the path (mit mt-holyoke bu wellesley babson penn). Extending the path (mit mt-holyoke bu wellesley babson tenn). Extending the path (mit mt-holyoke bu wellesley princeton babson). Extending the path (mit mt-holyoke bu wellesley princeton penn). Extending the path (mit mt-holyoke bu wellesley princeton ga-tech). Extending the path (mit mt-holyoke bu wellesley princeton tenn). Extending the path (mit mt-holyoke bu wellesley penn babson). Extending the path (mit mt-holyoke bu wellesley penn umass-amherst). Extending the path (mit mt-holyoke bu wellesley penn princeton). Extending the path (mit mt-holyoke bu wellesley penn tenn). Extending the path (mit mt-holyoke bu wellesley penn urbana). Extending the path (mit amherst smith mt-holyoke bu hahvud). Extending the path (mit amherst smith mt-holyoke bu wellesley). Extending the path (mit amherst mt-holyoke bu hahvud wellesley). Extending the path (mit amherst mt-holyoke bu wellesley hahvud). Extending the path (mit amherst mt-holyoke bu wellesley babson). Extending the path (mit amherst mt-holyoke bu wellesley princeton). Extending the path (mit amherst mt-holyoke bu wellesley penn). Extending the path (mit amherst bu hahvud wellesley babson). Extending the path (mit amherst bu hahvud wellesley princeton). Extending the path (mit amherst bu hahvud wellesley penn). Extending the path (mit amherst bu wellesley babson umass-amherst). Extending the path (mit amherst bu wellesley babson princeton). Extending the path (mit amherst bu wellesley babson penn). Extending the path (mit amherst bu wellesley babson tenn). Extending the path (mit amherst bu wellesley princeton babson). Extending the path (mit amherst bu wellesley princeton penn). Extending the path (mit amherst bu wellesley princeton ga-tech). Extending the path (mit amherst bu wellesley princeton tenn). Extending the path (mit amherst bu wellesley penn babson). Extending the path (mit amherst bu wellesley penn umass-amherst). Extending the path (mit amherst bu wellesley penn princeton). Extending the path (mit amherst bu wellesley penn tenn). Extending the path (mit amherst bu wellesley penn urbana). Extending the path (mit amherst hahvud bu mt-holyoke smith). Extending the path (mit amherst hahvud bu wellesley babson). Extending the path (mit amherst hahvud bu wellesley princeton). Extending the path (mit amherst hahvud bu wellesley penn). Extending the path (mit amherst hahvud wellesley bu mt-holyoke). Extending the path (mit amherst hahvud wellesley babson umass-amherst). Extending the path (mit amherst hahvud wellesley babson princeton). Extending the path (mit amherst hahvud wellesley babson penn). Extending the path (mit amherst hahvud wellesley babson tenn). Extending the path (mit amherst hahvud wellesley princeton babson). Extending the path (mit amherst hahvud wellesley princeton penn). Extending the path (mit amherst hahvud wellesley princeton ga-tech). Extending the path (mit amherst hahvud wellesley princeton tenn). Extending the path (mit amherst hahvud wellesley penn babson). Extending the path (mit amherst hahvud wellesley penn umass-amherst). Extending the path (mit amherst hahvud wellesley penn princeton). Extending the path (mit amherst hahvud wellesley penn tenn). Extending the path (mit amherst hahvud wellesley penn urbana). Extending the path (mit bu mt-holyoke smith amherst dartmouth). Extending the path (mit bu mt-holyoke smith amherst hahvud). Extending the path (mit bu mt-holyoke amherst hahvud wellesley). Extending the path (mit bu amherst hahvud wellesley babson). Extending the path (mit bu amherst hahvud wellesley princeton). Extending the path (mit bu amherst hahvud wellesley penn). Extending the path (mit bu hahvud amherst smith mt-holyoke). Extending the path (mit bu hahvud amherst mt-holyoke smith). Extending the path (mit bu hahvud wellesley babson umass-amherst). Extending the path (mit bu hahvud wellesley babson princeton). Extending the path (mit bu hahvud wellesley babson penn). Extending the path (mit bu hahvud wellesley babson tenn). Extending the path (mit bu hahvud wellesley princeton babson). Extending the path (mit bu hahvud wellesley princeton penn). Extending the path (mit bu hahvud wellesley princeton ga-tech). Extending the path (mit bu hahvud wellesley princeton tenn). Extending the path (mit bu hahvud wellesley penn babson). Extending the path (mit bu hahvud wellesley penn umass-amherst). Extending the path (mit bu hahvud wellesley penn princeton). Extending the path (mit bu hahvud wellesley penn tenn). Extending the path (mit bu hahvud wellesley penn urbana). Extending the path (mit bu wellesley hahvud amherst dartmouth). Extending the path (mit bu wellesley hahvud amherst smith). Extending the path (mit bu wellesley hahvud amherst mt-holyoke). Extending the path (mit bu wellesley babson umass-amherst penn). Extending the path (mit bu wellesley babson princeton penn). Extending the path (mit bu wellesley babson princeton ga-tech). Extending the path (mit bu wellesley babson princeton tenn). Extending the path (mit bu wellesley babson penn umass-amherst). Extending the path (mit bu wellesley babson penn princeton). Extending the path (mit bu wellesley babson penn tenn). Extending the path (mit bu wellesley babson penn urbana). Extending the path (mit bu wellesley babson tenn princeton). Extending the path (mit bu wellesley babson tenn penn). Extending the path (mit bu wellesley babson tenn ga-tech). Extending the path (mit bu wellesley babson tenn urbana). Extending the path (mit bu wellesley princeton babson umass-amherst). Extending the path (mit bu wellesley princeton babson penn). Extending the path (mit bu wellesley princeton babson tenn). Extending the path (mit bu wellesley princeton penn babson). Extending the path (mit bu wellesley princeton penn umass-amherst). Extending the path (mit bu wellesley princeton penn tenn). Extending the path (mit bu wellesley princeton penn urbana). Extending the path (mit bu wellesley princeton ga-tech tenn). Extending the path (mit bu wellesley princeton ga-tech chicago). Extending the path (mit bu wellesley princeton tenn babson). Extending the path (mit bu wellesley princeton tenn penn). Extending the path (mit bu wellesley princeton tenn ga-tech). Extending the path (mit bu wellesley princeton tenn urbana). Extending the path (mit bu wellesley penn babson umass-amherst). Extending the path (mit bu wellesley penn babson princeton). Extending the path (mit bu wellesley penn babson tenn). Extending the path (mit bu wellesley penn umass-amherst babson). Extending the path (mit bu wellesley penn princeton babson). Extending the path (mit bu wellesley penn princeton ga-tech). Extending the path (mit bu wellesley penn princeton tenn). Extending the path (mit bu wellesley penn tenn babson). Extending the path (mit bu wellesley penn tenn princeton). Extending the path (mit bu wellesley penn tenn ga-tech). Extending the path (mit bu wellesley penn tenn urbana). Extending the path (mit bu wellesley penn urbana tenn). Extending the path (mit hahvud amherst smith mt-holyoke bu). Extending the path (mit hahvud amherst mt-holyoke bu wellesley). Extending the path (mit hahvud amherst bu mt-holyoke smith). Extending the path (mit hahvud amherst bu wellesley babson). Extending the path (mit hahvud amherst bu wellesley princeton). Extending the path (mit hahvud amherst bu wellesley penn). Extending the path (mit hahvud bu mt-holyoke smith amherst). Extending the path (mit hahvud bu mt-holyoke amherst dartmouth). Extending the path (mit hahvud bu mt-holyoke amherst smith). Extending the path (mit hahvud bu amherst smith mt-holyoke). Extending the path (mit hahvud bu amherst mt-holyoke smith). Extending the path (mit hahvud bu wellesley babson umass-amherst). Extending the path (mit hahvud bu wellesley babson princeton). Extending the path (mit hahvud bu wellesley babson penn). Extending the path (mit hahvud bu wellesley babson tenn). Extending the path (mit hahvud bu wellesley princeton babson). Extending the path (mit hahvud bu wellesley princeton penn). Extending the path (mit hahvud bu wellesley princeton ga-tech). Extending the path (mit hahvud bu wellesley princeton tenn). Extending the path (mit hahvud bu wellesley penn babson). Extending the path (mit hahvud bu wellesley penn umass-amherst). Extending the path (mit hahvud bu wellesley penn princeton). Extending the path (mit hahvud bu wellesley penn tenn). Extending the path (mit hahvud bu wellesley penn urbana). Extending the path (mit hahvud wellesley bu mt-holyoke smith). Extending the path (mit hahvud wellesley bu mt-holyoke amherst). Extending the path (mit hahvud wellesley bu amherst dartmouth). Extending the path (mit hahvud wellesley bu amherst smith). Extending the path (mit hahvud wellesley bu amherst mt-holyoke). Extending the path (mit hahvud wellesley babson umass-amherst penn). Extending the path (mit hahvud wellesley babson princeton penn). Extending the path (mit hahvud wellesley babson princeton ga-tech). Extending the path (mit hahvud wellesley babson princeton tenn). Extending the path (mit hahvud wellesley babson penn umass-amherst). Extending the path (mit hahvud wellesley babson penn princeton). Extending the path (mit hahvud wellesley babson penn tenn). Extending the path (mit hahvud wellesley babson penn urbana). Extending the path (mit hahvud wellesley babson tenn princeton). Extending the path (mit hahvud wellesley babson tenn penn). Extending the path (mit hahvud wellesley babson tenn ga-tech). Extending the path (mit hahvud wellesley babson tenn urbana). Extending the path (mit hahvud wellesley princeton babson umass-amherst). Extending the path (mit hahvud wellesley princeton babson penn). Extending the path (mit hahvud wellesley princeton babson tenn). Extending the path (mit hahvud wellesley princeton penn babson). Extending the path (mit hahvud wellesley princeton penn umass-amherst). Extending the path (mit hahvud wellesley princeton penn tenn). Extending the path (mit hahvud wellesley princeton penn urbana). Extending the path (mit hahvud wellesley princeton ga-tech tenn). Extending the path (mit hahvud wellesley princeton ga-tech chicago). Extending the path (mit hahvud wellesley princeton tenn babson). Extending the path (mit hahvud wellesley princeton tenn penn). Extending the path (mit hahvud wellesley princeton tenn ga-tech). Extending the path (mit hahvud wellesley princeton tenn urbana). Extending the path (mit hahvud wellesley penn babson umass-amherst). Extending the path (mit hahvud wellesley penn babson princeton). Extending the path (mit hahvud wellesley penn babson tenn). Extending the path (mit hahvud wellesley penn umass-amherst babson). Extending the path (mit hahvud wellesley penn princeton babson). Extending the path (mit hahvud wellesley penn princeton ga-tech). Extending the path (mit hahvud wellesley penn princeton tenn). Extending the path (mit hahvud wellesley penn tenn babson). Extending the path (mit hahvud wellesley penn tenn princeton). Extending the path (mit hahvud wellesley penn tenn ga-tech). Extending the path (mit hahvud wellesley penn tenn urbana). Extending the path (mit hahvud wellesley penn urbana tenn). Extending the path (mit wellesley bu mt-holyoke smith amherst). Extending the path (mit wellesley bu mt-holyoke amherst dartmouth). Extending the path (mit wellesley bu mt-holyoke amherst smith). Extending the path (mit wellesley bu mt-holyoke amherst hahvud). Extending the path (mit wellesley bu amherst smith mt-holyoke). Extending the path (mit wellesley bu amherst mt-holyoke smith). Extending the path (mit wellesley bu hahvud amherst dartmouth). Extending the path (mit wellesley bu hahvud amherst smith). Extending the path (mit wellesley bu hahvud amherst mt-holyoke). Extending the path (mit wellesley hahvud amherst smith mt-holyoke). Extending the path (mit wellesley hahvud amherst mt-holyoke smith). Extending the path (mit wellesley hahvud amherst mt-holyoke bu). Extending the path (mit wellesley hahvud amherst bu mt-holyoke). Extending the path (mit wellesley hahvud bu mt-holyoke smith). Extending the path (mit wellesley hahvud bu mt-holyoke amherst). Extending the path (mit wellesley hahvud bu amherst dartmouth). Extending the path (mit wellesley hahvud bu amherst smith). Extending the path (mit wellesley hahvud bu amherst mt-holyoke). Extending the path (mit wellesley babson umass-amherst penn princeton). Extending the path (mit wellesley babson umass-amherst penn tenn). Extending the path (mit wellesley babson umass-amherst penn urbana). Extending the path (mit wellesley babson princeton penn umass-amherst). Extending the path (mit wellesley babson princeton penn tenn). Extending the path (mit wellesley babson princeton penn urbana). Extending the path (mit wellesley babson princeton ga-tech tenn). Extending the path (mit wellesley babson princeton ga-tech chicago). Extending the path (mit wellesley babson princeton tenn penn). Extending the path (mit wellesley babson princeton tenn ga-tech). Extending the path (mit wellesley babson princeton tenn urbana). Extending the path (mit wellesley babson penn princeton ga-tech). Extending the path (mit wellesley babson penn princeton tenn). Extending the path (mit wellesley babson penn tenn princeton). Extending the path (mit wellesley babson penn tenn ga-tech). Extending the path (mit wellesley babson penn tenn urbana). Extending the path (mit wellesley babson penn urbana tenn). Extending the path (mit wellesley babson tenn princeton penn). Extending the path (mit wellesley babson tenn princeton ga-tech). Extending the path (mit wellesley babson tenn penn umass-amherst). Extending the path (mit wellesley babson tenn penn princeton). Extending the path (mit wellesley babson tenn penn urbana). Extending the path (mit wellesley babson tenn ga-tech princeton). Extending the path (mit wellesley babson tenn ga-tech chicago). Extending the path (mit wellesley babson tenn urbana penn). Extending the path (mit wellesley princeton babson umass-amherst penn). Extending the path (mit wellesley princeton babson penn umass-amherst). Extending the path (mit wellesley princeton babson penn tenn). Extending the path (mit wellesley princeton babson penn urbana). Extending the path (mit wellesley princeton babson tenn penn). Extending the path (mit wellesley princeton babson tenn ga-tech). Extending the path (mit wellesley princeton babson tenn urbana). Extending the path (mit wellesley princeton penn babson umass-amherst). Extending the path (mit wellesley princeton penn babson tenn). Extending the path (mit wellesley princeton penn umass-amherst babson). Extending the path (mit wellesley princeton penn tenn babson). Extending the path (mit wellesley princeton penn tenn ga-tech). Extending the path (mit wellesley princeton penn tenn urbana). Extending the path (mit wellesley princeton penn urbana tenn). Extending the path (mit wellesley princeton ga-tech tenn babson). Extending the path (mit wellesley princeton ga-tech tenn penn). Extending the path (mit wellesley princeton ga-tech tenn urbana). Extending the path (mit wellesley princeton ga-tech chicago columbia). Final path length is 6 Proceed from mit to wellesley then from wellesley to princeton then from princeton to ga-tech then from ga-tech to chicago then from chicago to cmu. ;Value 10: ((cmu chicago ga-tech princeton wellesley mit)) ; David Golombek ; 6.034 pset #4 4) (define (best-first originhost destnhost) " Purpose: Perform best-first search Remark: Uses generalized search function " (define (combine-paths new-paths old-paths finish) " Purpose: Define a queue constructor specific to best-first search; add the best looking paths to the front " ; sort list based on how close the first host is to the ; destination host (sort (append new-paths old-paths) (lambda (path1 path2) (< (straight-line-distance (first-host path1) finish) (straight-line-distance (first-host path2) finish)))) ) ;; Fire up generalized search using queue constructor defined above: (generalized-search originhost destnhost (make-finish-test destnhost) combine-paths 1 extend-path)) 1 ]=> (best-first 'mit 'cmu) Extending the path (mit). Extending the path (mit wellesley). Extending the path (mit wellesley princeton). Extending the path (mit wellesley princeton ga-tech). Extending the path (mit wellesley princeton ga-tech chicago). Final path length is 6 Proceed from mit to wellesley then from wellesley to princeton then from princeton to ga-tech then from ga-tech to chicago then from chicago to cmu. ;Value 19: ((cmu chicago ga-tech princeton wellesley mit)) ; David Golombek ; 6.034 pset #4 5A) (define (best-first-hopcount originhost destnhost) " Purpose: Perform best-first-hopcount search Remark: Uses generalized search function " (define (combine-paths new-paths old-paths finish) " Purpose: Define a queue constructor specific to best-first-hopcount search; add the shortest paths to the front " ; sort paths based on length (sort (append new-paths old-paths) (lambda (path1 path2) (< (length path1) (length path2)))) ) ;; Fire up generalized search using queue constructor defined above: (generalized-search originhost destnhost (make-finish-test destnhost) combine-paths 1 extend-path)) 1 ]=> (best-first-hopcount 'mit 'cmu) Extending the path (mit). Extending the path (mit hahvud). Extending the path (mit amherst). Extending the path (mit bu). Extending the path (mit mt-holyoke). Extending the path (mit wellesley). Extending the path (mit amherst dartmouth). Extending the path (mit hahvud amherst). Extending the path (mit amherst mt-holyoke). Extending the path (mit wellesley princeton). Extending the path (mit wellesley penn). Extending the path (mit mt-holyoke smith). Extending the path (mit wellesley hahvud). Extending the path (mit wellesley bu). Extending the path (mit amherst bu). Extending the path (mit bu hahvud). Extending the path (mit amherst hahvud). Extending the path (mit mt-holyoke amherst). Extending the path (mit mt-holyoke bu). Extending the path (mit hahvud wellesley). Extending the path (mit bu amherst). Extending the path (mit wellesley babson). Extending the path (mit amherst smith). Extending the path (mit bu wellesley). Extending the path (mit hahvud bu). Extending the path (mit bu mt-holyoke). Extending the path (mit bu wellesley princeton). Extending the path (mit amherst bu wellesley). Extending the path (mit wellesley bu hahvud). Extending the path (mit hahvud wellesley princeton). Extending the path (mit bu hahvud amherst). Extending the path (mit wellesley princeton tenn). Extending the path (mit amherst bu mt-holyoke). Extending the path (mit hahvud bu wellesley). Extending the path (mit amherst hahvud wellesley). Extending the path (mit bu wellesley babson). Extending the path (mit wellesley princeton babson). Extending the path (mit bu wellesley penn). Extending the path (mit bu mt-holyoke smith). Extending the path (mit wellesley bu amherst). Extending the path (mit hahvud amherst dartmouth). Extending the path (mit wellesley penn urbana). Extending the path (mit amherst bu hahvud). Extending the path (mit hahvud wellesley babson). Extending the path (mit hahvud amherst smith). Extending the path (mit bu amherst mt-holyoke). Extending the path (mit wellesley babson tenn). Extending the path (mit wellesley bu mt-holyoke). Extending the path (mit wellesley babson princeton). Extending the path (mit wellesley penn tenn). Extending the path (mit amherst mt-holyoke bu). Extending the path (mit wellesley hahvud bu). Extending the path (mit hahvud amherst bu). Extending the path (mit wellesley princeton penn). Extending the path (mit hahvud amherst mt-holyoke). Extending the path (mit bu mt-holyoke amherst). Extending the path (mit amherst smith mt-holyoke). Extending the path (mit mt-holyoke amherst dartmouth). Extending the path (mit mt-holyoke smith amherst). Extending the path (mit wellesley penn umass-amherst). Extending the path (mit wellesley babson umass-amherst). Extending the path (mit wellesley babson penn). Extending the path (mit amherst hahvud bu). Extending the path (mit mt-holyoke bu amherst). Extending the path (mit wellesley princeton ga-tech). Extending the path (mit hahvud wellesley penn). Extending the path (mit bu amherst hahvud). Extending the path (mit bu amherst dartmouth). Extending the path (mit mt-holyoke amherst bu). Extending the path (mit hahvud wellesley bu). Extending the path (mit bu wellesley hahvud). Extending the path (mit wellesley penn babson). Extending the path (mit bu amherst smith). Extending the path (mit mt-holyoke amherst smith). Extending the path (mit amherst mt-holyoke smith). Extending the path (mit hahvud bu mt-holyoke). Extending the path (mit hahvud bu amherst). Extending the path (mit wellesley penn princeton). Extending the path (mit mt-holyoke bu hahvud). Extending the path (mit bu hahvud wellesley). Extending the path (mit mt-holyoke bu wellesley). Extending the path (mit wellesley hahvud amherst). Extending the path (mit mt-holyoke amherst hahvud). Extending the path (mit wellesley princeton penn babson). Extending the path (mit hahvud wellesley babson umass-amherst). Extending the path (mit wellesley babson princeton ga-tech). Extending the path (mit hahvud wellesley penn tenn). Extending the path (mit hahvud bu amherst dartmouth). Extending the path (mit wellesley babson penn tenn). Extending the path (mit bu hahvud amherst dartmouth). Extending the path (mit hahvud wellesley princeton penn). Extending the path (mit wellesley hahvud amherst dartmouth). Extending the path (mit wellesley penn babson tenn). Extending the path (mit mt-holyoke bu wellesley hahvud). Extending the path (mit bu hahvud amherst smith). Extending the path (mit bu wellesley hahvud amherst). Extending the path (mit hahvud bu mt-holyoke amherst). Extending the path (mit bu wellesley princeton babson). Extending the path (mit mt-holyoke amherst bu wellesley). Extending the path (mit wellesley bu mt-holyoke amherst). Extending the path (mit hahvud wellesley babson penn). Extending the path (mit wellesley babson umass-amherst penn). Extending the path (mit wellesley bu amherst mt-holyoke). Extending the path (mit wellesley penn tenn babson). Extending the path (mit wellesley penn princeton babson). Extending the path (mit bu amherst hahvud wellesley). Extending the path (mit amherst mt-holyoke bu wellesley). Extending the path (mit wellesley penn tenn ga-tech). Extending the path (mit hahvud wellesley princeton tenn). Extending the path (mit wellesley babson tenn penn). Extending the path (mit wellesley penn tenn urbana). Extending the path (mit hahvud wellesley babson princeton). Extending the path (mit wellesley penn umass-amherst babson). Extending the path (mit mt-holyoke amherst hahvud wellesley). Extending the path (mit wellesley hahvud amherst mt-holyoke). Extending the path (mit wellesley hahvud bu amherst). Extending the path (mit bu wellesley babson princeton). Extending the path (mit amherst mt-holyoke bu hahvud). Extending the path (mit mt-holyoke bu amherst hahvud). Extending the path (mit hahvud wellesley penn babson). Extending the path (mit wellesley bu hahvud amherst). Extending the path (mit wellesley princeton tenn penn). Extending the path (mit mt-holyoke smith amherst hahvud). Extending the path (mit mt-holyoke bu amherst smith). Extending the path (mit amherst hahvud wellesley penn). Extending the path (mit bu wellesley penn urbana). Extending the path (mit amherst hahvud wellesley princeton). Extending the path (mit bu hahvud wellesley penn). Extending the path (mit wellesley babson tenn princeton). Extending the path (mit bu mt-holyoke smith amherst). Extending the path (mit hahvud bu mt-holyoke smith). Extending the path (mit mt-holyoke bu wellesley penn). Extending the path (mit mt-holyoke bu amherst dartmouth). Extending the path (mit hahvud amherst bu wellesley). Extending the path (mit wellesley princeton ga-tech tenn). Extending the path (mit bu hahvud wellesley princeton). Extending the path (mit wellesley princeton tenn urbana). Extending the path (mit mt-holyoke bu wellesley babson). Extending the path (mit wellesley babson penn princeton). Extending the path (mit amherst bu wellesley babson). Extending the path (mit wellesley princeton tenn ga-tech). Extending the path (mit wellesley penn princeton ga-tech). Extending the path (mit hahvud wellesley babson tenn). Extending the path (mit wellesley hahvud bu mt-holyoke). Extending the path (mit bu wellesley penn babson). Extending the path (mit amherst hahvud bu wellesley). Extending the path (mit wellesley penn princeton tenn). Extending the path (mit amherst smith mt-holyoke bu). Extending the path (mit wellesley princeton babson penn). Extending the path (mit mt-holyoke smith amherst bu). Extending the path (mit hahvud amherst mt-holyoke smith). Extending the path (mit amherst bu hahvud wellesley). Extending the path (mit wellesley penn urbana tenn). Extending the path (mit bu hahvud amherst mt-holyoke). Extending the path (mit wellesley babson penn urbana). Extending the path (mit hahvud bu wellesley babson). Extending the path (mit hahvud wellesley bu amherst). Extending the path (mit bu wellesley penn umass-amherst). Extending the path (mit bu wellesley penn princeton). Extending the path (mit hahvud wellesley penn umass-amherst). Extending the path (mit bu mt-holyoke amherst hahvud). Extending the path (mit hahvud wellesley princeton ga-tech). Extending the path (mit mt-holyoke amherst hahvud bu). Extending the path (mit hahvud wellesley bu mt-holyoke). Extending the path (mit bu hahvud wellesley babson). Extending the path (mit bu mt-holyoke amherst smith). Extending the path (mit wellesley princeton penn tenn). Extending the path (mit wellesley penn babson princeton). Extending the path (mit mt-holyoke bu wellesley princeton). Extending the path (mit wellesley bu amherst smith). Extending the path (mit hahvud bu wellesley princeton). Extending the path (mit amherst bu wellesley penn). Extending the path (mit amherst hahvud bu mt-holyoke). Extending the path (mit wellesley hahvud amherst smith). Extending the path (mit hahvud amherst smith mt-holyoke). Extending the path (mit hahvud wellesley penn urbana). Extending the path (mit amherst bu wellesley princeton). Extending the path (mit hahvud bu amherst mt-holyoke). Extending the path (mit bu wellesley babson penn). Extending the path (mit wellesley bu amherst dartmouth). Extending the path (mit amherst hahvud wellesley babson). Extending the path (mit bu wellesley princeton tenn). Extending the path (mit hahvud bu wellesley penn). Extending the path (mit wellesley princeton babson umass-amherst). Extending the path (mit wellesley babson penn umass-amherst). Extending the path (mit hahvud amherst mt-holyoke bu). Extending the path (mit bu amherst mt-holyoke smith). Extending the path (mit mt-holyoke bu hahvud wellesley). Extending the path (mit bu mt-holyoke amherst dartmouth). Extending the path (mit wellesley penn babson umass-amherst). Extending the path (mit hahvud wellesley princeton babson). Extending the path (mit wellesley princeton tenn babson). Extending the path (mit bu amherst smith mt-holyoke). Extending the path (mit wellesley bu mt-holyoke smith). Extending the path (mit wellesley princeton penn umass-amherst). Extending the path (mit wellesley princeton babson tenn). Extending the path (mit bu wellesley penn tenn). Extending the path (mit wellesley babson tenn ga-tech). Extending the path (mit mt-holyoke smith amherst dartmouth). Extending the path (mit hahvud wellesley penn princeton). Extending the path (mit wellesley babson princeton penn). Extending the path (mit wellesley hahvud amherst bu). Extending the path (mit amherst bu mt-holyoke smith). Extending the path (mit wellesley penn tenn princeton). Extending the path (mit mt-holyoke amherst bu hahvud). Extending the path (mit bu wellesley princeton penn). Extending the path (mit wellesley bu amherst hahvud). Extending the path (mit wellesley babson princeton tenn). Extending the path (mit wellesley babson tenn urbana). Extending the path (mit amherst bu wellesley hahvud). Extending the path (mit bu wellesley babson umass-amherst). Extending the path (mit amherst hahvud wellesley bu). Extending the path (mit wellesley princeton penn urbana). Extending the path (mit bu wellesley babson tenn). Extending the path (mit hahvud bu amherst smith). Extending the path (mit hahvud amherst bu mt-holyoke). Extending the path (mit bu wellesley princeton ga-tech). Extending the path (mit wellesley princeton ga-tech chicago). Extending the path (mit mt-holyoke bu hahvud amherst). Extending the path (mit hahvud amherst mt-holyoke bu wellesley). Extending the path (mit hahvud wellesley princeton penn umass-amherst). Extending the path (mit hahvud amherst bu wellesley princeton). Extending the path (mit amherst bu wellesley penn umass-amherst). Extending the path (mit wellesley bu hahvud amherst mt-holyoke). Extending the path (mit hahvud wellesley princeton penn tenn). Extending the path (mit amherst bu wellesley babson umass-amherst). Extending the path (mit hahvud wellesley princeton tenn penn). Extending the path (mit wellesley princeton babson penn umass-amherst). Extending the path (mit amherst hahvud bu wellesley princeton). Extending the path (mit wellesley princeton tenn ga-tech chicago). Extending the path (mit wellesley babson tenn penn princeton). Extending the path (mit mt-holyoke amherst hahvud wellesley penn). Extending the path (mit hahvud wellesley penn princeton babson). Extending the path (mit hahvud wellesley penn tenn urbana). Extending the path (mit wellesley penn tenn princeton ga-tech). Extending the path (mit mt-holyoke bu wellesley princeton ga-tech). Extending the path (mit wellesley penn umass-amherst babson princeton). Extending the path (mit bu hahvud wellesley princeton babson). Extending the path (mit wellesley princeton babson tenn penn). Extending the path (mit hahvud wellesley princeton babson tenn). Extending the path (mit wellesley princeton penn urbana tenn). Extending the path (mit hahvud wellesley bu mt-holyoke amherst). Extending the path (mit amherst hahvud wellesley babson penn). Extending the path (mit bu mt-holyoke smith amherst hahvud). Extending the path (mit wellesley princeton penn babson tenn). Extending the path (mit hahvud wellesley princeton tenn urbana). Extending the path (mit bu wellesley penn urbana tenn). Extending the path (mit hahvud wellesley babson penn umass-amherst). Extending the path (mit wellesley babson princeton ga-tech chicago). Extending the path (mit hahvud bu wellesley babson penn). Extending the path (mit wellesley princeton ga-tech tenn babson). Extending the path (mit wellesley princeton ga-tech chicago columbia). Extending the path (mit hahvud bu amherst smith mt-holyoke). Extending the path (mit hahvud wellesley babson penn tenn). Extending the path (mit hahvud wellesley bu mt-holyoke smith). Extending the path (mit hahvud wellesley penn princeton tenn). Extending the path (mit wellesley princeton penn tenn urbana). Extending the path (mit hahvud bu wellesley princeton ga-tech). Extending the path (mit mt-holyoke smith amherst hahvud bu). Extending the path (mit wellesley princeton babson penn urbana). Extending the path (mit hahvud wellesley babson penn urbana). Extending the path (mit hahvud bu wellesley princeton penn). Extending the path (mit hahvud bu mt-holyoke amherst smith). Extending the path (mit amherst bu wellesley penn urbana). Extending the path (mit bu wellesley princeton babson tenn). Extending the path (mit hahvud bu wellesley princeton babson). Extending the path (mit hahvud wellesley princeton ga-tech tenn). Extending the path (mit mt-holyoke bu wellesley penn urbana). Extending the path (mit wellesley bu amherst mt-holyoke smith). Extending the path (mit hahvud wellesley bu amherst dartmouth). Extending the path (mit amherst smith mt-holyoke bu hahvud). Extending the path (mit mt-holyoke bu wellesley penn babson). Extending the path (mit wellesley babson penn princeton tenn). Extending the path (mit mt-holyoke bu hahvud wellesley penn). Extending the path (mit amherst hahvud wellesley princeton tenn). Extending the path (mit hahvud wellesley penn umass-amherst babson). Extending the path (mit mt-holyoke bu wellesley penn princeton). Extending the path (mit wellesley penn babson tenn urbana). Extending the path (mit amherst bu wellesley penn tenn). Extending the path (mit wellesley penn babson princeton ga-tech). Extending the path (mit mt-holyoke smith amherst hahvud wellesley). Extending the path (mit bu wellesley babson princeton tenn). Extending the path (mit wellesley babson princeton penn urbana). Extending the path (mit wellesley princeton penn babson umass-amherst). Extending the path (mit mt-holyoke bu hahvud wellesley princeton). Extending the path (mit wellesley princeton tenn penn urbana). Extending the path (mit wellesley penn urbana tenn babson). Extending the path (mit mt-holyoke bu wellesley penn tenn). Extending the path (mit wellesley babson princeton penn umass-amherst). Extending the path (mit wellesley princeton ga-tech chicago byu). Extending the path (mit amherst hahvud bu wellesley babson). Extending the path (mit wellesley princeton tenn penn babson). Extending the path (mit amherst hahvud wellesley babson tenn). Extending the path (mit wellesley babson tenn ga-tech princeton). Extending the path (mit wellesley penn tenn babson umass-amherst). Extending the path (mit wellesley hahvud amherst smith mt-holyoke). Extending the path (mit hahvud wellesley babson princeton ga-tech). Extending the path (mit bu wellesley princeton penn umass-amherst). Extending the path (mit hahvud wellesley penn tenn ga-tech). Extending the path (mit bu amherst hahvud wellesley babson). Extending the path (mit wellesley penn princeton tenn urbana). Extending the path (mit mt-holyoke bu hahvud amherst smith). Extending the path (mit hahvud wellesley princeton penn urbana). Extending the path (mit wellesley babson tenn penn urbana). Extending the path (mit amherst bu hahvud wellesley princeton). Extending the path (mit amherst bu wellesley princeton tenn). Extending the path (mit amherst mt-holyoke bu wellesley babson). Extending the path (mit hahvud wellesley princeton babson umass-amherst). Extending the path (mit wellesley babson princeton tenn ga-tech). Extending the path (mit wellesley princeton tenn penn umass-amherst). Extending the path (mit mt-holyoke bu wellesley babson umass-amherst). Extending the path (mit bu hahvud wellesley princeton ga-tech). Extending the path (mit hahvud bu wellesley penn babson). Extending the path (mit amherst hahvud wellesley princeton babson). Extending the path (mit amherst bu wellesley princeton penn). Extending the path (mit bu mt-holyoke smith amherst dartmouth). Extending the path (mit wellesley babson penn tenn princeton). Extending the path (mit bu wellesley hahvud amherst smith). Extending the path (mit mt-holyoke amherst bu hahvud wellesley). Extending the path (mit wellesley penn urbana tenn princeton). Extending the path (mit mt-holyoke amherst hahvud wellesley bu). Extending the path (mit wellesley penn urbana tenn ga-tech). Extending the path (mit hahvud wellesley babson penn princeton). Extending the path (mit wellesley penn princeton tenn babson). Extending the path (mit wellesley babson umass-amherst penn urbana). Extending the path (mit mt-holyoke amherst hahvud wellesley princeton). Extending the path (mit bu hahvud wellesley babson princeton). Extending the path (mit bu hahvud wellesley penn babson). Extending the path (mit wellesley penn babson tenn ga-tech). Extending the path (mit hahvud wellesley princeton tenn babson). Extending the path (mit mt-holyoke amherst bu wellesley princeton). Extending the path (mit amherst hahvud wellesley penn tenn). Extending the path (mit bu wellesley princeton penn tenn). Extending the path (mit hahvud wellesley babson princeton tenn). Extending the path (mit hahvud bu wellesley penn princeton). Extending the path (mit wellesley penn princeton babson tenn). Extending the path (mit mt-holyoke amherst bu wellesley hahvud). Extending the path (mit wellesley princeton penn umass-amherst babson). Extending the path (mit mt-holyoke bu wellesley babson princeton). Extending the path (mit mt-holyoke smith amherst bu wellesley). Extending the path (mit mt-holyoke bu wellesley princeton penn). Extending the path (mit wellesley penn princeton ga-tech chicago). Extending the path (mit mt-holyoke bu wellesley princeton tenn). Extending the path (mit bu amherst hahvud wellesley penn). Extending the path (mit amherst bu wellesley penn princeton). Extending the path (mit amherst hahvud wellesley penn urbana). Extending the path (mit bu wellesley princeton tenn urbana). Extending the path (mit wellesley babson tenn ga-tech chicago). Extending the path (mit bu wellesley babson umass-amherst penn). Extending the path (mit wellesley penn princeton ga-tech tenn). Extending the path (mit bu wellesley princeton penn babson). Extending the path (mit hahvud bu wellesley princeton tenn). Extending the path (mit amherst hahvud wellesley princeton penn). Extending the path (mit wellesley princeton ga-tech tenn urbana). Extending the path (mit bu hahvud wellesley penn princeton). Extending the path (mit wellesley babson tenn penn umass-amherst). Extending the path (mit wellesley princeton ga-tech chicago indiana). Extending the path (mit wellesley hahvud amherst mt-holyoke smith). Extending the path (mit bu wellesley hahvud amherst mt-holyoke). Extending the path (mit bu wellesley babson penn princeton). Extending the path (mit hahvud wellesley penn tenn princeton). Extending the path (mit hahvud wellesley princeton tenn ga-tech). Extending the path (mit mt-holyoke smith amherst bu hahvud). Extending the path (mit bu wellesley penn babson tenn). Extending the path (mit amherst smith mt-holyoke bu wellesley). Extending the path (mit wellesley babson penn urbana tenn). Extending the path (mit amherst hahvud wellesley babson princeton). Extending the path (mit wellesley princeton ga-tech tenn penn). Extending the path (mit amherst hahvud bu mt-holyoke smith). Extending the path (mit wellesley bu mt-holyoke amherst dartmouth). Extending the path (mit hahvud wellesley babson tenn princeton). Extending the path (mit mt-holyoke bu hahvud amherst dartmouth). Extending the path (mit wellesley babson tenn urbana penn). Extending the path (mit bu wellesley princeton tenn penn). Extending the path (mit bu hahvud wellesley penn tenn). Extending the path (mit hahvud wellesley penn tenn babson). Extending the path (mit bu wellesley penn princeton ga-tech). Extending the path (mit mt-holyoke amherst hahvud wellesley babson). Extending the path (mit amherst mt-holyoke bu wellesley penn). Extending the path (mit bu wellesley babson princeton ga-tech). Extending the path (mit amherst hahvud wellesley penn princeton). Extending the path (mit bu wellesley princeton babson umass-amherst). Extending the path (mit hahvud wellesley babson tenn ga-tech). Extending the path (mit hahvud amherst bu wellesley penn). Extending the path (mit hahvud bu wellesley babson princeton). Extending the path (mit wellesley hahvud bu mt-holyoke amherst). Extending the path (mit bu wellesley penn tenn babson). Extending the path (mit bu wellesley hahvud amherst dartmouth). Extending the path (mit wellesley bu mt-holyoke amherst hahvud). Extending the path (mit hahvud bu wellesley penn urbana). Extending the path (mit amherst mt-holyoke bu wellesley princeton). Extending the path (mit amherst bu hahvud wellesley penn). Extending the path (mit bu hahvud wellesley babson penn). Extending the path (mit mt-holyoke bu wellesley hahvud amherst). Extending the path (mit hahvud wellesley princeton penn babson). Extending the path (mit bu wellesley princeton penn urbana). Extending the path (mit bu mt-holyoke amherst hahvud wellesley). Extending the path (mit amherst bu wellesley babson tenn). Extending the path (mit amherst bu wellesley princeton babson). Extending the path (mit bu hahvud wellesley babson umass-amherst). Extending the path (mit wellesley hahvud bu mt-holyoke smith). Extending the path (mit amherst mt-holyoke bu hahvud wellesley). Extending the path (mit amherst hahvud wellesley penn umass-amherst). Extending the path (mit wellesley penn tenn princeton babson). Extending the path (mit bu hahvud wellesley princeton tenn). Extending the path (mit wellesley bu amherst smith mt-holyoke). Extending the path (mit wellesley babson penn princeton ga-tech). Extending the path (mit hahvud wellesley bu amherst smith). Extending the path (mit bu wellesley babson penn umass-amherst). Extending the path (mit bu wellesley babson princeton penn). Extending the path (mit mt-holyoke bu wellesley princeton babson). Extending the path (mit wellesley princeton babson umass-amherst penn). Extending the path (mit wellesley princeton babson tenn urbana). Extending the path (mit wellesley penn tenn ga-tech chicago). Extending the path (mit hahvud wellesley bu amherst mt-holyoke). Extending the path (mit bu wellesley babson tenn penn). Extending the path (mit bu wellesley babson tenn urbana). Final path length is 6 Proceed from mit to wellesley then from wellesley to princeton then from princeton to ga-tech then from ga-tech to chicago then from chicago to cmu. ;Value 3: ((cmu chicago ga-tech princeton wellesley mit)) ; David Golombek ; 6.034 pset #4 5B) Best-first performs significantly better than best-first-hopcount because it's heuristic is much more sensible in this situation. Best-first does well because it is selecting on hosts that are closer to the destination. Best-first-hopcount is selecting almost at random, because the number of hops along a given path has no correlation to how far along you've traveled, much less how far towards the destination you've gone. 5C) Best-first-hopcount is essentially an implementation of branch-and-bound search, where the least-cost-paths are defined to be those with the fewest hosts along them. 5D) Best-first-hopcount is very similar to breadth-first search in that all paths are expanded to the same depth at each level. However, best-first-hopcount is doing a lot more work to determine the next path to search along, so it runs much more slowly than breadth-first. ; David Golombek ; 6.034 pset #4 6A) See attached 6B) (define (eval-premises patterns bindings) ;;; ;;; tries to see whether each premise of rule is true (ie assertion exists or rule ;;; can infer it) under the current accumulated set of bindings. ;;; This returns either #f or a list of one element (the bindings list). ;;; (if (null? patterns) ;; if we got to the end, return bindings ;; to avoid confusing () with #f, return a list of the bindings. (list bindings) ; sort patterns based on the number or rules that match them (let ((sorted-patterns (sort patterns (lambda (pattern1 pattern2) (< (count-rules pattern1) (count-rules pattern2)))))) ; then use the head of this sorted patterns list in eval-premise (let ((result (eval-premise (first sorted-patterns) bindings))) (if result (eval-premises (rest sorted-patterns) (first result)) #f))))) ; rules matching procedure -- for each rule in *rules*, see if it ; matches the given pattern, and if so increment count. (define (count-rules pattern) ;; Counts rules that match specified pattern. (let ((count 0)) (for-each (lambda (x) (let ((m (match pattern x))) (if (not (eq? m 'fail)) (set! count (+ count 1))))) *rules*) count)) 1 ]=> (backchain '(fred species is (? x))) Trying to establish whether (fred species is (? x)) with bindings (). Trying to establish (fred species is cheetah) using rule z9. Trying to establish whether ((? animal9) has tawny color) with bindings ((x cheetah) (animal9 fred)). Have no assertion or successful rule to determine whether (fred has tawny color). Is this true [y or n]? n Rule z9 fails to establish (fred species is cheetah). Trying to establish (fred species is tiger) using rule z10. Trying to establish whether ((? animal25) has tawny color) with bindings ((x tiger) (animal25 fred)). Have no assertion or successful rule to determine whether (fred has tawny color). Is this true [y or n]? n Rule z10 fails to establish (fred species is tiger). Trying to establish (fred species is giraffe) using rule z11. Trying to establish whether ((? animal41) has long legs) with bindings ((x giraffe) (animal41 fred)). Have no assertion or successful rule to determine whether (fred has long legs). Is this true [y or n]? y Trying to establish whether ((? animal41) has dark spots) with bindings ((x giraffe) (animal41 fred)). Have no assertion or successful rule to determine whether (fred has dark spots). Is this true [y or n]? y Trying to establish whether ((? animal41) has long neck) with bindings ((x giraffe) (animal41 fred)). Have no assertion or successful rule to determine whether (fred has long neck). Is this true [y or n]? y Trying to establish whether ((? animal41) class is ungulate) with bindings ((x giraffe) (animal41 fred)). Trying to establish (fred class is ungulate) using rule z7. Trying to establish whether ((? animal93) family is mammal) with bindings ((animal93 fred) (x giraffe) (animal41 fred)). Trying to establish (fred family is mammal) using rule z1. Trying to establish whether ((? animal94) has hair) with bindings ((animal94 fred) (animal93 fred) (x giraffe) (animal41 fred)). Have no assertion or successful rule to determine whether (fred has hair). Is this true [y or n]? y Rule z1 establishes (fred family is mammal). Trying to establish whether ((? animal93) has hoofs) with bindings ((animal94 fred) (animal93 fred) (x giraffe) (animal41 fred)). Have no assertion or successful rule to determine whether (fred has hoofs). Is this true [y or n]? y Rule z7 establishes (fred class is ungulate). Rule z11 establishes (fred species is giraffe). We have established that (fred species is giraffe). Final data base contents: (fred species is giraffe) (fred class is ungulate) (fred has hoofs) (fred family is mammal) (fred has hair) (fred has long neck) (fred has dark spots) (fred has long legs) ;No value