;                       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