Question 1 [9 pts]: A search method is called complete when it is guaranteed to find a solution if there is one. A search method is said to produce optimal solutions when the method is guaranteed to output the highest-quality solution (in our case, the least expensive path from the start state to the goal state) when there are several different solutions. For EACH of the following search methods below, answer both of the following questions two questions: Completeness: Is the search method complete? If your answer is YES, explain why the method is complete. If your answer is NO, show an example in which the method fails to find a solution even though a solution exists. Optimality: Does the search method output optimal solutions? If your answer is YES, explain why. If your answer is NO, show an example in which the method fails to find an optimal solution even though several solutions exists. EXPLAIN YOUR ANSWER - No credit will be given to a plain YES/NO answer without the corresponding explanation. Depth 1st Search Depth-limited Search Iterative Deepening Search Branch-and-bound (= Uniform Cost Search) Greedy Search (= Best 1st Search) A* Hill-climbing Beam Search Question 2 [6 pts]: 2.1. Simulated annealing will find a global optimum with probability approaching 1 if you lower T slowly enough. Please explain what simulated annealing will do in each of the following cases (a) What happens if you lower T very quickly? (b) What happens if you never lower T? 2.2. Explain other ways that hill climbing can add randomness to avoid getting stuck. (By other we mean other than simulated annealing )