Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
One, Sphere packing is a special problem class, that is especially hard to solve. I shouldn't have mentioned it.

Two, try it. But first, some numbers...

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.)

Now, max and min cases, the container can't be smaller than 4x3x3 and 130x130x130 is clearly large enough.

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.

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.

It is still like 100 million cases you have to run, brute force. 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.

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 SURE you have the right answer, just sure that you have AN answer.

I really don't want to be a spoilsport on this and I don't know everything® 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. =)

--
$you = new YOU;
honk() if $you->love(perl)


In reply to RE: RE: RE: Re: Packaging Algorithm by extremely
in thread Packaging Algorithm by marius

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others chanting in the Monastery: (9)
    As of 2014-08-20 21:02 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      The best computer themed movie is:











      Results (124 votes), past polls