Ana səhifə

General guidelines for problem sets

Yüklə 8.65 Kb.
ö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

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

(b) depth-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 © 2016
rəhbərliyinə müraciət