Open | Closed | N | L | Nodes | 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 |
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