Pakowanie prostokątne

Pakowanie prostokątne to problem pakowania , w którym celem jest ustalenie, czy dany zestaw małych prostokątów można umieścić wewnątrz danego dużego wielokąta, tak aby żadne dwa małe prostokąty nie zachodziły na siebie. Zbadano kilka wariantów tego problemu.

Pakowanie identycznych prostokątów w prostokąt

W tym wariancie istnieje wiele wystąpień pojedynczego prostokąta o rozmiarze ( l , w ) i większego prostokąta o rozmiarze ( L , W ). Celem jest upakowanie jak największej liczby małych prostokątów w dużym prostokącie bez nakładania się między prostokątami (małymi lub dużymi). Typowe ograniczenia tego problemu obejmują ograniczenie obrotu małego prostokąta do wielokrotności 90 ° i wymaganie, aby każdy mały prostokąt był prostopadły do ​​dużego prostokąta.

Ten problem ma pewne zastosowania, takie jak ładowanie skrzynek na palety, a konkretnie składowanie miazgi drzewnej . Przykładowy wynik: w duży prostokąt o wymiarach (1600,1230) można spakować 147 małych prostokątów o wymiarach (137,95).

Pakowanie identycznych kwadratów w prostoliniowy wielokąt

Biorąc pod uwagę prostoliniowy wielokąt (którego boki przecinają się pod kątem prostym ) R na płaszczyźnie, zbiór S punktów w R oraz zbiór identycznych kwadratów, celem jest znalezienie jak największej liczby niezachodzących na siebie kwadratów, które można upakować punkty S. _

Załóżmy, że dla każdego punktu p w S wstawiliśmy kwadrat o środku w p . Niech G S będzie wykresem przecięcia tych kwadratów. Kwadratowe upakowanie jest równoważne niezależnemu zbiorowi w GS . Znalezienie największego upakowania kwadratowego jest NP-trudne; można to udowodnić redukując z 3SAT .

Pakowanie różnych prostokątów w dany prostokąt

W tym wariancie małe prostokąty mogą mieć różną długość i szerokość i powinny być upakowane w dany duży prostokąt. Problem decyzyjny, czy takie upakowanie istnieje, jest NP-trudny . Można to udowodnić przez redukcję z 3-partycji . Biorąc pod uwagę przypadek 3-podziału z 3 m dodatnimi liczbami całkowitymi: a 1 , ..., a 3 m , z całkowitą sumą m T , konstruujemy 3 m małe prostokąty, wszystkie o szerokości 1, takie, że długość prostokąta i jest a ja + m . Duży prostokąt ma szerokość m i długość T + 3 m . Każde rozwiązanie instancji z 3 partycjami indukuje upakowanie prostokątów w m podzbiorów, tak że całkowita długość w każdym podzbiorze wynosi dokładnie T , więc dokładnie pasują do dużego prostokąta. I odwrotnie, w każdym opakowaniu dużego prostokąta nie może być żadnych „dziur”, więc prostokąty nie mogą być obracane. Dlatego upakowanie musi obejmować dokładnie m rzędów, gdzie każdy rząd zawiera prostokąty o łącznej długości dokładnie T . Odpowiada to rozwiązaniu instancji z 3 partycjami.

Gdy istnieje dodatkowe ograniczenie, że opakowanie musi być dokładne (bez marnowania miejsca), małe prostokąty można obracać tylko o wielokrotność 90°. W tym przypadku problem leży w NP . Bez tego wymogu małe prostokąty można obracać pod dowolnymi kątami. W tym bardziej ogólnym przypadku nie jest jasne, czy problem jest w NP, ponieważ znacznie trudniej jest zweryfikować rozwiązanie.

Pakowanie różnych prostokątów w prostokąt o minimalnej powierzchni

W tym wariancie małe prostokąty mogą mieć różne długości i szerokości, a ich orientacja jest stała (nie można ich obracać). Celem jest umieszczenie ich w otaczającym prostokącie o minimalnej powierzchni, bez granic na szerokości lub wysokości otaczającego prostokąta. Ten problem ma ważne zastosowanie w łączeniu obrazów w jeden większy obraz. Strona internetowa, która ładuje pojedynczy większy obraz, często renderuje się w przeglądarce szybciej niż ta sama strona ładująca wiele małych obrazów, ze względu na obciążenie związane z żądaniem każdego obrazu z serwera WWW. Problem jest ogólnie NP-zupełny , ale istnieją szybkie algorytmy do rozwiązywania małych przypadków.

Powiązane problemy

  • Cięcie gilotynowe jest wariantem pakowania prostokątnego, z dodatkowym ograniczeniem, że prostokąty w opakowaniu powinny być rozdzielne tylko przy użyciu cięć gilotynowych .
  • Maksymalny zbiór rozłączny (lub Maksymalny zbiór niezależny ) to problem, w którym zarówno rozmiary, jak i położenie prostokątów wejściowych są ustalone, a celem jest wybranie największej sumy nienakładających się prostokątów. Natomiast w pakowaniu prostokątnym (podobnie jak w rzeczywistych problemach z pakowaniem) rozmiary prostokątów są podane, ale ich położenie jest elastyczne. Niektóre dokumenty używają terminu „pakowanie”, nawet jeśli lokalizacje są ustalone.
  1. Bibliografia   _ Lobato, RD; Morabito, R (2010). „Efektywne podejście do partycjonowania rekurencyjnego do pakowania identycznych prostokątów w prostokącie”. Dziennik Towarzystwa Badań Operacyjnych . 61 (2): 306–320. doi : 10.1057/jors.2008.141 . S2CID 12718141 .
  2. Bibliografia   _ Paterson, Michael S.; Tanimoto, Steven L. (13.06.1981). „Optymalne upakowanie i pokrycie w płaszczyźnie są NP-zupełne” . Listy dotyczące przetwarzania informacji . 12 (3): 133–137. doi : 10.1016/0020-0190(81)90111-3 . ISSN 0020-0190 .
  3. ^   Demaine, Erik D.; Demaine, Martin L. (2007-06-01). „Puzzle, dopasowywanie krawędzi i pakowanie Polyomino: połączenia i złożoność” . Grafy i kombinatoryka . 23 (1): 195–208. doi : 10.1007/s00373-007-0713-4 . ISSN 1435-5914 .
  4. ^ ab Demaine , Erik (2015). „MIT OpenCourseWare - Łatwa twardość 2 - 3-partycja I” . YouTube .
  5. Bibliografia   _ Korf, RE (2013-01-23). „Optymalne pakowanie prostokątne: podejście do umieszczania bezwzględnego” . Dziennik badań nad sztuczną inteligencją . 46 : 47–87. doi : 10.1613/jair.3735 . ISSN 1076-9757 .
  6. ^ „Szybka optymalizacja algorytmu pakowania prostokątów do budowania duszków CSS” . www.codeproject.com . Źródło 2020-09-09 .
  7. ^   Chan, TM (2003). „Schematy aproksymacji czasu wielomianowego do pakowania i przebijania grubych przedmiotów”. Dziennik algorytmów . 46 (2): 178–189. CiteSeerX 10.1.1.21.5344 . doi : 10.1016/s0196-6774(02)00294-8 .
Pobrano z „ https://en.wikipedia.org/w/index.php?title=Rectangle_packing&oldid=1140050720 ”