10 07 2023

Pagina 1

Politecnico di Milano School of Industrial and Information Engineering Foundations of Artificial Intelligence September 8, 2023 Prof. Francesco Amigoni & Prof. 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. • Exam receiving 5 points or less will be graded as REPEAT. 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 FAMILY NAME FIRSTNAME CODICE PERSONA/ID Problem Scores /8 /8 /8 /8 Search (8 points). In the context of search, answer the following questions. Question 1: Define the concept of state space. The state space is a directed graph with nodes representing states and arcs representing actions. Question 2: Define the concept of search tree. A search tree is a structure superimposed over the state space graph, forming various paths from the initial state, trying to find a path that reaches a goal state. A search tree is composed of search nodes. Each node in the search tree corresponds to a state in the state space and the edges in the search tree correspond to actions. Thus, each node corresponds to a path from the initial state to a state in the state space. The root of the tree corresponds to…