Pre-Class Lecture 17
Please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.
1) Pruning a Decision Tree
Recall the movie-marathon example from the previous lesson. You and your friends had six possible movies but only enough time to watch exactly three. To find every possible group, we used a decision tree that made one choice for each movie: include it in the marathon or leave it out. This generated the full power set of 2^6 = 64 movie combinations. We then filtered those combinations and kept only the groups containing exactly three movies.
That approach is correct, but it explores many branches whose results will eventually be filtered out.
If we control the recursion directly, we can stop exploring a branch as soon as we know that none of its descendants can produce a useful answer. This is called pruning. Pruning does not discard possible valid answers; it skips a branch only after the constraints prove that the branch is complete or impossible.
For fixed-size subsets, let size mean "the number of additional items this branch still needs to choose." At each node, the next item creates two decisions:
- exclude it: recurse on the remaining items with the same
size, or - include it: recurse on the remaining items with
size - 1, then add the item to each returned subset.
For example, suppose we need to choose three movies from ["A", "B", "C", "D", "E", "F"]. After choosing "A" and excluding "B", the remaining subproblem is:
subsets_with_size(["C", "D", "E", "F"], 2)
The node records that four movies remain and two more must be chosen. Before expanding any node, ask:
- Has this branch already selected as many items as it needs?
- Are enough items left to select as many as it still needs?
|
Question 1: In each call, size is the number of additional movies the branch must select. Which states can stop without making another recursive call? Check all that apply.
|
These observations give us two stopping conditions. If size == 0, the branch has made all the selections it needs. It returns [set()] so that earlier recursive calls can add the items they chose. If size > len(items), the branch needs more items than remain, so it cannot produce a valid subset and returns [].
def subsets_with_size(items, size):
if size == 0:
return [set()] # this branch is complete
if size > len(items):
return [] # this branch is impossible
first, rest = items[0], items[1:]
without_first = subsets_with_size(rest, size)
with_first = [
{first} | subset
for subset in subsets_with_size(rest, size - 1)
]
return without_first + with_first
Consider subsets_with_size(["F"], 2). Without pruning, the function would explore branches that include or exclude "F", even though neither could select the two movies still needed. The second stopping condition returns [] immediately and skips that unnecessary work.
|
Question 2: Which statements correctly describe pruning in subsets_with_size? Check all that apply.
|
Decision trees generate combinations by making an include-or-exclude choice for each item. To find subsets of a desired size, we could generate the full power set and then filter its results. However, we can work more efficiently by pruning a branch as soon as it cannot produce a valid result. For example, once a branch has accumulated the target number of items, there is no need to keep exploring choices that add more items. We can extend this idea from constraints on the number of selected items to constraints on their total weight, which leads us to the knapsack problem in the next section.
2) Decision Tree Example
Imagine that you are packing a bag for a day on campus. Your bag can hold at most 10 pounds, and you are deciding whether to pack each of these items:
- a laptop weighing 5 pounds,
- a textbook weighing 4 pounds,
- lunch weighing 2 pounds, and
- a jacket weighing 3 pounds.
A decision tree can represent every possible packing list. At each level, you consider one item and create two branches: one where you leave it out and one where you pack it. For example, after considering the laptop and textbook, one node might represent the state laptop packed, textbook left out, 5 pounds used. A node therefore needs to record the choices made so far and enough information, such as the current weight, to decide which choices remain valid.
|
Question 3: Which description would be most useful as a node in this decision tree?
|
|
Question 4: When the tree considers the jacket, what do its two outgoing branches represent?
|
We do not need to follow every branch to the bottom. If a node represents a bag that is already over the 10-pound limit, adding or excluding later items cannot make the items already packed weigh less. We can prune that node and all of its descendants. We can also stop exploring once every item has been considered, because that node already represents a complete packing list.
|
Question 5: Which situations can stop being explored immediately? Check all that apply.
|
3) Knapsack Problem
So far, our decision-tree examples have treated every selected item the same: we either generated every subset or required a subset to contain a particular number of items. The knapsack problem adds two pieces of information to each item: a weight and a value. Instead of finding every subset of a certain size, we must find the subset with the greatest total value whose total weight stays within a capacity limit. The tree still makes an include-or-exclude decision for each item, but deciding whether a branch is useful now depends on the combined weights and values of the selected items.
In the knapsack problem, we must choose a subset of available items that maximizes total value without exceeding a fixed weight capacity. In the fractional version, we may take part of an item. In the discrete 0/1 knapsack version, each item must be either included or excluded. This class looks at the discrete version, where you either take an entire item or you exclude the entire item.
Suppose a knapsack can hold 10 grams and we can choose among a 5-gram gold bar worth $250, 4 grams of saffron worth $240, and a 3-gram diamond worth $1,500. Taking the items in descending order of value per gram selects the diamond and saffron, worth $1,740, but choosing the diamond and gold instead produces the better total of $1,750. This example shows why a greedy strategy based on value, value per unit weight, or weight can miss the optimal combination. Although greedy strategies are fast and may produce a good approximation, solving 0/1 knapsack exactly requires considering how the items' weights and values interact.