; 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