Trace Table for Best First Search
Practice Trace of Road from Bordeaux (Bord) to Dijon (Di)
(Partial solution)


For a trace of the output in Clisp, click here

Open Closed N LNodes Fvalue Pointer
(Bord)

()
 nil
-
Bord
 57
nil
()



(To Lim Nan)

(Bord)





 Bord





(Lim To Nan)





 Lim
To
Nan



39 (12-51)
37 (14-51)
67 (-16-51)



 Bord
Bord
Bord
(Lim Nan)



(Mont Lim Nan)

(To Bord)





 To





(Mont Bord Lim)





 Mont





14 (36-51)





 To
(Lim Nan)



(Av Lim Nan)

(Mont To Bord)





 Mont





(Av To)





 Av





3 (48-51)





 Mont
Keep going to find the route to Dijon




At the end, print the pointer links in reverse order

See the code for bestfirst.lisp here.
Global Variables: open_count, val, goal, closed, open, n, l 
   Best-First Search algorithm
   1. Place the starting node, S, on OPEN, compute f(S), and associate
      this value with S.  Associate a null pointer to S.
   2. If OPEN is empty, return "Failure" and stop
   3. Choose a node N from OPEN such that f(N) <= f(M) for each M on OPEN
      and such that N is a goal node if any goal  node achieves that 
      minimum f value.
   4. Put N on closed and remove N from OPEN.  
   5. If N is a goal node, return the path from S to N obtained by
      tracing backward the pointers from N to S.  Then stop.
   6. For each successor J of N that is not already on OPEN or on CLOSED:
      a. Compute f(J) and associate it with J
      b. Put J on OPEN
      c. Associate a pointer with J pointing back to N
   7. Go back to step 2