title: Lisp - Hill Climbing
body: <p>Ok I have a Lisp implementation of BFS that I am trying to convert to do a hill climbing search.  </p>
  
  <p>Here is what my BFS code looks like:</p>
  
  <pre><code>; The list of lists is the queue that we pass BFS.  the first entry and 
  ; every other entry in the queue is a list.  BFS uses each of these lists and 
  ; the path to search.  
  
  (defun shortest-path (start end net)   
    (BFS end (list (list start)) net))
  
  ;We pass BFS the end node, a queue containing the starting node and the graph 
  ;being searched(net)   
  
  (defun BFS (end queue net)
    (if (null queue) ;if the queue is empty BFS has not found a path so exit
        nil
        (expand-queue end (car queue) (cdr queue) net)))
  
  (defun expand-queue (end path queue net)
    (let ((node (car path)))
      (if (eql node end)   ; If the current node is the goal node then flip the path
                           ; and return that as the answer
          (reverse path)
          ; otherwise preform a new BFS search by appending the rest of 
          ; the current queue to the result of the new-paths function
          (BFS end (append queue (new-paths path node net)) net))))
  
  ; mapcar is called once for each member of the list new-paths is passed
  ; the results of this are collected into a list
  (defun new-paths (path node net)
    (mapcar #'(lambda (n) (cons n path))
           (cdr (assoc node net))))
  </code></pre>
  
  <p>Now, I know that instead of always expanding the left node as I do in the BFS I need to expand the node that seems closest to the goal state.<br>
  The graph I am using looks like this:</p>
  
  <pre><code>(a (b 3) (c 1))  
  (b (a 3) (d 1))
  </code></pre>
  
  <p>I have a conversion function to make this work with the above BFS implementation, but now I need to turn this into Hill climbing using this graph format.    </p>
  
  <p>I'm just not sure where to begin, and have been trying things to no avail.  I know I mainly need to change the <code>expand-queue</code> function to expand the closest node, but I can't seem to make a function to determine which node is closest.</p>
  
  <p>Thanks for the help!</p>