search - Lisp - Hill Climbing -

ok have lisp implementation of bfs trying convert hill climbing search.

here bfs code looks like:

; list of lists queue pass bfs.  first entry ,  ; every other entry in queue list.  bfs uses each of these lists ,  ; path search.    (defun shortest-path (start end net)      (bfs end (list (list start)) net))  ;we pass bfs end node, queue containing starting node , graph  ;being searched(net)     (defun bfs (end queue net)   (if (null queue) ;if queue empty bfs has not found path 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 current node goal node flip path                          ; , return answer         (reverse path)         ; otherwise preform new bfs search appending rest of          ; current queue result of new-paths function         (bfs end (append queue (new-paths path node net)) net))))  ; mapcar called once each member of list new-paths passed ; results of collected list (defun new-paths (path node net)   (mapcar #'(lambda (n) (cons n path))          (cdr (assoc node net)))) 

now, know instead of expanding left node in bfs need expand node seems closest goal state.
graph using looks this:

(a (b 3) (c 1))   (b (a 3) (d 1)) 

i have conversion function make work above bfs implementation, need turn hill climbing using graph format.

i'm not sure begin, , have been trying things no avail. know need change expand-queue function expand closest node, can't seem make function determine node closest.

thanks help!

appending things end of list wrong. costly operation list. whole list gets copied , other list appended. use in recursive procedure, means done each time expand node create new paths.

if put items on queue, need in order doing this. breadth first, 1 visits each node in level, before moving next level. hill-climbing require sort candidates 'best' using weighting function. need kind of function computing numeric value current node , next node candidate. need sort candidates , expand first 'best' node. lifo (last in, first out) queue means promising node needs pushed last, first expanded. note lifo queues fit singly linked lists. fifo (first in, first out) not so.

a typical idea of computer science data abstraction. if lifo queue such data structure, need define functions make-lifo-queue, empty-queue-p, ... theses functions use instead of list, null , others , make purpose of data structure clearer. makes code longer, since lisp lists generic , can (ab-)used kinds of usage scenarios, looking @ list operations alone not make intention clear. important more complicated graph algorithms.