Problem In the following tree, the numbers on the arrows represent the individual action costs. The root state is A and the Goal state is G. Note that that the nodes denoted by Gs, Ga, Go refer to the same goal state. We chose this notation to simplify writing the answers a) Write down the sequence of nodes expanded by each of the following search algorithms until it expands a Goal state. For example, if you expand A then then, your answer should be something like: ABC-G8 - (Use alphabetical order to break ties) Search Algorithm Breadth first (BFS) Expansion sequence Depth first (DFS) Uniform cost (UC) b) Write the search solution found by each algorithm (it should be something like A+ - +G). Also, write the total cost of the solution and indicate if it is optimal with respect to the total cost or not. Algorithm Search solution Optimal? (yes or no) BFS Total cost DFS UCS c) For USC, write all the steps of the tree search process until reaching the Goal state USC expansion steps AB A-C CS Scanned with CamScanner Problem 2 In the same tree search problem, suppose that we have selected a heuristic given by the following table. Sate Heuristic ABCD 542 G IF 11 K 111 a) Is this an admissible heuristie? Why or why not? b) Using Uniform Cost Search (UCS) algorithm, write the ordered in which the nodes are expanded in addition to the value of the expansion criterion (e.g. cost) used to decide which node to expand. (Use alphabetical order to break ties). Also write the search solution reached by this al . . Order of node Spain Value of expansion criterion 1 2 3 4 5 6 Order of node expansion B D F Value of expansion criterion Start state 1 2 2 7 8 19 10 11 12 Search solution: A Order of mode espansion Vale of expansion criteri c) Repeat (b) for Greedy search. Order of node Value of expansion expansion criterion Start state 2 B 4 3 D 2 4 F 2 5 6 Search solution: A 7 8 19 10 11 12 cs Scanned with CamScanner Order of node expansion Value of expansion criterion d) Repeat (b) for A search Order of node expansion 1 A 2 B 3 D 4 F 5 6 Search solution: A Value of expansion criterion Start state 1 2 2 7 8 9 10 11 12 e) is the following an admissible heuristic? Why or why not? Sate A D E F G Heuristic 542 5110 H 2 1 2 K 1 CS Scanned with CamScanner tas Problem A farmer, wolf, sheep and grass are initially on one side of the river (A). The farmer wants to transport everything to the other side (B) under some conditions: He can only transport a maximum of one thing each time (in addition to himself because he is the only one that can drive the boat) ii. The sheep cannot be left alone with the wolf or grass at any side. Transportation in both directions is allowed, le, A to B and B to A. We would like to formulate this as a search problem. a) Choose a suitable state representation. Describe the possible values it can take (Hint: you can use binary representation) b) How many world states in this problem (including those that are not allowed)? c) Using your notation in tel. give two examples of states that are not allowed due to condition (i). c) Using your notation in (al. blve one example of an action (state transitions) that is not allowed due to condition (). c) Using your natation in (a), write the start state and the goal state, cs Scanned with CamScanner
