Lisp Programming breadth first search?

Question

This function is doing the breadth first search , I need it to show all the node which has been extended any one can help me ????
(let ((Breadth-info (make-hash-table :size 20))
(path-predecessor-info (make-hash-table :size 20)) )
(defun set-adj (x y)
(setf (gethash x Breadth-info) y) )
(defun get-adj (x)
(gethash x Breadth-info) )
(defun set-predecessor (x y)
(setf (gethash x path-predecessor-info) y) )
(defun get-predecessor (x)
(gethash x path-predecessor-info) )
)

;Generating The Tree
(set 'A '(B C))
(set 'B '(D E)) (set 'C '(F G))
(set 'D '(H I)) (set 'E '(J K))
(set 'F '(L M)) (set 'G '(N))
(set 'H '(D)) (set 'I '(D))
(set 'J '(E)) (set 'K '(E))
(set 'L '(F)) (set 'M '(F))
(set 'N '(G))

;This function performs a breadth-first search from the "START-NODE" to reach the "GOAL-NODE".

(defun breadth-first-search (start-node goal-node)
(let ((open (list start-node)) ;Step1
(closed nil)n l)
(set-predecessor start-node nil)
(loop
(if (null open)(return 'failure)) ;Step2
(setf n (pop open)) ;Step3
(push n closed)(increment-count)
(if (eql n goal-node)
(return (extract-path n)) )
(setf l (successors n)) ;Step4
(setf l (list-difference l (append open closed)))
(setf open (append open l) ) ;Step5
(dolist (x l)
(set-predecessor x n) )

) ) )


; This function returns the sequence of cities which has been found.
(defun extract-path (n)
"Returns the path to N."
(cond ((null n) nil)
(t (append (extract-path (get-predecessor n))
(list n) )) ) )

; This function retrieves the list of cities adjacent,to N from N's property list.
(defun successors (n)
"Returns a list of the nodes adjacent to N."
(get-adj n) )

; LIST-DIFFERENCE is like the built-in Lisp function,it called SET-DIFFERENCE,
; it preserves the ordering in LST1.

(defun list-difference (lst1 lst2)
"Returns a list of those elements of LST1 that do not
occur on LST2."
(dolist (elt lst2 lst1)
(setf lst1 (remove elt lst1)) ) )

; Use a local variable EXPANSION-COUNT for counting the number of nodes has been expanded.
(let (expansion-count)
(defun initialize-count () (setf expansion-count 0))
(defun increment-count () (incf expansion-count))
(defun get-count () expansion-count) )



; Test function sets EXPANSION-COUNT to 0 and begins a search from A to N.
(defun test ()
"Tests the function BREADTH-FIRST-SEARCH."
(initialize-count)
(format t "Breadth-first-search solution: ~n.~%"
(breadth-first-search 'a 'n) )
(format t "~n nodes has been expanded.~%"
(get-count) )
(test)

Answer 1

Common Lisp -- yummy.



Anyway, look at your "Step 5"; that is where the new nodes to be searched are added to the open nodes. Print out the new nodes in list l.



Make sure you do it after the list-difference; that is an optimization to ensure that the same nodes aren't visited again.

Answer 2

Breadth First Search Lisp

Answer 3

Where is your attempt at the code? Post it here for correction. We are not here to do your homework.