Exhaustive Search
The solutions in Figures
9 and
10 are pretty good. But can you do better?
If you look closely, you'll see that each solution has a row with 6 used squares. Each solution also has 11 unused squares on other rows. In theory at least, if you could rearrange things to move those 6 used squares onto other unused squares, then you could eliminate the six-used-squares row and shorten the solution by another unit to a height of 12.
That result shows that we cannot prove there is no better solution, but it doesn't tell you whether a better solution is actually possible. In fact, you
can achieve a better solution. You might want to spend a few minutes trying to find it before you read further.
For a relatively small problem such as this one, you can resort to exhaustive search. The heart of the sample program's exhaustive search is the
FillExhaustive subroutine shown in the following code:
Private Sub FillExhaustive(ByRef best_rects() As Rectangle, _
ByRef best_max_y As Integer, ByVal rects() As Rectangle, _
ByVal next_i As Integer, ByVal used(,) As Boolean)
' See if we're at a leaf node.
If next_i >= rects.Length Then
' We're at a leaf node.
' See if this solution is an improvement.
Dim max_y As Integer = MaxY(rects)
If best_max_y > max_y Then
best_max_y = max_y
best_rects = DirectCast(rects.Clone(), Rectangle())
End If
Else
Dim rect As Rectangle = rects(next_i)
For y As Integer = 0 To _
used.GetUpperBound(1) - rect.Height + 1
For x As Integer = 0 To _
used.GetUpperBound(0) - rect.Width + 1
' See if we can put the rectangle here.
Dim can_fit As Boolean = True
For i As Integer = 0 To rect.Width - 1
For j As Integer = 0 To rect.Height - 1
If used(x + i, y + j) Then
can_fit = False
Exit For
End If
Next j
If Not can_fit Then Exit For
Next i
' Give it a try.
If can_fit Then
' Put the rectangle here.
rects(next_i).X = x
rects(next_i).Y = y
For i As Integer = 0 To rect.Width - 1
For j As Integer = 0 To rect.Height - 1
used(x + i, y + j) = True
Next j
Next i
' Recurse.
FillExhaustive(best_rects, best_max_y, _
rects, next_i + 1, used)
' Un-put the rectangle here.
For i As Integer = 0 To rect.Width - 1
For j As Integer = 0 To rect.Height - 1
used(x + i, y + j) = False
Next j
Next i
End If
Next x
Next y
End If
End Sub
The
best_rects parameter is an array containing the current best solution, while
best_max_y is the height of that solution. The
rects array contains all the rectangles;
next_i is the index of the next rectangle that the algorithm must position. The
used array holds one entry for each square in the stock and contains true if a square is in use by a rectangle.
The code starts by checking whether every rectangle has been positioned. If so, it's reached a possible solution. The code compares this solution's
best_max_y value to others and saves this solution if it improves on the previous best solution.
If all the rectangles have not yet been positioned, then the code tries placing rectangle number
next_i in every possible position. The code loops through each possible X and Y position, skipping coordinates where the rectangle would fall partly off of the stock's right or bottom edge. For each possible position, the code tests the
used array to see if the rectangle can fit without overlapping another previously positioned rectangle.
When a rectangle can fit at a position, the subroutine puts it there, updates the used array, and recursively calls itself to position the remaining rectangles.
 | |
| Figure 11. Exhaustive Solution: By testing every possible arrangement, the exhaustive solution finds the best possible answer. |
After the recursive call returns, the subroutine removes the rectangle from its position and continues its loop, trying to place the rectangle in other locations.
When the original call to position the first rectangle finishes, the program has tried every possible arrangement of the rectangles and has found the best possible solution.
Figure 11 shows the result—with a total height of only 12 units. This solution contains only 5 unused squares and the emptiest row contains 7 used squares so I'm fairly confident that you won't be able to find a better solution than this one. Table 1 summarizes the results of the heuristics you've seen.
Table 1. Heuristics Summary: Sorting by the total height of stock used, here are the results of the various heuristics evaluated in this article.
| Heuristic |
Total Height |
| Two Columns |
18 |
| One Column |
16 |
| Sort by Height |
14 |
| Sort by Width |
14 |
| Sort by Area |
14 |
| Sort by Squareness |
15 |
| Fill by Stripes |
13 |
| Recursive Division |
13 |
| Exhaustive |
12 |
The first several, Two Columns through Sort by Squareness, are relatively straightforward and produce fairly good results, but their main advantage is that they're also extremely fast, so your best bet is to try them all and pick the best result.
The Fill by Stripes algorithm is much more complicated and requires some fairly tricky recursion, so it takes longer than the previous algorithms, but it's fast enough that speed isn't much of an issue. In one test, the first few algorithms took no noticeable time to arrange 50 rectangles, while Fill by Stripes took about 0.30 seconds.
Recursive Division uses a much more complete recursion, so it takes some serious time. One test took 38 seconds to position only 10 rectangles.
Finally exhaustive search takes the longest. In one test this algorithm took 45 seconds to position a mere eight rectangles. You can see that it's probably not possible to use an exhaustive method to position more than nine or ten rectangles in a reasonable amount of time.
Other heuristics are certainly possible, and you may be able to come up with some that beat these algorithms at least some of the time.
For any given stock width and collection of rectangles, different heuristics will produce different results. To get the best results, try the fastest algorithms first, and pick the best solution they produce. Then if you have time, rewrite the Recursive Division and Exhaustive algorithms so they display good solutions as they find them—and let the programs rip. Then, at any point during execution, you can decide whether the current best solution is good enough, or whether you want to wait and give these slower algorithms a chance to find even better solutions.
It's also possible that other heuristics will find better solutions for certain arrangements of shapes. If you discover any that work well,
let me know and I'll make them available on the
VB Helper web site.
Previous Page
