Perform an A* search applied to the problem of getting from Lugoj to Bucharest using the straight-line distance heuristic using the map on p.68 and table on p.93(attached below). On the graph, show the f, g, and h score for each node as it is expanded.

NOTE: Make sure to accumulate total distance traveled in your g() score as you expand each node - the total cost to get to that node includes all the g() costs prior (total distance from source to that node, sum of all road lengths so far).

(Note: You can draw out on paper and scan or take a pic with your cell phone, as long as it's legible.)

Show the sequence of nodes that the algorithm will choose as the optimal path, and the total distance traveled.

71 Neamt 87 Zerind151 75 asi Arad 140 92 Sibiu Fagaras 118 Vaslui 80 Rimnicu Vilcea Timisoara 142 211 Pitesti Lugoj 97 98 70 Hirsova Mehadia 146 101 Urziceni 86 75 138 Bucharest 120 90 Eforie Craiova Giurgiu Figure 3.2 A simplified road map of part of Romania