Układanie prostokątów w celu uzyskania możliwie małej przestrzeni

Question

Mam program, który obliczy minimalny obszar za pomocą dopasowania prostokątów.

Dane wejściowe: prostokąty o różnej wysokości i szerokości.
Wynik: Jeden prostokąt zawierający wszystkie te prostokąty.
Reguły: Nie można obracać ani obracać prostokątów i nie mogą się one nakładać.

Rozumiem, że jest to związane lub jest prawdopodobnie zdefiniowane jako problem z pakowaniem skrzynek (NP-hard). Jednak algorytmy, które znalazłem dla tych, którzy często ustawiają limit na przykład na szerokość. Nie mam takich ograniczeń, jedynym celem jest uzyskanie tak małego obszaru, jak to możliwe.

Jakieś wskazówki, jaki algorytm jest odpowiedni do uzyskania przyzwoitego rozwiązania?

Answer 1

http://www-rcf.usc.edu/~skoenig/icaps/icaps04/icapspapers/ICAPS04KorfR.pdf

Widocznie ten problem jest trudniejsze niż się wydaje na początku. Jest to interesujący algorytm, ponieważ najpierw odgaduje rozwiązanie, a następnie ulepsza je, więc jeśli nie chcesz czekać na optymalne rozwiązanie, możesz po prostu uruchomić go dla określonej liczby iteracji, aby uzyskać przybliżone rozwiązanie (dłuższe uruchomisz go, tym lepsze przybliżenie).

Answer 2

Zacznę od przeglądania przez http://mathworld.wolfram.com - są niesamowite na takie rzeczy.

Po drugie, mógłbym wyobrazić sobie algorytm dope, który umieści najdłuższy (w wymiarze X) okienko na dole, a następnie najwyższy (w wymiarze Y) na nim po jednej lub po drugiej stronie. Następnie kontynuuj układanie ich w ten "schodkowy" sposób, idąc w prawo w górę iw górę (na przykład idź w prawo, aż nie możesz, potem idź w górę itp.).

To prawdopodobnie nie jest idealny i może bardzo dobrze dać złe wyniki, ale to, co pierwszy wpadł na myśl.

Answer 3

Polecam zacząć od prostego chciwego podejścia i sprawdzenia, czy jest to wystarczająco dobre dla twoich potrzeb. Jeśli twój wkład jest dobrze zachowany lub mały, może to być wszystko, czego potrzebujesz - a złożoność wzrośnie szybko, gdy spróbujesz zrobić coś bardziej wyrafinowanego.

Na przykład: sortuj prostokąty według wielkości, największe jako pierwsze. Dodaj prostokąty po jednym na raz, próbując każdej możliwej pozycji dla nowego prostokąta. Wybierz pozycję, która spowoduje najmniejsze pole ograniczające.

Innym chciwym podejściem byłoby wybieranie początkowego prostokąta, a następnie wielokrotne dodawanie prostokąta, który daje najbardziej zwarty układ (gdzie gęstość jest zdefiniowana jako procent wypełnionego obszaru obwiedni).