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?
- Rejestracja:około 13 lat
- Ostatnio:ponad 9 lat
- Postów:15

- Rejestracja:prawie 14 lat
- Ostatnio:2 dni
- Postów:2512
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 ;]

- Rejestracja:około 17 lat
- Ostatnio:4 minuty
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.
- Rejestracja:około 13 lat
- Ostatnio:ponad 9 lat
- Postów:15
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...:-))

- Rejestracja:około 17 lat
- Ostatnio:4 minuty
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.

- Rejestracja:prawie 19 lat
- Ostatnio:około miesiąc
- Postów:29
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

- Rejestracja:ponad 22 lata
- Ostatnio:około godziny
- Lokalizacja:Poznań
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ł.
- screenshot-20180123111556.png (157 KB) - ściągnięć: 131