DepthFirstSearch < OpsRes

Tags: view all tags
---+ Depth-First Search for Enumeration 

One common method of generating patterns for [[SetPartitioning][set partitioning problems]] is to use a [[https://en.wikipedia.org/wiki/Depth-first_search][depth-first search]] to find feasible patterns/schedules/sets.

---++ Depth-First Search in AMPL

Depth-first search is usually implemented using recursion, but AMPL does not have functions, so does not support recursion. However, we can implement a depth-first search non-recursively.

Consider the depth-first search code from the [[SpongeRollProductionProblem][Sponge Roll Production Problem]]:
<pre>
reset;

model cutting_stock_col.mod;
data cutting_stock_col.dat;

param TotalLength;
param Length {ROLLS} >= 0;

data;

param TotalLength := 20;

param Length :=
 A    5
 B    7
 C    9
 ;

model;

reset data PATTERNS, YIELDS, PatternYield; # Remove any pattern data, we will find it automatically

# Search the possibilities for cutting patterns
param MinLength := min {i in ROLLS} Length[i]; # Find the minimum length of all the ROLLS
param MaxPossible {i in ROLLS} >= 0, integer # Find the maximum number of each length item
        := TotalLength div Length[i];        # that can be cut from a roll

# The current product being considered
param current symbolic within ROLLS;
# The number of each product being cut
param number {ROLLS} >= 0, integer, default 0;
# Are we still searching?
param stillSearching binary;

# Any new pattern found
param newPattern > 0, integer;

let PATTERNS := {};
# Start with the first product and no ROLLS being cut
let current := first(ROLLS);
let number[current] := 0;
let stillSearching := 1;
repeat {
  display current, number;
  if ( current <> last(ROLLS) ) and
     ( number[current] <= MaxPossible[current] ) then {
       let current := next(current, ROLLS);
       let number[current] := 0;
  }
  else if number[current] <= MaxPossible[current] then {
    # current = last(ROLLS), cutting pattern found
    # Save the pattern
    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};
      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;
  }
  else { # Too many cut, backtrack up the tree
    let number[current] := 0;
    if current = first(ROLLS) then
      let stillSearching := 0;
    else {
      let current := prev(current, ROLLS);
      let number[current] := number[current] + 1;
    }
  }
} while stillSearching;
</pre>
Let's break down what is happening in detail. This code is performing a depth-first search of possible cutting patterns:

<img src="%ATTACHURLPATH%/dfs_tree.jpg" alt="dfs_tree.jpg" width='681' height='356' />

We get the maximum number of each type of roll that can be cut from the 20cm rolls from =MaxPossible=. This defines the number of nodes at each level in the decision tree.

We start at the root node and search on the first possibility at level 1 (the 5cm rolls):
<pre>
# Start with the first product and no ROLLS being cut
let current := first(ROLLS);
let number[current] := 0;
let stillSearching := 1;
</pre>

Then, we enter the loop. Each iteration through the loop starts with a node and decides where to move to from that node. There are 3 possibilities:
<ol>
<li>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:
<pre>
  if ( current <> last(ROLLS) ) and
     ( number[current] <= MaxPossible[current] ) then {
       let current := next(current, ROLLS);
       let number[current] := 0;
  }
</pre>
<li>If we are at the last level (<tt>current = last(ROLLS)</tt>) and have a valid possibility, then evaluate the pattern we have found and move to the next possibility:
<pre>
  else if number[current] <= MaxPossible[current] then {
    # current = last(ROLLS), cutting pattern found
    # Save the pattern
    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};
      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;
  }
</pre>
<li>If we have exhausted our possibilities at our current level then <i>backtrack</i> to the previous level and look at the next possibility. If we are at the top level (the 5cm rolls) then we have finished searching the tree:
</pre>
  else { # Too many cut, backtrack up the tree
    let number[current] := 0;
    if current = first(ROLLS) then
      let stillSearching := 0;
    else {
      let current := prev(current, ROLLS);
      let number[current] := number[current] + 1;
    }
  }
</pre>
Proceeding this way we dive to the first _leaf node_ at the bottom left of the decision tree first:

<img src="%ATTACHURLPATH%/dfs_first_pattern.jpg" alt="dfs_first_pattern.jpg" width='681' height='362' />

Then move across the next possibilities at that level:

<img src="%ATTACHURLPATH%/dfs_second_pattern.jpg" alt="dfs_second_pattern.jpg" width='681' height='367' />

Once all possibilities are exhausted we move back up the tree and move to the next possibility at that level before diving again.

Finally, we will backtrack from the last leaf node (bottom right) and complete our depth-first traversal of the decision tree.

-- Main.MichaelOSullivan - 07 May 2008
Topic revision: r6 - 2008-05-07 - TWikiAdminUser