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
 
  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; } }
     
    This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 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