CSE473 Homework # 1 : Search

 

1. R&N: Exercise 3.3 (a,d)

 

SOLUTION:

 

I pretty much accepted anything that was plausible.  Some of you allotted path costs for the map coloring problem and some of you asserted that the path cost does not matter for this problem.  I accepted both answers.

 

2. Consider the formulation of the 8-queens problem on the top of page 65

in R&N, with an empty chess board for the initial state.  What makes more

sense in this case, breadth-first or depth-first search?  Why?

 

SOLUTION:

 

The key notion is that depth-first search will probably find the solution faster, since it will always lie at the leaves of the search tree.  The fact that the search tree is finite for this problem (you won’t put more than 8 queens on the board, so no search path will be infinite) also leads to depth-first, since you want to take advantage of it’s lower space requirements if you can.

 

3. What are the memory and time requirements for breadth, depth and

iterative deepening search for

            i) branch factor 2, depth 10

            ii) branch factor 10, depth 10

 

SOLUTION:

 

 

Breadth-first

Depth-first

Iterative Deepening

 

Time

Space

Time

Space

Time

Space

BF2, D10

2047

2047

2047

20

4083

20

BF10, D10

11111111111

11111111111

11111111111

100

123456789011

100

 

I also accepted worst-case answers of the form O(b^n)…  or any response that displayed understanding that there are some important constants in there.  It’s important to understand that depth-first search and iterative deepening have different behaviors when it comes to time, since iterative deepening has to regenerate nodes for each iteration. 

 

4. What is the "catch" with bi-directional search for most problems?

Give an example of a real application where it would help.

 

SOLUTION:

 

As many of you noted, there is more than one “catch” with bi-directional search.  Most of you identified the ones listed in the book: the difficulty in generating predecessor states in some problems, the possible existence of multiple goal states, etc.  The question asks for a problem where bi-directional search would help.  Many of you offered map and maze problems, which was fine.  I appreciated the more creative responses.

 

5. R&N: Exercise 3.20 (a)

 

SOLUTION:

 

There was a huge variation in the level of detail of your responses to this question.  After going through the homeworks once, I decided on threshold for how many constraints I wanted listed (for full credit).  Most of you got full credit.

 

The cryptarithmetic problem as a CSP:

 

Variables: The letters in the puzzle words.

Domain: Digits (0-9)

Constraints:

            All the letters must have distinct digits assigned to them.

            The mathematical expression that results from the assignments must hold.

            The left-most letter in each word can’t be zero.

           

 

6. Using the map on page 95 (figure 4.2) of R&N, show how breadth-first

search would find a path from Dobreta to Bucharest.  Then, show how A* search

would expand this path using the "straight-line distance" to Bucharest as

your heuristic function. Your answers should use a format similar to that of

Figure 4.3 (a series of search trees).

 

SOLUTION:

 

I believe everyone did the graphs right for breadth-first.  On the graphs for best-first search, many of you expanded Pitesti before considering Mehadia, which actually has a lower f() value than any of Craiova’s children (Rimicu Vilcea, Dobreta, Pitesti).  Best-first just looks at the f() values of the nodes in it’s queue, so Mehadia should be expanded before Pitesti (even though it reveals two nodes we won’t want to expand, subsequently).

 

7. Give an example of an admissable heuristic for the 8-Queens problem.

 

SOLUTION:

 

This question caused a lot of confusion.  I ended up giving full credit to just about any answer that displayed knowledge about admissible heuristics (what they are, why they’re important, etc…).  Basically, all attempts that seemed sincere got full credit.

 

8. Give an example of a search problem in which simple hill-climbing would

provide better performance, on average, than simulated annealing.  Why does

the simpler algorithm work better in this instance?

 

SOLUTION:

 

Simulated-annealing will make “bad moves” at times in order to avoid local maxima/minima.  Most problems have some local maxima, so this is an important modification.  However, if the problem has a very smooth “heuristic landscape,” it makes less since to take these sorts of measures.  The class came up with a wide range of examples for these sorts of “simple” problems – again, I appreciated the more creative ones.