14 07 2022

Page 1

Politecnico di Milano School of Industrial and Information Engineering Foundations of Artificial Intelligence July 14, 2022 Prof. Francesco Amigoni & Pierluca Lanzi GENERAL INSTRUCTIONS • This is a closed-book/closed-notes exam. • Pencils are not allowed. • Answers must be written inside the answer boxes designated for each problem. • Answers must be legible and adequately motivated. • The exam must be returned with all its original sheets. • No sheet can be added. • None of the sheets can be removed. • Only non-programmable calculators are allowed. • Notes/books/mobile phones are not allowed. • If a student is caught using forbidden material, the exam will immediately end, and the disciplinary committee will be notified. SCORING • A problem left unsolved will amount to zero points. • Completely wrong answers assign negative points. STUDENTS HAVE 1:30h TO SOLVE ALL THE PROBLEMS SIGN THIS BOX TO WITHDRAW FROM THE EXAM SURNAME FIRSTNAME CODICE PERSONA/ID GRADES Informed Search (8 points). In chess the knight (the horse) moves in an L-shape—that is, it can either move two squares in any direction vertically followed by one square horizontally, or two squares in any direction horizontally followed by one square vertically. The picture below reports a knight and the admissible moves using the black square dots. Consider the problem of moving a knight on the 3x4 grid below from the start position S to the goal position G. Each position of the grid is identified by a letter and the heuristic value. All moves have cost 1. S (h=3) H (h=1) D (h=1) K (h=1) I (h=1) J (h=2) A (h=2) E (h=2) C (h=1) B (h=2) G (h=0) F (h=3) Question 1. Draw the state space (search graph) for the 3x4 grid above. Answer: Question 2. Given that, (1) all the algorithms apply graph search and thus do not…