22 02 2018

Page 1

ARTIFICIAL INTELLIGENCE February 22, 2018 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 la st 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). Consider the search problem described by the state space represented below, where 1 is the initial state, 5 is the only state that satisfies the goal test , the step costs are reported close to the corresponding actions, and values of a heuristic function are shown. 1 3 2 5 4 1 1 1 1 1 1 3 h(1)=0 h(2)=0 h(3)=0 h(4)=3 h(5)=0 (1) Solve the problem using uniform -cost search strategy and GRAPH-SEARCH (i.e., with elimination of repeated states). Report the search tree and the solution found. (2) Solve the problem using A* search strategy and GRAPH-SEARCH. R eport the search tree and the solution found. (3) Which one of the two solutions is guaranteed to be optimal? Explain why. (4) Which one of the two search strategies is optimal if TREE-SEARCH (i.e., without elimination of repeated states) is used? (1) Search tree built by uniform-cost search strategy: 1 2 3 3 g=0 g=1g=1 5 g=2 g=4 1 4 g=2 g=2 5 g=3 X X Solution found is 1-3-4-5 and has cost 3. (2) Search tree built by A* search strategy: 1 2 3 3 f=g+h=0+0=0 f=1+0=1f=1+0=1 5 f=2+0=2…