Introduction to Artificial Intelligence
Worksheet #5B
AStar (A*) Search - Part 2, Using UPDATE-OPEN Trace from Av to Nan (Avignon to Nantes)

1. For A* part two, use an updated version of the A* search: astar2000.lsp.
   NOTE: This code uses the complete names of the cities, for instance, Ren to Av is Rennes to Avignon.
   
   
2. In order to see the an example of the effects of UPDATE-OPEN,
   trace the path from Avignon to Nantes. The first step of this path can be
   is shown on a tracing table.
   
   
3. The trace of this path is much more involved than a path for Av to To,
   for example. The overall route that you find should follow this sequence:
   • Part 1: Av -> Mont -> To -> Bord
   • Part 2:
     • At this point, the algorithm checks Mars (backstepping) and then Ly.
     • At Ly, you should find that a recalculation of Lim finds a
       shorter updated route to Lim through Ly rather than To.
     • Re-insert Lim into OPEN using the new value of f for Lim.
     • You should also change the ptr for Lim (from To to ?)
   • Part 3: With the new value of f for Lim, visit Lim next and
     find its successors. You should see that Nan now needs to
     be updated. The value f for Nan will be smaller coming from
     Lim rather than Bord (the city used for the previous f of Nan).
   
   
4. Hand in your detailed description - along with the values for
   f, g, and h - of the trace from Av to Nan.