# Difference: DepthFirstSearch (4 vs. 5)

Line: 1 to 1

 META TOPICPARENT name="SetPartitioning"

# Depth-First Search for Enumeration

Line: 73 to 73
let number[current] := number[current] + 1; } else { # Too many cut, backtrack up the tree
Deleted:
<
<
print "Problem"; display current, number;
let number[current] := 0; if current = first(ROLLS) then let stillSearching := 0;
Line: 82 to 80
let current := prev(current, ROLLS); let number[current] := number[current] + 1; }
Deleted:
<
<
display current, number;
} } while stillSearching;
Line: 94 to 91
We start at the root node and search on the first possibility at level 1 (the 5cm rolls):
```
```
Changed:
<
<
let current := first(ITEMS);
>
>
# Start with the first product and no ROLLS being cut let current := first(ROLLS);
let number[current] := 0; let stillSearching := 1;
Line: 103 to 101

1. If we are not at the lowest level (the 9cm rolls) and we have a valid possibility for this node then dive to the next level:
```
```
Changed:
<
<
if ( current <> last(ITEMS) ) and
>
>
if ( current <> last(ROLLS) ) and
( number[current] <= MaxPossible[current] ) then {
Changed:
<
<
let current := next(current, ITEMS);
>
>
let current := next(current, ROLLS);
let number[current] := 0; }
Changed:
<
<
• If we are at the last level and have a valid possibility, then evaluate the pattern we have found and move to the next possibility:
• >
>
• If we are at the last level (current = last(ROLLS)) and have a valid possibility, then evaluate the pattern we have found and move to the next possibility:
•
```  else if number[current] <= MaxPossible[current] then {

```
Changed:
<
<
# current = last(ITEMS), cutting pattern found
>
>
# current = last(ROLLS), cutting pattern found
# Save the pattern
Changed:
<
<
if ( sum {i in ITEMS} number[i] * Length[i] <= TotalLength) and ( TotalLength - sum {i in ITEMS} number[i] * Length[i] < MinLength) then {
>
>
if ( sum {i in ROLLS} number[i] * Length[i] <= TotalLength) and ( TotalLength - sum {i in ROLLS} number[i] * Length[i] < MinLength) then {
let newPattern := card(PATTERNS) + 1; let PATTERNS := PATTERNS union {newPattern};
Changed:
<
<
let {i in ITEMS} PatternYield[newPattern, i] := number[i]; }
>
>
let YIELDS[newPattern] := {i in ROLLS : number[i] > 0}; let {i in YIELDS[newPattern]} PatternYield[newPattern, i] := number[i];
} # Increase the number cut let number[current] := number[current] + 1;
Line: 129 to 127
else { # Too many cut, backtrack up the tree let number[current] := 0;
Changed:
<
<
if current = first(ITEMS) then
>
>
if current = first(ROLLS) then
let stillSearching := 0; else {
Changed:
<
<
let current := prev(current, ITEMS);
>
>
let current := prev(current, ROLLS);
let number[current] := number[current] + 1; } }

Copyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback