;;;  heuristics.scm    Dave Reed    9/04/08
;;;
;;;  Implements the following informed search strategies for state spaces:
;;;    hill-climbing (hill-climb)
;;;    best first search (best)
;;;
;;;  These functions assume that the GET-MOVES function has been defined for 
;;;  a given state space:  (GET-MOVES state) returns a list of all new 
;;;  states reachable from state.
;;;
;;;  Also assumes HEURISTIC function has been defined: 
;;;  (HEURISTIC state goalState) returns heuristic estimate of how close
;;;  state is to goalState (higher value implies better/closer state).
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (hill-climb startState goalState)
  
  (define (climb-path path)
    (if (equal? (car path) goalState)
        path
        (let ((nextStates (sort (GET-MOVES (car path)) better-state )))
          (if (or (null? nextStates) (not (better-state (car nextStates) (car path))))
              #f
              (climb-path (cons (car nextStates) path))))))
  
  (define (better-state state1 state2)
    (> (HEURISTIC state1 goalState) (HEURISTIC state2 goalState)))
          
  (climb-path (list startState)))
  
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (best startState goalState)
  
  (define (best-paths paths)
    (cond ((null? paths) #f)
          ((equal? (caar paths) goalState) (car paths))
          (else (best-paths (sort (append (cdr paths)
                                          (extend-all (car paths) 
                                                      (GET-MOVES (caar paths))))
                                  better-path)))))
  
  (define (extend-all path nextStates)
    (cond ((null? nextStates) '())
          ((member (car nextStates) path) (extend-all path (cdr nextStates)))
          (else (cons (cons (car nextStates) path)
                      (extend-all path (cdr nextStates))))))
  
  (define (better-path path1 path2)
    (> (HEURISTIC (car path1) goalState) (HEURISTIC (car path2) goalState)))
  
  (best-paths (list (list startState))))