On Oct 14, 7:41 am, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> wrote:
> Hi,
>
> I have a different number of different shaped profile bars which I
> need to fit into as few boxes as possible. The box has a fixed size.
> The profiles are always the same length, which means the problem only
> needs to be solved on 2 dimensions. The shape of the profiles are
> either rectangular or have an L-shape. During packing, the same type
> of profiles shall be packed together or near by.
>
> Here see a picture of an
> example:http://picasaweb.google.com/rlaemmler/ProfileBox/photo#51211558861254...
>
> I found a tool called Real Cut 2D which solves a similar problem but
> unfortunately only covers rectangular shaped
> figures.http://www.optimalprograms.com/RealCut2d.htm
>
> Has anybody a good algorithm or idea on how to solve this optimization
> problem?
>
> Thanks,
> Reto
This problem is certainly NP complete, so the best you will do is a
heuristic search algorithm. You should study the A-star (often
written A*) algorithm. (Adak's suggestion of minimax or alpha-beta
does not make sense to me because these are for two-player games.)
There are lots of design decisions. One is the heuristic function.
Another is how to compute successor configurations (all possible ways
of placing the next piece given a configuration of pieces alread
placed). This raises the question of how to represent bars packed in
boxes. A simple way would be to subdivide the box area into a grid.
Then a bar is just represented as a set of grid squares (a coordinate
list or a bitmap, for example). An interesting problem! I wish
someone would pay me to solve it!
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
