<?xml version="1.0" encoding="windows-1252"?>
<node id="40319" title="RE: RE: RE: Re: Packaging Algorithm" created="2000-11-07 05:06:20" updated="2005-07-19 14:08:39">
<type id="11">
note</type>
<author id="20087">
extremely</author>
<data>
<field name="doctext">
One, Sphere packing is a special problem class, that is
especially hard to solve.  I shouldn't have mentioned it.
&lt;p&gt;Two, try it. But first, some numbers...
&lt;p&gt;Lets limit ourselves here. 10 boxes.  I'm not letting you
have cubical, so they have 6 orientations that matter.
We'll limit ourselves to 4 inch increments and reasonable
box sizes and so 52" is max.  That is boxes ranging from
1 to 13 "increments" on a side. (btw that is not 13**3 types
of boxes but it doesn't matter, we are only interested in
ten at a time. Discrete box sizes doesn't help at all anyway,
except if you can keep the number of positions low.) 
&lt;p&gt;Now, max and min cases, the container can't be smaller than 4x3x3
and 130x130x130 is clearly large enough.
&lt;p&gt;So, for each box to place you have around 2 million origins,
and 6 orientations.  For 10 boxes.  And in each of these
120 million cases, you have to determine that none of them
intersect.
&lt;p&gt;Just whip that out in perl real quick and run it. You can
do it with a 3d matrix or be fancy about it.  You can throw
entire sub trees out if you can tell that a case is already
bigger than the smallest case you've found so far.
&lt;p&gt;&lt;b&gt;It is still like 100 million cases you have to run,
brute force.&lt;/b&gt; It's an ugly problem and I've not seen
a good suggestion as to how to break it down much better
to throw out large sets of fails.  Worse, I don't think
anyone has found an "answer", a strategy that lets you
cut thru the brute-force approach and jump straight to the
answer.
&lt;p&gt;And I suppose you are correct that you can start small
and work your way up, but as I recall the algorithm in the
books is just a "pretty-good" solution that is a bug-out
brute-force.  That means you are going to repeat trying
cases you know are bad, over and over again as you go up
in size.  And you won't be &lt;b&gt;SURE&lt;/b&gt; you have the right
answer, just sure that you have &lt;b&gt;AN&lt;/b&gt; answer.
&lt;p&gt;I really don't want to be a spoilsport on this and 
&lt;em&gt;I don't know everything&amp;reg;&lt;/em&gt; but I'm pretty sure
this is a frustration fest.  Don't let me stop you guys from
trying tho. Just consider using a box you don't mind letting
sit a while. =)
&lt;p&gt;&lt;i&gt;-- &lt;br&gt;
$you = new YOU;&lt;br&gt;
honk() if $you-&gt;love(perl)&lt;/i&gt;</field>
<field name="root_node">
40304</field>
<field name="parent_node">
40318</field>
</data>
</node>
