Chciałbym napisać program który będzie pomagał w wycinaniu elementów z płyty dla stolaży. W programie podaje się rozmiar płyty, np 1800x2000. A następnie podaje się rozmiary elementów które planujemy wyciąć. Chciałbym teraz rozplanować cięcie optymalnie by jak najmniej płyty zużyć. Do problemu użyłem algorytmu który używa drzewa. Dla każdego nowego wsadzonego elementu do kontera są tworzone dwoje dzieci, możnaby powiedzieć dwa nowe obszary. Pierwszy obszar znajduje się pod spodem elementu, drugi obszar znajduje się na prawo od wsadzonego elementu. Następnie gdy chcemy wsadzić nowy element całe drzewo jest przeszukiwane by znaleźć obszar który będzie pasował dla danego elementu, następnie wracamy do punktu wyjścia i dla tego elementu tworzymy dwa nowe obszary. Tutaj jest implementacja tego algorytmu https://github.com/jakesgordon/bin-packing/blob/master/js/packer.js . Problem jest wtedy gdy mamy takie elementy jak na obrazku:
Tu jest pytanie które przypomina mój problem http://stackoverflow.com/questions/5119734/algorithm-to-organise-rectangles-in-the-fixed-rectangular-container . Autor odpowiedzi zasugerował by użyć coś takiego jak przeszukiwanie tabu jeśli chcemy znaleźć optymalne rozwiązanie. Czy to jest konieczne ? Czy istnieją jakieś inne techniki ?
0
0
Jeśli potrzebujesz naprawdę optymalnego rozwiązania, to problem jest NP-trudny, więc jakieś heurystyki (np. tabu) mogą Ci w praktyce przyspieszyć Twoje rozwiązanie, ale wydaje się, że na razie ludzkość nie zna wielomianowego rozwiązania tego problemu. Pytanie tylko, czy naprawdę potrzebujesz optymalnego, czy "dość dobre" Ci wystarczy? Poszukaj trochę więcej o 2D bin packing (np. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.3502&rep=rep1&type=pdf lub https://arxiv.org/pdf/1508.01376.pdf).