Problem 2: Show all operations taken by A* search applied to the problem of getting from Timisoara to Bucharest using the straight line distance heuristic. That is, show how the priority queue changes, the states removed from the priority queue, the backpointers, etc, during a run of A* search. Also specify the path found by A* and its cost. You will need to refer to Figure 3.1 on page 64 for the graph that corresponds to the map of Romania, which shows the actual costs of transitions, etc. You will also need to refer to Figure 3.16 on page 85, which lists the straight line distances from each city to Bucharest that you will need for the heuristic (i.e., that table is the heuristic).

Oradea 71 Neamt 87 Zerind 75/ 151 Iasi Arad 140 92 Sibiu 99 Fagaras 118 Vaslui 80 Rimnicu Vilcea Timisoara 142 111 211 Lugoj Pitesti 97 70 98 Mehadia 146 Hirsova 101 85 Urziceni Bucharest 75 138 86 Drobeta 120 90 Craiova Giurgiu Eforie Figure 3.2 A simplified road map of part of Romania. Figure 3.16 Arad Bucharest Craiova Drobeta Eforie Fagaras Giurgiu Hirsova Iasi Lugoj 366 0 160 242 161 176 77 151 226 244 Mehadia Neamt Oradea Pitesti Rimnicu Vilcea Sibiu Timisoara Urziceni Vaslui Zerind 241 234 380 100 193 253 329 80 199 374 Values of hsld-straight-line distances to Bucharest