Breadth First Search

Discussion of Common Lisp
Post Reply

Breadth First Search

Post by emertana » Wed Dec 24, 2008 3:58 am

I need this code to show me all the node that has been expanded any one can help me plzzzzzz

(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)
(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."
(format t "Breadth-first-search solution: ~n.~%"
(breadth-first-search 'a 'n) )
(format t "~n nodes has been expanded.~%"
(get-count) )

Posts: 35
Joined: Sat Jun 28, 2008 1:05 pm
Location: Urbana, Illinois, US


Post by danb » Thu Dec 25, 2008 3:07 pm

emertana wrote:

Code: Select all

(defun set-adj (x y)
  (setf (gethash x Breadth-info) y) )
(defun get-adj (x)
  (gethash x Breadth-info) )

(set 'A '(B C)) 

(defun successors (n)
  (get-adj n) )
You're never calling SET-ADJ, so GET-ADJ is returning NIL.

This seems to work with the rest of your implementation:

Code: Select all

(defun successors (n) (symbol-value n))

Code: Select all

BFS> (test)
Breadth-first-search solution: (A C G N).
14 nodes has been expanded.

Post Reply