18 01 2019

Page 1

ARTIFICIAL INTELLIGENCE January 18, 2019 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). Consider a search problem defined on a state space with initial state 𝑠 and a single goal state 𝑡 and with step cost between a node 𝑛 and a successor node 𝑛′ (when taking action 𝑎) equal to: 𝑐(𝑛,𝑎,𝑛))=2-(.,/)+1 where 𝑔(𝑠,𝑛) is the minimum path cost for reaching 𝑛 starting from the node corresponding to 𝑠 (assume 𝑔(𝑠,𝑠)=0). (1) Do the breadth-first, depth-first, and uniform-cost search strategies guarantee to find the optimal solution of the above search problem? Assume to use GRAPH-SEARCH. (2) Do the breadth-first and the uniform-cost search strategies generate different search trees (apart from tie breaking)? Motivate the answer, possibly with an example. (3) Under which condition on the heuristic function ℎ() does A* search strategy guarantee to find the optimal solution of the above search problem? Assume to use GRAPH-SEARCH. (1) An example of a portion of a search tree built for the problem is: It is easy to see that the path cost between the root node corresponding to 𝑠 and a node 𝑛 is a non-decreasing function of the depth of 𝑛…