This is an Artificial Intelligence problem. Please provide the answer typed out or computer generated.
Q6. Suppose we want to travel from Arad to Bucharest in the following graph. Oradea 71 Neamt Zerind 87 151 75 lasi Arad 140 92 Sibiu 99 Fagaras 118 Vaslui 80 Timisoara Rimnicu Vilcea 142 111 Lugoj Pitesti 211 97 70 98 Hirsova Mehadia 146 101 85 Urziceni 86 138 75 Drobeta Bucharest 120 Craiova Eforie Giurgiu Figure 3.2 A simplified road map of part of Romania. (i) If we did a Breadth First Search starting from Arad, what sequence of places would we visit before reaching Bucharest? Drawing the tree is required. (15 points) (ii)If we did a Depth First Search starting from Arad, what sequence of places would we visit before reaching Bucharest? Use the tree that you constructed for the solution to (i) above. Do not construct a new tree. (15 points) If we did an A* Search starting from Arad, what sequence of places would we visit before reaching Bucharest? The straight line distance of each place to Bucharest is given below. Construct a new tree if needed. In that case, drawing the tree is required. (20 points) 366 Arad Bucharest Craiova Drobeta Eforie Fagaras Giurgiu Hirsova Iasi Lugoj 0 160 242 161 176 77 151 226 244 Mehadia Neamt Oradea Pitesti Rimnicu Vilcea Sibiu Timisoara Urziceni Vaslui Zerind 241 234 380 100 193 253 329 80 199 374 Figure 3.22 Values of hsld-straight-line distances to Bucharest. Q6. Suppose we want to travel from Arad to Bucharest in the following graph. Oradea 71 Neamt Zerind 87 151 75 lasi Arad 140 92 Sibiu 99 Fagaras 118 Vaslui 80 Timisoara Rimnicu Vilcea 142 111 Lugoj Pitesti 211 97 70 98 Hirsova Mehadia 146 101 85 Urziceni 86 138 75 Drobeta Bucharest 120 Craiova Eforie Giurgiu Figure 3.2 A simplified road map of part of Romania. (i) If we did a Breadth First Search starting from Arad, what sequence of places would we visit before reaching Bucharest? Drawing the tree is required. (15 points) (ii)If we did a Depth First Search starting from Arad, what sequence of places would we visit before reaching Bucharest? Use the tree that you constructed for the solution to (i) above. Do not construct a new tree. (15 points) If we did an A* Search starting from Arad, what sequence of places would we visit before reaching Bucharest? The straight line distance of each place to Bucharest is given below. Construct a new tree if needed. In that case, drawing the tree is required. (20 points) 366 Arad Bucharest Craiova Drobeta Eforie Fagaras Giurgiu Hirsova Iasi Lugoj 0 160 242 161 176 77 151 226 244 Mehadia Neamt Oradea Pitesti Rimnicu Vilcea Sibiu Timisoara Urziceni Vaslui Zerind 241 234 380 100 193 253 329 80 199 374 Figure 3.22 Values of hsld-straight-line distances to Bucharest
