Difference: DepthFirstSearch (4 vs. 5)

Revision 52008-05-07 - TWikiAdminUser

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

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; } }

View topic | History: r6 < r5 < r4 < r3 | More topic actions...