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 Zerind 87 151 75 Iasi Arad 140 92 Sibiu 99 Fagaras 118 Vaslui 80 Timisoara Rimnicu Vilcea 142 111 211 Lugoj Pitesti 97 70 98 Mehadia Hirsova 146 101 85 Urziceni 86 75 138 Bucharest Drobeta 120 90 Craiova Eforie Giurgiu 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