[AI_107A_B_1]

1. [15%] Given the map below, we want to find a path from K to R. Consider only graph search, i.e., each state is visited at most once in the search process. For equally preferred nodes, generate and expand them in alphabetical order. (a) [4%] List the states expanded, in the correct order, if we use breadth-first search (BFS). What is the solution path? (b) [4%] List the states expanded, in the correct order, if we use uniform-cost search. What is the solution path? (c) [4%] Show the process of A* search with the straight-line distance as heuristic. What is the solution path? (d) [3%] Does iterative-deepening search (IDS) yields the same path as BFS? If yes, then what is the advantage of using IDS instead of BFS? K

1. [15%] Given the map below, we want to find a path from K to R. Consider only graph search, i.e., each state is visited at most once in the search process. For equally preferred nodes, generate and expand them in alphabetical order. (a) [4%] List the states expanded, in the correct order, if we use breadth-first search (BFS). What is the solution path? (b) [4%] List the states expanded, in the correct order, if we use uniform-cost search. What is the solution path? (c) [4%] Show the process of A* search with the straight-line distance as heuristic. What is the solution path? (d) [3%] Does iterative-deepening search (IDS) yields the same path as BFS? If yes, then what is the advantage of using IDS instead of BFS? K 125 15 90 F 30 20 70 J straight-line distances F J K R S C 15 25 115 70 55 F 20 130 65 65 J 125 50 60 K 160 70 R 100 170 60 R 1. [15%] Given the map below, we want to find a path from K to R. Consider only graph search, i.e., each state is visited at most once in the search process. For equally preferred nodes, generate and expand them in alphabetical order. (a) [4%] List the states expanded, in the correct order, if we use breadth-first search (BFS). What is the solution path? (b) [4%] List the states expanded, in the correct order, if we use uniform-cost search. What is the solution path? (c) [4%] Show the process of A* search with the straight-line distance as heuristic. What is the solution path? (d) [3%] Does iterative-deepening search (IDS) yields the same path as BFS? If yes, then what is the advantage of using IDS instead of BFS? K 125 15 90 F 30 20 70 J straight-line distances F J K R S C 15 25 115 70 55 F 20 130 65 65 J 125 50 60 K 160 70 R 100 170 60 R