13 02 2020

Page 1

ARTIFICIAL INTELLIGENCE February 13, 2020 LAST NAME AND FIRST NAME ROW COLUMN ID NUMBER (CODICE PERSONA) • The exam is composed of three stapled paper sheets printed on both sides. • This front page must be filled with last name, first name, ID number, position (row and column communicated by the instructor), and signature. • Exams without a completely filled front page or with missing sheets will not be considered. • Answers can be written only on these sheets. If you need more space, please write on the last page. • Exam is closed books (i.e., no books, notebooks, notes, … are allowed). Cell phones, bags, cases, and wallets are not allowed on the desk during the exam. • All the answers must be justified. SIGNATURE Question 1 (8 points). While organizing the Oscars’ Night gala dinner you have to assign seats to 𝑛 guests around a round table with 𝑛 places. For every pair of guests 𝑖 and 𝑗 you know a positive value Pleasure(𝑖,𝑗) that measures how much guest 𝑖 likes sitting next to guest 𝑗. For simplicity, assume that Pleasure(𝑖,𝑗)= Pleasure(𝑗,𝑖). Your objective is to find the seat assignment that maximizes the total pleasure of guests. (1) Formulate the above problem as a search problem. First, illustrate how you represent the states. Then, specify the initial state, the ACTIONS() function, the RESULT() function, the goal test, and the step cost. (Hint: be especially careful in defining the step cost.) (2) Does your formulation allow to generate multiple nodes in the search tree that correspond to the same state? If yes, illustrate a variant of your formulation that prevents these repetitions to happen. If no, explain why. (3) Assume that you solve the problem using TREE-SEARCH and A* search strategy with two heuristic functions, both of them admissible. Is it possible…