#|---------------------------------------------------------------------------- Artificial Intelligence, Second Edition Elaine Rich and Kevin Knight McGraw Hill, 1991 This code may be freely copied and used for educational or research purposes. All software written by Kevin Knight. Comments, bugs, improvements to knight@cs.cmu.edu ----------------------------------------------------------------------------|# #|---------------------------------------------------------------------------- HILL-CLIMBING SEARCH "hill.lisp" ----------------------------------------------------------------------------|# ;; Function HILL-CLIMBING performs steepest-ascent hill climbing search. ;; It either returns a solution path from start to goal, or it gets stuck ;; in a local minimum. This version of hill-climbing does not do any ;; backtracking to extricate itself from a local minimum -- it simply halts. (defun hill-climbing (start &optional verbose) (do ((current-state start) (solution-path (list start)) (minimum-reached nil)) (minimum-reached (if (goal-state? current-state) (nreverse solution-path) "Stuck in local-minimum.")) (when verbose (format t "Expanding state ~d~%" current-state)) (let* ((succs (expand current-state)) (best-succ (choose-best succs))) (cond ((< (heuristic best-succ) (heuristic current-state)) (setq current-state best-succ) (setq solution-path (cons current-state solution-path))) (t (setq minimum-reached t)))))) ;; Function CHOOSE-BEST returns the member of SUCCESSORS with the lowest ;; heuristic score, i.e., the state deemed closest to goal. (defun choose-best (successors) (do ((s successors (cdr s)) (best-succ nil) (best-score *infinity*)) ((null s) best-succ) (let ((succ (car s))) (when (< (heuristic succ) best-score) (setq best-succ succ) (setq best-score (heuristic succ))))))