Rozwazanie teoretyczne.
Problem: Mamy w magazynie X paczek (prostopadłościanów) o dowolnych wymiarach. Chcemy je zaladowac na X samochodow (prostopadloscian) o znanych wymiarach. Czy mozna wyliczyc minimalna ilosc samochodow , na ktore daloby sie te paczki zapakowac? Problem optymalizacji. Czy w ogole istnieje jakis algorytm rozwiazujacy taki problem?
0
0
prloblem plecakowy bodajże.
0
A konkretniej dyskretny problem plecakowy
http://pl.wikipedia.org/wiki/Problem_plecakowy
Aaaa no tak problem plecakowy to nie to, bo skupia się na zabraniu przedmiotów o jak największej wartości, a nie do jak najmniejszej liczbie plecaków ;]
0
Ja bym powiedział, że jest to "problem optymalnego rozkroju" w wersji 3d. Deską do pokrojenia jest paka samochodu. Wycinkami są paczki, które trzeba spakować.
W końcu nie zastanawiamy się jakie paczki pakujemy do jednego samochodu, ale jak użyć najmniej samochodów by przetransportować wszystko.
0
Troche poczytalem na te tematy i wydaje mi sie, ze nie da sie tego problemu rozwiazac. Sa programy, ktore z duza dokladnoscia potrafia optymalizowac rozklad prostokatow na prostokacie - np. wycinanie z prostokatnej blachy n-elementow prostokatnych. Nie da sie natomiast napisac programu, ktory optymalizowalby takie wycinanie figur o dowolnychg ksztaltach (+kola, + trapezy + elipsy). A to dopiero problem 2 - wymiarowy. Z paczkami bylby 3 - wymiarowy wiec w ogole matrix.
Dowiedzialem sie natomiast, ze istnieja programy, ktore dokonuja optymalizacji 2 wymiarowej. ALE! Ale podobno dzialaja w ten sposob, ze czasami daja rozne 2 rozne wyniki przy wprowadzeniu 2 takich samych zalozen poczatkowych. A to by oznaczalo, ze nawet w tych programach nie ma jakiegos 1 algorytmu matematycznego. Przypuszaczam, ze programy te w trakcie swojej pracy 'ucza sie' caly czas problemu.
Stad wnioskuje, ze problem z paczkami jest na moim poziomie i stanie wiedzy absolutnie nierozwiazywalny...:-))
0
e tam przesadzasz.
Owszem znalezienie optymalnego rozwiązania tego problemu jest bardzo trudne, są jednak metody miękkie, które dość dobrze się sprawdzają w rozwiązywaniu takich problemów.
Zabawa z algorytmem genetycznym nie jest wcale, aż tak skomplikowana jak ci się wydaje.
0
Trochę opracowań na temat pakowania w 3D tutaj:
http://www.optimization-online.org/DB_FILE/2007/06/1686.pdf
http://www.optimization-online.org/DB_FILE/2010/09/2736.pdf
http://en.wikipedia.org/wiki/Packing_problem
0
Odkurzam stary wątek.
Czy są jakieś darmowe programy wspomagające optymalne rozkładanie elementów? Idealnie w 3D, ale w 2D też mnie urządzi.
Chciałbym porobić sobie jak najmniejsze opakowania na gry planszowe, by zabierać je w podróż. Mam więc gabaryty elementów, trzeba je tylko dobrze rozmieścić, by się nie poniszczyły (niektóre bywają delikatne). Całość wyciąć w gąbce, coś w ten deseń:
[edit]
Namierzyłem kilka pod hasłem "nesting" - będę testował.
0
Na studiach rozwiazywalem takie zadanie przy pomocy jezyka MiniZinc. Ksztalty reprezentowalo sie jako zbiory prostokatow o roznych wymiarach, zapuszczalo sie solver ktory liczyl kordynaty.