Problem 1 (20 points): Trace the operation of A" search (the tree version) applied to the problem of getting to Bucharest from Lugoj using the straight-line distance heuristic. That is, show the sequence of nodes that the algorithm will con sider and the f. g. and h score for each node. You don't need to draw the graph, just right down a sequence of city, f(city), g(city), h(city)) in the order in which the nodes are expanded Oradea 71 erind 151 75 lasi Arad 140 92 Sibiu Fagaras Vaslui 80 Rimnicu Vilcea Timisoara 97 Hirsova Mehadia 146 101 86 138 Drobeta 120 90 Eforie Craiova Figure 1: A simplified road map of part of Romania indicating distances between different cities Mehadia Neamt Oradea Pitesti Rimnicu Vilcea Sibiu Timisoara Urziceni Vaslui 241 Arad Bucharest Craiova Drobeta Eforie Fagaras Giurgiu Hirsova lasi Lugoj 380 100 193 176 151 226 244 199 374 Figure 2: Straight-line distances to Bucharest