Question 1 All Roads Leads to Rome] This map, illustrated in Figure 1, 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 book and the slides present two correct, yet slightly different, versions of the algorithm. Please use the algorithm in the slides. gen Bremen Hamburg - Wielkoposk Bydgoszcz Belanus o OEmmen Hannover 15 Warsaw Gomel o Polska Bielefeld Braunsch Zeiona LeipzigZona oDortmund (linek) Deutschlan Rwne O Kin Dresden Wrodkawsm Germany esbadeno o Frankfurt am Main Cesk Republikao Krakw hmelnitsky Cherkassy ( Czech Republic mberg (Bass Ukraine Munich ostadt 12 Slo ensko ou Chernivis urg im Galen Osterreich Schweiz Suissesbck Budapesta uceMoldova Chiinau o Hungary Arad ClujNapoca Bacu Pecs greb 15 Slovenija szeged Romania Focsani Odesa kegrade Resits ona Venice Ploiest O Buzau TorinoMnao Bosna i Hercegovina Srb Drobeta Turnu Severin Bucurestn&vetanta Monaco 6 Bosnia and Italia SpltD Herzegowns Draguignan Sofia Varna Crna Gora Kosva enearo KosOvo Montenegro Shkode 14 Rome Macedonie (FYROM >-^Edirne, stanbul Latna Napoli Shqiperia Bolu Cankr le Bursao Adapaza Brndsi Taranto Ankarao Kr Cadlian Figure 1: Central Europe Map with Mean Driving Times (in hours). A. Fill the table below Algorithmm Depth-first search Breadth-first search Uniform cost search Greedy search' A" search Order Path Grade 3 pt 3 pt 3 pt 3 pt 3 pt Use the following heuristic: h(Odesa) = 20 hrs, h(Budapest) = 12 hrs h(Munich) = 3 hrs, h(Venice) = 3 hrs h(Rome 0 hrs, h(Warsaw) 30 hrs. B. Is the heuristic admissible? Consistent? Briefly justify your answers Question 1 All Roads Leads to Rome] This map, illustrated in Figure 1, 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 book and the slides present two correct, yet slightly different, versions of the algorithm. Please use the algorithm in the slides. gen Bremen Hamburg - Wielkoposk Bydgoszcz Belanus o OEmmen Hannover 15 Warsaw Gomel o Polska Bielefeld Braunsch Zeiona LeipzigZona oDortmund (linek) Deutschlan Rwne O Kin Dresden Wrodkawsm Germany esbadeno o Frankfurt am Main Cesk Republikao Krakw hmelnitsky Cherkassy ( Czech Republic mberg (Bass Ukraine Munich ostadt 12 Slo ensko ou Chernivis urg im Galen Osterreich Schweiz Suissesbck Budapesta uceMoldova Chiinau o Hungary Arad ClujNapoca Bacu Pecs greb 15 Slovenija szeged Romania Focsani Odesa kegrade Resits ona Venice Ploiest O Buzau TorinoMnao Bosna i Hercegovina Srb Drobeta Turnu Severin Bucurestn&vetanta Monaco 6 Bosnia and Italia SpltD Herzegowns Draguignan Sofia Varna Crna Gora Kosva enearo KosOvo Montenegro Shkode 14 Rome Macedonie (FYROM >-^Edirne, stanbul Latna Napoli Shqiperia Bolu Cankr le Bursao Adapaza Brndsi Taranto Ankarao Kr Cadlian Figure 1: Central Europe Map with Mean Driving Times (in hours). A. Fill the table below Algorithmm Depth-first search Breadth-first search Uniform cost search Greedy search' A" search Order Path Grade 3 pt 3 pt 3 pt 3 pt 3 pt Use the following heuristic: h(Odesa) = 20 hrs, h(Budapest) = 12 hrs h(Munich) = 3 hrs, h(Venice) = 3 hrs h(Rome 0 hrs, h(Warsaw) 30 hrs. B. Is the heuristic admissible? Consistent? Briefly justify your answers
