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 NN 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