Ĺadny brzuch
Witam, potrzebuję kilku rad, zwłaszcza od strony matematycznej poniższego problemu.
Oto on: mamy podane wymiary płyty, oraz wymiary kilku (liczba nie określona) fragmentów które należy z tej płyty wyciąć. Zadanie polega na tym, aby te fragmenty tak poukładać, żeby zaoszczędzić jak najwięcej miejsca. Najelepiej aby te niewykorzystane miejsce było w dużych kawałka które jeszcze będzie można w przyszłości wykorzystać!
Muszę taki algorytm napisać, tylko jeszcze niestety brakuje mi zaplecza matematycznego, a nie chcę, aby byle jak optymalizował!
POMOCY!!
zlowieku, ty wiesz ile nad takim algorytmem sie pracuje. A jak juz sie go opracuje to kosztuje on majatek :D
Dla ulatwienia podpowiem ci ze z duza pomoca moze przyjsc tutaj Metoda Elementow Skonczonych(MES). A dokladniej rozklad duzych elementow na mniejsze(najlepiej trojkatne elementy). POstepujesz to z duza plyta, jak i z elementami ukladanymi na niej.
Powiem tylko, ze nad podobnym problemem sidzialem dosyc dlugo(tak okolo roku czasu) i udalo sie odzyskac 5% materialu zdatnego do uzytku w procesie produkcyjnym i uwierz ze to byl duzy sukces w moim przypadku. Ale program byl bardzo zasobortzerny. Ale spowodowane bylo to bardzo duza zlozonoscia elementow:D
w takim wypadku byłbyś skłonny uchylić tajemnicy tego algorytmu?
Skoro już cos robił, to jak ja bym jeszcze nad tym troszke pomyślał to moze robił by więcej :)
Witam, potrzebuję kilku rad, zwłaszcza od strony matematycznej poniższego problemu.
Oto on: mamy podane wymiary płyty, oraz wymiary kilku (liczba nie określona) fragmentów które należy z tej płyty wyciąć. Zadanie polega na tym, aby te fragmenty tak poukładać, żeby zaoszczędzić jak najwięcej miejsca. Najelepiej aby te niewykorzystane miejsce było w dużych kawałka które jeszcze będzie można w przyszłości wykorzystać!
Muszę taki algorytm napisać, tylko jeszcze niestety brakuje mi zaplecza matematycznego, a nie chcę, aby byle jak optymalizował!
POMOCY!!
no ja tez mam wrazenie, ze to problem NP-zupelny, a w takim wypadku jedyne co mozesz zrobic, to zaproksymowac rozwiazanie, czyli postaraj sie robic takie wykroje, aby pozostala czesc byla "dosc dobra".
Nie wiem czy tego można się domyślić z moich powyższych wypowiedzi, ale wszystkie obiekty które będą wycinane są prostokątami. Zadnych innych kształtów.
//Edit
Z tego co do tej pory wydedukowałem to wydaje mi się że dobrym posunięciem byłoby grupowanie obiektów wg. takich samych boków, a później ułożenie z nich jednego większego prostokąta. No ale takie rozwiązanie niestety nie sprawdza się na każdych danych wejściowych, zawsze znajdzie sie jakiś układ który należałoby inaczej rozplanować.
Sprobuję jeszcze zagłębić się w pojęcie minimalizacji funkcji wielu zmiennych.
Moze dostanę jeszcze jakiegoś olśnienia.
Ale wszelkie spostrzeżenia, oraz pomysły są mile widziane.
Użytkownik Programist edytował ten post 14 sierpień 2005, 13:25
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
Oto on: mamy podane wymiary płyty, oraz wymiary kilku (liczba nie określona) fragmentów które należy z tej płyty wyciąć. Zadanie polega na tym, aby te fragmenty tak poukładać, żeby zaoszczędzić jak najwięcej miejsca. Najelepiej aby te niewykorzystane miejsce było w dużych kawałka które jeszcze będzie można w przyszłości wykorzystać!
Muszę taki algorytm napisać, tylko jeszcze niestety brakuje mi zaplecza matematycznego, a nie chcę, aby byle jak optymalizował!
POMOCY!!
zlowieku, ty wiesz ile nad takim algorytmem sie pracuje. A jak juz sie go opracuje to kosztuje on majatek :D
Dla ulatwienia podpowiem ci ze z duza pomoca moze przyjsc tutaj Metoda Elementow Skonczonych(MES). A dokladniej rozklad duzych elementow na mniejsze(najlepiej trojkatne elementy). POstepujesz to z duza plyta, jak i z elementami ukladanymi na niej.
Powiem tylko, ze nad podobnym problemem sidzialem dosyc dlugo(tak okolo roku czasu) i udalo sie odzyskac 5% materialu zdatnego do uzytku w procesie produkcyjnym i uwierz ze to byl duzy sukces w moim przypadku. Ale program byl bardzo zasobortzerny. Ale spowodowane bylo to bardzo duza zlozonoscia elementow:D
w takim wypadku byłbyś skłonny uchylić tajemnicy tego algorytmu?
Skoro już cos robił, to jak ja bym jeszcze nad tym troszke pomyślał to moze robił by więcej :)
Witam, potrzebuję kilku rad, zwłaszcza od strony matematycznej poniższego problemu.
Oto on: mamy podane wymiary płyty, oraz wymiary kilku (liczba nie określona) fragmentów które należy z tej płyty wyciąć. Zadanie polega na tym, aby te fragmenty tak poukładać, żeby zaoszczędzić jak najwięcej miejsca. Najelepiej aby te niewykorzystane miejsce było w dużych kawałka które jeszcze będzie można w przyszłości wykorzystać!
Muszę taki algorytm napisać, tylko jeszcze niestety brakuje mi zaplecza matematycznego, a nie chcę, aby byle jak optymalizował!
POMOCY!!
no ja tez mam wrazenie, ze to problem NP-zupelny, a w takim wypadku jedyne co mozesz zrobic, to zaproksymowac rozwiazanie, czyli postaraj sie robic takie wykroje, aby pozostala czesc byla "dosc dobra".
Nie wiem czy tego można się domyślić z moich powyższych wypowiedzi, ale wszystkie obiekty które będą wycinane są prostokątami. Zadnych innych kształtów.
//Edit
Z tego co do tej pory wydedukowałem to wydaje mi się że dobrym posunięciem byłoby grupowanie obiektów wg. takich samych boków, a później ułożenie z nich jednego większego prostokąta. No ale takie rozwiązanie niestety nie sprawdza się na każdych danych wejściowych, zawsze znajdzie sie jakiś układ który należałoby inaczej rozplanować.
Sprobuję jeszcze zagłębić się w pojęcie minimalizacji funkcji wielu zmiennych.
Moze dostanę jeszcze jakiegoś olśnienia.
Ale wszelkie spostrzeżenia, oraz pomysły są mile widziane.
Użytkownik Programist edytował ten post 14 sierpień 2005, 13:25