Difference: DepthFirstSearch (2 vs. 3)

Revision 32008-05-07 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SetPartitioning"

Depth-First Search for Enumeration

Line: 70 to 70
  Let's break down what is happening in detail. This code is performing a depth-first search of possible cutting patterns:
Changed:
<
<
src="dfs_tree.jpg"
>
>
dfs_tree.jpg
  We get the maximum number of each type of roll that can be cut from the 20cm rolls from {\tt MaxPossible}. This defines the number of nodes at each level in the decision tree.
Line: 121 to 121
  Proceeding this way we dive to the first leaf node at the bottom left of the decision tree first:
Changed:
<
<
src="dfs_first_pattern.jpg"
>
>
dfs_first_pattern.jpg
  Then move across the next possibilities at that level:
Changed:
<
<
src="dfs_second_pattern.jpg"
>
>
dfs_second_pattern.jpg
  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.

-- MichaelOSullivan - 07 May 2008

Deleted:
<
<
  • dfs_tree.jpg:
    dfs_tree.jpg

  • dfs_first_pattern.jpg:
    dfs_first_pattern.jpg

  • dfs_second_pattern.jpg:
    dfs_second_pattern.jpg
 
META FILEATTACHMENT attachment="dfs_tree.jpg" attr="h" comment="" date="1210150393" name="dfs_tree.jpg" path="dfs_tree.jpg" size="76660" stream="dfs_tree.jpg" tmpFilename="" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="dfs_first_pattern.jpg" attr="h" comment="" date="1210150473" name="dfs_first_pattern.jpg" path="dfs_first_pattern.jpg" size="87068" stream="dfs_first_pattern.jpg" tmpFilename="" user="MichaelOSullivan" version="1"
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback