Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation

RE: RE: Re: Packaging Algorithm

by Fastolfe (Vicar)
on Nov 07, 2000 at 09:34 UTC ( #40318=note: print w/ replies, xml ) Need Help??

in reply to RE: Re: Packaging Algorithm
in thread Packaging Algorithm

Why a sphere? He has a bunch of boxes. This seems perfect for a bin-packing problem. He just needs to try the algorithm against successively larger containers until he's able to fit everything. He's followed up with a comment indicating that he's already planned to limit himself to a pre-determined discrete set of box sizes.

Comment on RE: RE: Re: Packaging Algorithm
RE: RE: RE: Re: Packaging Algorithm
by extremely (Priest) on Nov 07, 2000 at 10:06 UTC
    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)

      Okay, how many crate sizes can you buy at U-Haul? Or are you expecting him to buy sheet cardboard and build a custom crate in order to achieve maximal packing? The number of crate sizes to try is just a few. But then, I wouldn't try any sizes of crates at all!

      Where did you get this crazy idea to try every possible origin for a package? If I put packages together tightly, then every package shares part of a side with another package. And we aren't talking about some theory trying to prove that we have the maximally tightest packing (which would be very hard, sure). Just assume that a reasonable packing exists where one package hits a corner of the crate (when was the last time you put packages in a crate in such a way that no package shared a corner with the crate?).

      Now all you have to do is place a package in the corner of an infinite box (the positive octant) and add boxes in the resulting "corners". As you place boxes, keep track of the bounding crate. Iterate through all of the possibilities. Sure, this isn't trivial to code and the number of possiblities is huge. If you have a large number of packages, then try at random and report the best solution so far once you are tired of waiting. Who cares if it is brute force? Also, if you haven't placed all of the boxes yet and you are already worse off then your best solution so far, no need to continue adding packages.

      Take N boxes.
      First box: N choices (orientation doesn't matter yet)
      Second box: N-1 boxes * <=3 corners * 6 orientations
      Third box: N-2 boxes * <=5 corners * <=6 orientations

      If I change the *3*5*7*9... terms to *4*6*8*10... then we are bounded by N! * 2^(N-1)*N! * 6^(N-1) == N!^2 * 12^(N-1). So assuming a worse-than-worst-possible case where we don't trim any chunks from the decision tree (we try all of the combinations in exactly the wrong order and don't eliminate overlapping boxes until we've placed all boxes), then we can still exhaustively search for 5 packages pretty quickly.

      For 6 or 7, easy trimming of the decision tree might let you exhaustively search (hard to predict). For more than 7, you'd probably have to settle for stopping early and having a less optimal solution.

      Brute force is often a very good way to solve real-life problems. That is why they computers that are fast. (:

              - tye (but my friends call me "Tye")
        You've just traded fewer iterations for a more complex inner loop. My point was and still is that the job doesn't have a clean strategy to "solving" it. Thus brute force, however fancy you choose to get, still multiplies quickly to the not-in-my-lifetime stage. Of course that is what you wound up saying too. =) {and I did say you could be fancy with the code, just that it just gains you a few packages}.

        Also, I still say it doens't matter how many different sizes of box there are in the world. He didn't ask that question. No matter tho, it's just beating a dead horse.

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

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://40318]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (7)
As of 2014-07-28 22:48 GMT
Find Nodes?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:

    Results (210 votes), past polls