1. A. The following search problem start with state S and goal state G. The transition costs are next to the edges, and the heuristic values are next to the states. - 20 6 3 hr 2 2 3 s B D G . 6 4 1 3 6 E h2 Figure 1. Search problem domain I. What is the final path for the Uniform-Cost Search? [04 Marks II. What is the final path for the Depth First Search? (Hint: If a node has multiple successors, then we always expand the successors in increasing alphabetical order.) [04 Marks What is the final path for the A Search? [04 Marks] IV. Is the heuristic function in this example admissible? [02 Marks] B. Here is the pseudo-code for simulated annealing beginning in Configuration X and with initial temperature T and temperature decay rater. 1. Let X initial object 2. Let val(X) 3. Let X* :-randomly chosen configuration chosen from the moveset of X 4. Let' :-EvalX") E 5. Let zz-a number drawn randomly uniformly between 0 and 1 a 1 6. IfE > Eorexpl-1E-E' /T) > then -- X:-* X .EE 7. T 8. If a convergence test is satisfied then halt. Else go to Slep 3. 2 PL/EX/02 REV.00/00.00.0000 1. Normally r, the temperature decay rate, is chosen in the range 0 1? [03 Marks IL Alternatively, how would it change ifr=0? [03 Marks III. If we simplified the conditional test in Step 6 Ifexp(-E- EN/T) > then How would the behaviour of simulated annealing change? [05 Marks)