15 02 2019

Page 1

ARTIFICIAL INTELLIGENCE February 15, 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). In a word ladder problem, given a start word and a target word, the goal is to find the shortest way to transform the start word into the target word by changing one letter at a time, such that each change results in a word belonging to a dictionary 𝐷 (the start word and the target word also belong to 𝐷). For example, starting with ‘green’ we can reach ‘trees’ in 3 steps (assuming that all the words are in 𝐷): green → greed → treed → trees (1) Define a search problem that represents the word ladder problem, providing a precise and complete description of all the elements of the formalization. (2) Considering the formalization in (1), and assuming 𝐷 finite, do breadth-first, depth-first, and iterative deepening search strategies guarantee to find a solution? Consider TREE-SEARCH and GRAPH-SEARCH variants. (3) Considering the formalization in (1), solve the problem in which the start word is ‘smart’, the target word is ‘bears’, and 𝐷={beans, bears, braid, brain, brand, brans, scars, sears, smart, stars, start, swart} using A* search…