2. (20 points) Consider the following road network and distance estimates: Estimated distance to Sebastopol from Ao Nuevo (A)is 256 from Butte (B) from Castle Rock (C) is 112 from Franconia (F) is 124 from Popocatapetl (P) is 135 from Rincon (R) from Sebastopol (S)is 0 Start Ao Nuevo IS 177 98 69 56 Popocatapetl Butte Francoria 102 is 69 ncon 97 Castle Rock 148 70 Sebastopol Using the underestimates in the table Estimated distance to Sebastopol, draw the complete search tree produced during an A* search of the network. assuming that you wanted to travel from Ao Nuevo to Sebastopol. Show the value of f(n) below each node n in the tree using the format g(n) + h(n) - f(n) Assume that the check for goalness is made only at the point a node is chosen for expansion. Show pruning that occurs as a result of applying the dynamic programming principle. Break any ties by placing a previously generated node in the open list ahead of a newly generated node. Use the abbreviations shown in the distance chart for each city, rather than writing out a city's entire name 2. (20 points) Consider the following road network and distance estimates: Estimated distance to Sebastopol from Ao Nuevo (A)is 256 from Butte (B) from Castle Rock (C) is 112 from Franconia (F) is 124 from Popocatapetl (P) is 135 from Rincon (R) from Sebastopol (S)is 0 Start Ao Nuevo IS 177 98 69 56 Popocatapetl Butte Francoria 102 is 69 ncon 97 Castle Rock 148 70 Sebastopol Using the underestimates in the table Estimated distance to Sebastopol, draw the complete search tree produced during an A* search of the network. assuming that you wanted to travel from Ao Nuevo to Sebastopol. Show the value of f(n) below each node n in the tree using the format g(n) + h(n) - f(n) Assume that the check for goalness is made only at the point a node is chosen for expansion. Show pruning that occurs as a result of applying the dynamic programming principle. Break any ties by placing a previously generated node in the open list ahead of a newly generated node. Use the abbreviations shown in the distance chart for each city, rather than writing out a city's entire name