Re: Packaging Algorithm

[mitd]

With all do respect to our esteemed monk extremely is this not closer to the 'Knapsack' and 'bin packing' class of problems which can be solved using several non-brute force techniques therefore do not fall into the general class of NP-Complete problems.

There are several books that cover detailed solutions to these kinds of problems. My personal favourite is 'ALGORITHMS', Robert Sedgewick, Addison-Wesley, 1983.

Sedgewick describes some excellent approaches to your problem.

Computer Algorithms, Inroduction to Design and Analyssis, Sara Base, Addison-Wesley 1988 is also a good source.

mitd-Made in the Dark
'My favourite colour appears to be grey.'

[extremely]

Actually, no it isn't like a bin-packing problem. It's like the sphere-packing problem. It is unbounded since he specifically asked for the smallest container. I'm pretty sure that is a rather bit nastier than bin-packing, since the only way to find the answer is to run the bin-packing work on a huge series of various container sizes. As I recall, that was what made this such a nasty problem, there isn't a specific strategy for finding the "best" answer, just a good strategy for finding a "fair" answer for a single facet of the problem.

OTOH, mentioning Sedgewick's book is good enough for a ++ in my book, anyday =) And you are correct in that refactoring the problem can surely help make it solvable.

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

[Fastolfe]

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.

[extremely]

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)

[tye]

BTW, I used to work for a guy who had several good solutions for packing spheres. He used them for designing composites (for example, what mixes of sizes of gravel to use for certain types of concrete). One involved selecting spheres from the chosen mix at random and dropping them into a virtual cylinder and letting them settle. Sure, he wasn't proving the maximally tightest possible packing. But he was able to make good predictions about how certain mixes of sizes of spheres would pack in practice.

He also sometimes repeated the experiment of make a bunch of spheres, put them in a bag, squeeze the bag for a few days, poor wax in, let it cool, remove bag, analyze positions of spheres.

Don't let someone's proof that some problem is impossible to solve prevent you from solving the problem well enough to get your work done!

        - tye (but my friends call me "Tye")

[extremely]

Don't let someone's proof that some problem is impossible to solve prevent you from solving the problem well enough to get your work done!
(smartest thing said so far in this whole discussion.)

Well, again, "the sphere packing problem" is different than that. In fact, there have been some neat breakthru's in the field. We have 9600 baud and up modems thanks to a trellis-code based on packing spheres efficiently in 8 dimensions. Turns out a single sphere can be touched by 1024 spheres in a tightly-packed regular array. =) That result is basically cool in anyone's book.

The original problem was that given a bunch of spheres that are the same size, how many can you get to touch a single sphere at the same time. In 2d, the answer is clearly 6. (try it with pennies.) In 3d, 12 is the answer but if you look at the spherical cone of impact that each outer sphere makes, it would seem that 13 COULD be possible. The deal is that no one has found a function that provably states for each dimension what the number is. Only a special case exists for multiples of 8. High-weirdness, plain and simple.

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