Question 1 Search [30 marks] a) Compare the following search strategies in terms of completeness and optimality: i. Breadth-first search. ii. Depth-first search. iii. Depth-first search with iterative deepening. iv. Greedy search.

b) Explain in your own words what is meant by a heuristic search strategy and an admissible heuristic. Give an example of a search heuristic which is not discussed elsewhere in this coursework.

c) For this question you will need to use the simplified map of Romania and the table of straight-line distances to Bucharest from Chapter 3 of AIMA. Calculate the route that would be chosen from Zerind to Bucharest by each of: i. Greedy search. ii. A* search. You should explain your answers and show your working. Detailed content such as successive states of the search tree may be given in an appendix. [16 marks