20 01 2020

Pagina 1

ARTIFICIAL INTELLIGENCE January 20, 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). Consider the following search problem: - initial state: 𝑠", - function ACTIONS() defined as: state 𝑠 𝑠" 𝑠# 𝑠$ 𝑠% 𝑠& 𝑠' ACTIONS(𝑠) {goto-1, goto-4} {goto-0, goto-2, goto-5} {goto-1, goto-3} {goto-2, goto-4} {goto-0, goto-3} {goto-1} - function RESULT() defined as: RESULT(𝑠, goto-𝑥) = 𝑠/, - goal test is satisfied by states 𝑠& and 𝑠' (and only by them), - step cost is unitary. (1) Represent as a graph the state space corresponding to the above problem. (2) Consider TREE-SEARCH with breadth-first search strategy. How many nodes at best and at worst are generated before a solution is found for the above search problem? Why? (3) Is the solution found in (2) guaranteed to be optimal? Why? (4) Consider TREE-SEARCH with depth-first search strategy. How many nodes at best and at worst are generated before a solution is found for the above search problem? Why? (5) Is the solution found in (4) guaranteed to be optimal? Why? (6) Consider GRAPH-SEARCH with greedy best-first search strategy. Is there any heuristic function ℎ() such that a node…