2004 Paper 5 Question 6
Artificial Intelligence
(a) Describe the way in which a problem should be represented in order to allow
its solution using a heuristic search technique. [5 marks]
(b) Define what it means for a search algorithm to be complete, and to be optimal.
[2 marks]
(c) Define what it means for a heuristic function to be admissible, and to be
monotonic. [2 marks]
(d) Describe the operation of the A?
heuristic search algorithm. [5 marks]
(e) Prove that the A?
heuristic search algorithm is optimal when applied in
conjunction with a monotonic heuristic. State the conditions under which
the algorithm is also complete, and explain why this is the case. [6 marks]