29 01 2019

Page 1

ARTIFICIAL INTELLIGENCE January 29, 2018 LAST NAME AND FIRST NAME ROW COLUMN ID NUMBER (MATRICOLA)  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, positi on (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). Consider the search problem described by the state space represented below, where s0 is the initial state, sf is the only state that satisfies the goal test, all step costs are unitary if not indicated, and n is a fixed integer number (n > 1). s0 sf s1 s2 s3 sn ... step cost = n+2 Discuss the conditions under which the breadth -first, depth -first, iterative deepening, and A* search strategies guarantee to find a solution to the above problem. Discuss the conditions under which the same search strategies guarantee to find the optimal solut ion to the above problem. When relevant, distinguish between TREE-SEARCH (i.e., without elimination of repeated states) and GRAPH-SEARCH (i.e., with elimination of repeated states) Search strategy Solution? Optimal solution? Breadth-first Always Never Depth-first With GRAPH-SEARCH Never Iterative deepening Always Never A* Always The root of the search tree has a child corresponding to s f with f-evaluation n+2. Th ere is only a finite number of possible nodes of the search tree with f - evaluation less…