Best First Trace in Clisp
Sample Route from Bordeaux (Bord) to Dijon (Di)
As an example of the use of debugging statements, I added two lines
inside the function bfs. I also needed to write a helper function called
printFvalues. Here's the code I added:
(loop (cond ((null open)(return 'failure)))
(setq n (select_best open))
(setq open (delete n open))
(setq closed (cons n closed))
(if (eq n goal) (return(extract_path n)))
(setq l (get n 'adj))
(mapcar 'open_node (set_diff (set_diff l open) closed))
--> (format t "N:~a Open:~a Closed:~a~&" n open closed)
--> (printFvalues open)
)
This prints the results after the open list has been updated with the new
cities and fvalues for those cities.
The function printFvalues prints out the fvalues of the cities in the list
that is sent as a parameter (in this case "open").
(defun printFvalues (lst)
(dolist (city lst)
(format t "City: ~a Fvalue: ~f~&" city (get city 'fvalue))
)
)
For a review of the syntax of the format statement, look in the
"Overview of Lisp" link from Peter Norvig's book. See the section on
Input/Output.
Here's a trace of the output for the path from Bordeaux to Dijon:
[16]> (bfs 'bord 'di)
N:BORD Open:(TO LIM NAN) Closed:(BORD)
City: TO Fvalue: 37.0
City: LIM Fvalue: 39.0
City: NAN Fvalue: 67.0
N:TO Open:(MONT LIM NAN) Closed:(TO BORD)
City: MONT Fvalue: 15.0
City: LIM Fvalue: 39.0
City: NAN Fvalue: 67.0
N:MONT Open:(AV LIM NAN) Closed:(MONT TO BORD)
City: AV Fvalue: 3.0
City: LIM Fvalue: 39.0
City: NAN Fvalue: 67.0
N:AV Open:(MARS LY GREN LIM NAN) Closed:(AV MONT TO BORD)
City: MARS Fvalue: 2.0
City: LY Fvalue: 3.0
City: GREN Fvalue: 6.0
City: LIM Fvalue: 39.0
City: NAN Fvalue: 67.0
N:MARS Open:(LY GREN NICE LIM NAN) Closed:(MARS AV MONT TO BORD)
City: LY Fvalue: 3.0
City: GREN Fvalue: 6.0
City: NICE Fvalue: 22.0
City: LIM Fvalue: 39.0
City: NAN Fvalue: 67.0
N:LY Open:(DI GREN NICE LIM NAN) Closed:(LY MARS AV MONT TO BORD)
City: DI Fvalue: 0.0
City: GREN Fvalue: 6.0
City: NICE Fvalue: 22.0
City: LIM Fvalue: 39.0
City: NAN Fvalue: 67.0
(BORD TO MONT AV LY DI)
[17]>