This map shows approximate mean driving times (in hours) between pairs of cities. For each of the following graph search strategies, work out the order in which states are expanded, as well as the path returned by graph search. In all cases, assume ties resolve in such a way that states with earlier alphabetical order are expanded first. The start and goal states are Warsaw and Rome, respectively. Remember that in graph search, a state is expanded only once.

The distance from Warsaw to Munich is 15, from Warsaw to Odesa is 6, from Warsaw to Budapest is 9, from Munich to Budapest is 12, from Munich to Venice is 3, from Munich to Rome is 15, from Rome to Venice is 6, and from Odesa to Venice is 14.

1. Greedy search with the given above heuristics

2. A* search with the same heuristics.

Path Expaned	Closed List	Fringe(ordered by path + heuristic

esWarsaw 15 Cit Munichlto 30 12 Warsaw Budapest Munich Odesa Rome Venice 12 Budapesto Odesa 20 Gers