;Worksheet #4

;;This search procedure is called the "Best-First-Search"
;;Global variables: open_count, val, goal, closed, open, n, l
 
(setq open_count 0)
(setq val 0)
(defun bfs (start goal_node)
(setq goal goal_node)
      (setq closed nil)                            ;;Step 1
      (putprop start nil 'ptr)
      (putprop start (f start) 'fvalue)
      (setq open (list start))
      (loop (cond ((null open)(return 'failure)))  ;;Step 2
          (setq n (select_best open))              ;;Step 3 
          (setq open (delete n open))              ;;Step 4
          (setq closed (cons n closed))
          (if (eq n goal) (return(extract_path n)));;Step 5
          (setq l (get n 'adj))                    ;;Step 6
          (mapcar 'open_node (set_diff (set_diff l open) closed))
    )                                      ;;End of loop, Step 7
)                                         



(defun select_best (lst)                           ;;Step 3
   (cond ((eq (first lst) goal)(first lst))
         (T (better (first lst)(rest lst)))
   )
)

(defun better (elem lst)                           ;;Step 3
   (cond ((null lst) elem)
         ((< (get elem 'fvalue)(get (first lst) 'fvalue)) elem)
         ((eq (first lst) goal)(first lst))
         (T (better elem (rest lst)))
   )
)

(defun open_node (M)                       ;;Step 6
   (prog ()
     (setq open_count ( + 1 open_count))
     (putprop m (setq val (f m)) 'fvalue)
     (setq open (insert m open))
     (putprop m n 'ptr)
   )
)

(defun insert (node lst)                   ;;Step 6
    (cond ((null lst)(list node))
          ((< val (get (first lst) 'fvalue))(cons node lst))
          (T (cons (first lst)(insert node (rest lst))))
    )
)

(defun successors (node) (get node 'adj))

(defun putprop (s  v p)
  (setf (get s p) v)
)

(defun set_diff (ls1 ls2)
   (cond ((null ls1) nil)
         ((member (first ls1) ls2)(set_diff (rest ls1) ls2))
         (T (cons (first ls1)(set_diff (cdr ls1) ls2)))
   )
)

;the next two functions could easily be combined but the author wanted
;to make the fvalue property self explanatory
(defun longitude_diff(n1 n2)
    (abs (- (get n1 'lg)(get n2 'lg)))
)

(defun f(n)
    (longitude_diff n goal)
)

(defun extract_path (n)
  (cond ((null n) nil)
        (t (append (extract_path (get n 'ptr))
                                   (list n)))
  )
)

;lg stands for longitude.
;each city is paired with its longitude.
;notice how cleverly the mapcar effectively accomplishes 18 putprops
(mapcar #'(lambda(x) (putprop (first x)(first (rest x)) 'lg))
          '((av 48)(bord -6)(bre -45)(caen -4)(calais 18)
            (di 51)(gren 57)(lim 12)(ly 48)(mars 53)
            (mont 36)(nan -16)(ncy 62)(nice 73)(paris 23)
            (ren -17)(stras 77)(to 14))
)


;these putprops construct the graph. It is similar to Worksheet #3 except that
;the graph is much larger

(putprop 'bre '(ren) 'adj)
(putprop 'ren '(caen paris bre nan) 'adj)
(putprop 'caen '(calais paris ren) 'adj)
(putprop 'calais '(ncy paris caen) 'adj)
(putprop 'ncy '(stras di paris calais) 'adj)
(putprop 'stras '(di ncy) 'adj)
(putprop 'di '(stras ly paris ncy) 'adj)
(putprop 'ly '(gren av lim di) 'adj)
(putprop 'gren '(av ly) 'adj)
(putprop 'av '(gren mars mont ly) 'adj)
(putprop 'mars '(nice av) 'adj)
(putprop 'nice '(mars) 'adj)
(putprop 'mont '(av to) 'adj)
(putprop 'to '(mont bord lim) 'adj)
(putprop 'bord '(lim to nan) 'adj)
(putprop 'lim '(ly to bord nan paris) 'adj)
(putprop 'nan '(lim bord ren) 'adj)
(putprop 'paris '(calais ncy di lim ren caen) 'adj)

Here's the map for the French cities used in Best First search:
(See the best-first search algorithm below the map)

;;;   Best-First Search algorithm
;;;   1. Place the starting node, S, on OPEN, compute f(S), and associate
;;;      this value with S.  Associate a null pointer to S.
;;;   2. If OPEN is empty, return "Failure" and stop
;;;   3. Choose a node N from OPEN such that f(N) <= f(M) for each M on OPEN
;;;      and such that N is a goal node if any goal  node achieves that 
;;;      minimum f value.
;;;   4. Put N on closed and remove N from OPEN.  
;;;   5. If N is a goal node, return the path from S to N obtained by
;;;      tracing backward the pointers from N to S.  Then stop.
;;;   6. For each successor J of N that is not already on OPEN or on CLOSED:
;;;      a. Compute f(J) and associate it with J
;;;      b. Put J on OPEN
;;;      c. Associate a pointer with J pointing back to N
;;;   7. Go back to step 2