[A.I]

1. Using the Romanian map in the textbook, search for the path to Bucharest from Lugoj using graph-search BFS. For equally preferred nodes, generate and expand them in alphabetical order. Show the frontier after each step, the order of expanded nodes, and the solution found.

2. Same as problem #5, but use A* search with the straight-line distance heuristic. When showing the frontier, include the f, g, and h score for each node.

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