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"

>
>

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"

>
>

Then move across the next possibilities at that level:

Changed:

<
<

src="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_first_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"

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