Introduction to Artificial Intelligence: Problem Set 1

Assigned: Jan. 17
Due: Jan. 24

The KNAPSACK problem is defined as follows: You are given a collection of N objects. Each object has a specified weight and a specified value. You are given a capacity, which is the maximum total weight you can carry, and a quota, which is the minimum total value that you want to get. The problem is to find a subset of the objects whose total weight is at most equal to the capacity and whose total value is at least equal to the quota.

For example, suppose that you are given three objects:

  Object      Weight     Value
    A          70         80
    B          50         50
    C          50         50
and you are given a capacity of 110 and a quota of 90. Then a solution to the problem is the set { B,C }. Note that there is no solution involving object A, because once you have put A in the knapsack, there is no room for the other two. (You are not allowed to choose a fraction of an object.)

It is believed that there is no efficient algorithm that always finds a solution to KNAPSACK when one exists. (In the technical jargon, the problem is NP-complete.)

Problem 1

This problem can be formulated as state-space search as follows: Arrange the objects in some order O. A state is any set of objects whose total weight is not more than than the capacity. An operator on state S is to find an object X in S such that Weight(S) + Weight(X) <= Capacity and such that the name of X is later in order O than any of the objects in S, and add X to S. A goal state is one whose value is greater than or equal to the quota. The start state is the empty set.

A. Is this state space a tree? Explain your answer.

Answer: Yes. Because of the restriction that objects are added to set S in the order they are given in O, there is only one way of creating a given set S, and therefore only one path to the state S.

B. What is the maximum branching factor, as a function of N, the number of objects?

Answer: At the root, the branching factor is N. At all other states, the branching factor is less than N. Hence, the maximum branching factor for the space is N

C. Give an upper bound on the distance from the start state to the goal state, as a function of N.

Answer: There can be at most N operations from the start state to any other state, as each operation adds another element to S.

D. Give an upper bound on the maximum size (number of states) in the state space, as a function of N.

Answer: A crude answer would be [Branching factor] ** [Depth]; i.e. NN. A better estimate would be to observe that there are 2N different subsets of N objects, and hence at most 2N different states. This bound can actually be acheived, if the only solution involves putting all the objects in the knapsack.

E. Consider the following collection of objects:

Name:      A    B    C    D    E    F    G    H    I    
Weight:   70   60   50   40   30   20   10   10    1  
Value:   260  245  200  100   80   65   60   60   10
with a capacity of 100 and a quota of 400.

Assume that different branches of the search spaces are explored in alphabetical order. What is the first solution that is found in a depth-first search?

Answer: {B,F,G,H}

Problem 2

In problem 1, we explored the space by starting with an empty knapsack and adding one object at a time, as long the total weight was at most the capacity. An alternative method of solving the problem is to start with all the objects in the knapsack, and gradually remove objects, as long as the total value of the objects in the knapsack is at least as great as the quota.

A. Characterize this search method formally, after the style of problem 1. (That is, what is a state? What is an operator? What is the goal? What is the start state.)

Answer:A state is a set of objects whose total value is at least the quota. The operator is to remove an object that comes later in order O than any object previously removed. The goal is a state whose total weight is at most the capacity. The start state is the set of all objects.

B. Using the same collection of objects as in Problem 1, part E, and assuming, again, that different branches are explored in alphabetical order, what is the first solution that is found in a depth-first search?

Answer: {C,E,G,H}