- Consider The Search Space Below Where S Is The Initial State And The States G1 And G2 Satisfy The Goal Test Arcs Are L 1 (56.1 KiB) Viewed 80 times
Consider the search space below, where S is the initial state and the states G1 and G2 satisfy the goal test. Arcs are labelled with the cost of traversing them; for instance, traversing from S to A costs 3. And the estimated (heuristic) cost to a goal is reported inside nodes. That is, the following heuristic function h() is used: h(A) = 12; h(B) = 10; h(C) = 13; h(D) = 8; h(E) = 5; h(F) = 3; h(G1) = 0; h(G2) = 0; h(H) = 12; h(S) = 9. (6x5 = 30 marks) A 12 20 G1 0 2 E 5 3 A 5 3 3 B 10 F 00 00 8 S 14 7 с 13 13 G2 - 5 00 1 13 دیا A co D 8 H 12
For each of the following tree-based search strategies, you are given a list of options. Each option describes, using that search strategy, the goal state that is reached (if any) and the sequence of all the states associated with the expanded nodes on the search tree. When all else is being equal, nodes are expanded in alphabetical order. Please select one option that correctly describes the search strategy. Hints: (i) The sequence of expanded nodes is NOT the same as the solution. It is the nodes on your search tree that are expanded, in order, according to the search strategy. (ii) You may not always traverse directly from one node to another. For instance, you can directly traverse from B to C, but you cannot directly traverse from C to B. (iii) If you want to insert extra information to explain your answer (such as the search tree you draw), please feel free to do so.
1. Which of the following options correctly describes Breadth First Search (BFS) with repeated state check? | (a) Goal: G1; expanded nodes: S, A, B, C, D, Gl (b) Goal: G2; expanded nodes: S, A, B, D, C, E, G2 (c) Goal: Gl; expanded nodes: S, A, B, D, B, GI (d) Goal: G1; expanded nodes: S, A, B, D, S, B, G1 (e) Goal: No goal reached; expanded nodes: S, A, S, A, .... Infinite loop 2. Which of the following options correctly describes Depth First Search (DFS) with repeated state check? (a) Goal: G1; expanded nodes: S, A, B, D, B, G1 (b) Goal: G2; expanded nodes: S, A, B, C, G2 (c) Goal: G2; expanded nodes: S, A, B, G2 (d) Goal: G1; expanded nodes: S, A, G1 (e) Goal: No goal reached; expanded nodes: S, A, B, A, B, .... Infinite loop 3. Which of the following options correctly describes Depth First Search (DFS) without repeated state check? (a) Goal: Gl; expanded nodes: S, A, B, D, B, Gl (b) Goal: G2; expanded nodes: S, A, B, C, G2 (c) Goal: G1; expanded nodes: S, A, GI (d) Goal: No goal reached; expanded nodes: S, A, B, A, B, .... Goal: No goal reached; expanded nodes: S, A, S, A, Infinite loop Infinite loop (c) Goal: G2; expanded nodes: S, B, G2 (d) Goal: Gl; expanded nodes: S, A, GI Goal: G1; expanded nodes: S, B, E, F, Gl (5 marks) (5 marks) 4. Which of the following options correctly describes Greedy Best First Search (GBFS) with repeated state check? (a) Goal: G2; expanded nodes: S, D G2 (b) Goal: G2; expanded nodes: S, D, B, G2 (5 marks) (d) Goal: Gl; expanded nodes: S, B, E, F, Gl Goal: No goal reached; expanded nodes: S, D, S, D, .... Infinite loop (5 marks) 5. Which of the following options correctly describes Greedy Best First Search (GBFS) without repeated state check? (a) Goal: G2; expanded nodes: S, D, H, G2 (b) Goal: G2; expanded nodes: S, D, B, G2 (c) Goal: G2; expanded nodes: S, B, G2 6. Which of the following options correctly describes A* with repeated state check? (a) Goal: G2; expanded nodes: S, D, H, G2 (b) Goal: Gl; expanded nodes: S, D, A, B, E, F, Gl Goal: G2; expanded nodes: S, B, G2 (d) Goal: G1; expanded nodes: S, B, E, F, Gl (e) Goal: G2; expanded nodes: S, A, B, G2 (5 marks) (5 marks)