## Artificial Intelligence: Problem Set 1: Solutions

### Problem 1

A. The first five solutions are

1. Objects 1 and 2 to bin 1; objects 3 and 4 to bin 2; object 5 to bin 3;
object 6 to bin 4; object 7 to bin 5; object 8 to bin 6.

2. 1 and 2 to 1; 3 and 5 to 2; 4 and 6 to 3; 7 to 4; 8 to 5.

3. 1 and 2 to 1; 3 and 5 to 2; 4 and 7 to 3; 6 to 4; 8 to 5.

4. 1 and 2 to 1; 3 and 5 to 2; 4 and 8 to 3; 6 to 4; 7 to 5.

5. 1 and 2 to 1; 3 and 5 to 2; 4 to 3; 6 to 4; 7 to 5; 8 to 6.
B. A state is an assignment of the first I objects to bins 1 .. P with at
least 1 object in each bin. An operator is to place the I+1st object
either in a bin 1..P where it fits or in bin P+1. A goal state is
an assignment of all N objects.

C. The maximum branching factor is N, attained when all but the last
object have been assigned, each to a different bin. The depth of
the space is N; all goal nodes are at depth N. The space therefore
has no more than N^{N} states; in fact, this is a considerable
overestimate.

### Problem 2

Pruning first takes place at the state
"1 and 2 to 1; 3 and 5 to 2; 4 to 3; 6 to 4; 7 to 5". As shown
in problem 1.A, before this state is found, the search has already
found a couple of solutions of size 5. This state certainly cannot
lead to any state of size smaller than 5. Hence, we can prune here,
and need not consider assignments of object 8.
### Problem 3:

A. Heuristic 1 corresponds to ordering the children of the AND node,
and heuristic 2 corresponds to ordering the children of the OR node.
B.
Applying heuristic 1, the first solution found will be the optimal one:
5 and 3 to 1; 6 and 4 to 2; 8 and 2 to 3; 7 and 1 to 4.

Applying heuristic 2, the first several solutions will be the same.
The first case where this makes a difference is from state
"Objects 1 and 2 to 1; 3 to 2; 4 to 3; 5 to 4." Here using
heuristic 2, the search will first try to try the assignment of 6 to 4
before the assignment of 6 to 3.

The result of applying both heuristics, in this example, is the same
as the result of applying just the first.

C. Suppose that B=9 and that there are 6 objects with weights 5,3,3,3,2,2.
Then applying both heuristics, in the first solution found
the first bin will hold objects of weight 5 and 3; the second bin will hold
objects of weight 3, 3, and 2; and the third bin will have one object of
weight 2. However, in the optimal solution, the first bin has 5,2,2, and
the second has 3,3,3.

Back to course home page