; CSW 4701- Artificial Intelligence
; MORE Search Programs in LISP
;The UNIFORM COST SEARCH and the A* SEARCH are a bit more pensive
;about how they choose paths for exploration in searching for solutions.
;Both do so by maintaining total path costs in each node and choosing paths
;for expansion that have been found to be of minimal cost so far.
;A* adds to this information and estimated value of the cost of each path
;to a solution. Its the most "thoughtful".
;GREED is GREED, however. Grab any opportunity as soon as you can
whenever it arises irrespective of the past!
;What that principle in mind, the GREEDY search simplyl chooses paths
;for exploration based upon the simple startegy of pick the one with
;the minimal hhat value!
;Thus, for GREEDY SEARCH we update our node representation to be:
; (State Operator-name Parent-Node) ;note ghat is gone
;and include a new accessor function:
(Defun State (node) (first node))
(Defun Operator (node) (second node))
(Defun Parent (node) (third node))
;Now we can simply dispense with the cost function in the successor
;generating function
;Here is the greedy search algorithm in LISP
(defun greedy-search (s0 sg sons)
(let ( ( open (list (list s0 (hhat s0) nil) ));note the inner list is a node
( closed nil )
( n nil )
( daughters nil )) ;ok, here we go:
(loop
(if (null open) (return 'fail)) ;failure, oh well....
(setf n (pop open)) ;Ok, remove the first node
;and update open and
(push n closed) ;update closed with n since we expand it next
; Recall that we maintain open and closed lists so that we
; do not "loop" forever through the search space by visiting
; states we've previously explored. Here now we have to also
; concern ourselves with MAINTAINING THE MINIMAL COST PATHS WE FIND
; TO ANY STATE IN THE STATE SPACE.
(if (**equal** (state n) sg) ;have we found our goal state?
;remember (state n) = (first n)
;and **equal** has to be general
(let () ;OK...for free, I fixed this bug for you
(print "Great. I found a solution. Here it is:")
(return (trace-solution n)))) ;AND ITS THE MINIMAL COST SOLUTION
;GUARANTEED!!! TAKE IT TO THE BANK
(setf daughters (apply sons n)) ;here we generate new derived states
(setf daughters
(DIFF daughters closed)) ;Remove duplicate states
;previously explored and residing on closed. REMEMBER, THE
;NEW PATH TO THIS STATE THAT WE HAVE PREVIOUSLY EXPANDED MUST
;BE MORE EXPENSIVE SO WE JUST ELIMINATE IT FORM OUR CURRENT
;LIST OF DAUGHTER NODES.
;BUT NOW WE HAVE TO KEEP THE CHEAPEST DAUGHTER NODES ON OPEN
(setf open ;LOOK HERE...WE'RE SORTING THE OPEN LIST FROM MIN H-HAT TO MAX
(sort open
'(lambda(node1 node2) (< (h-hat node1) (h-hat node2))))) ;ends setf
;By taking the fist node off of OPEN, above in the loop, then
;we are assured of expanding the next cheapest path
) ;closes loop
) ;closes let
) ;closes defun