Ana səhifə

General guidelines for problem sets

 tarix 27.06.2016 ölçüsü 8.65 Kb.
 Mehran Sahami Handout #3 CS121 July 5, 2001 Problem Set #1 Due: Beginning of class, Thursday, July 12th General guidelines for problem sets If anything is ambiguous or unclear: 1. Check the class web page for "Problem Set Clarifications" 2. Ask the instructor or TA for clarification 3. Make assumptions, state them clearly in your solution, and then work out the problem. You may discuss problems with colleagues, but all work must be done individually. Remember to cite the people you discussed a problem with on your assignment. Problem Set 1. (15 points) Uninformed search Consider the following search tree: In what order are the nodes expanded using: (a) breadth-first search (c) iterative deepening search (starting with depth 0, and incrementing the depth by 1 in each iteration) 2. (20 points) Formulating search problems In cryptarithmetic problems, letters stand for digits and the aim is to find a substitution of digits for letters such that the resulting sum is arithmetically correct. Each letter must stand for a different digit. Here is an example of such a problem: FORTY Solution: 29786 + TEN + 850 + TEN + 850 ----- ----- SIXTY 31486 That is: F=2, O=9, R=7, T=8, Y=6, E=5, N=0, S=3, I=1, X=4 Such problem can be solved using search techniques. Formulate cryptarithmetic as a search problem, by describing the states, operators, initial state, and goal test for such problems. Make you answer general enough to be applicable to any cryptarithmetic problem. 3. (10 points) Search spaces Describe a search space (a graph is sufficient – it need not correspond to a real-world problem) in which iterative deepening search performs much worse, in terms of the number of nodes expanded, than depth-first search. 4. (20 points) A* Search Problem 9.1 in Nilsson textbook, p. 160-161. 5. (15 points) Termination of A* Problem 9.3 in Nilsson textbook, p. 161. 6. (20 points) Non-admissible heuristics Invent and describe a heuristic for the 8-puzzle that sometimes over-estimates the cost to the goal (i.e., is not an admissible heuristic), and show how it can lead to a sub-optimal solution for a particular instance of the 8-puzzle.

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©atelim.com 2016
rəhbərliyinə müraciət