Worksheet #5B
AStar (A*) Search - Part 2, Using UPDATE-OPEN

                                             Name ______________

Trace from Av to Nan (Avignon to Nantes)

1. For A* part two, use an updated version of the A* search:
   /home/atlas1/ai/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
   found here.

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.