;;;  atree.scm    Dave Reed    10/04/04
;;;
;;;  Implements Algorithm A using tree representation of search (a-tree) 
;;;
;;;  The function assumes that the GET-MOVES function has been defined for 
;;;  a given state space:  (GET-MOVES state) returns a list of (state cost) 
;;;  pairs, representing all those reachable states from the given state and
;;;  the associated cost of each move.  
;;;
;;;  Also assumes H function has been defined: (H state goalState) returns 
;;;  estimated cost of reaching goalState from current state.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(require (lib "compat.ss"))


(define (a-tree startState goalState)
  
  (define (a-paths paths)
    (cond ((null? paths) #f)
          ((equal? (cadar paths) goalState) (car paths))
          (else (a-paths (sort better-path
                               (append (cdr paths)
                                       (extend-all (car paths) 
                                                   (GET-MOVES (cadar paths)))))))))
  
  (define (extend-all path nextStates)
    (cond ((null? nextStates) '())
          ((member (caar nextStates) path) (extend-all path (cdr nextStates)))
          (else (cons (cons (+ (car path) (cadar nextStates))
                            (cons (caar nextStates) (cdr path)))
                      (extend-all path (cdr nextStates))))))
  
  (define (better-path path1 path2)
    (< (+ (car path1) (H (cadr path1) goalState))
       (+ (car path2) (H (cadr path2) goalState))))
  
  (a-paths (list (list 0 startState))))