1. (100 points) Please make your new bidirectional uniform cost search algorithm with clear steps for finding a path as short as possible from a city to another city in a map. Please clearly show how your new algorithm finds a short path from Arad to Giurgiu in Romania map step by step (tree expansion steps must be shown clearly in detail). Please make best effort to write a perfect solution by typing in your clear solution. Arad 75, 118 71 Oradea Zerind 140 Timisoara 70 Midterm Exam Spring 2024 CSc 4810 Artificial Intelligence Undergraduate Student Name: 75 Dobreta 151 Lugoj Sibiu Me hadia 120 80 Rimnicu Vilcea 97 Fagaras 146 Pitesti 138 Cralova 211 101 Neamt Q 87 85 ♫ 90 Giurgiu Bucharest lasi 92 142 Urziceni 98 Vaslui Hirsova 86 Eforie Straight-line distance b Bucharest Arad Bucharest Craiova Dobreta Eforie Fagaras Giurgiu Hirsova Iasi Lugoj Mehadia Neamt Oradea Pitesti Rimnicu Vilcea Sibiu Timisoara Urziceni Vaslui Zerind 366 0 160 242 161 176 77 151 226 244 241 234 3.80 10 193 253 329 80 199 374

Fig: 1