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