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 na razie jeszcze niestety brakuje mi zaplecza matematycznego.
POMOCY!!
mi to pachnie minimalizacją funkcji wielu zmiennych. konkretnie - robisz funkcję, która zwraca ilość niewykorzystanego miejsca w zależności od ułożenia wzoru płyty, przy czym parametrami tej funkcji będą pozycje/kąty tych płyt.
do minimalizacji funkcji istnieje wiele implementacji przeróżnych algorytmów, choćby kilka z "numerical recipes in pascal" (np.: FRPRMN, DFPMIN itp). Osobiście polecam metodę sprzężonych gradientów.
w zasadzie są tylko dwa problemy - jak stwierdzić, że jest za dużo płytek, i jak ustawiać je tak, żeby nie zachodziły na siebie. ale jest to jak najbardziej do zrobienia - miłej zabawy.
dzięki teraz przynajmniej wiem od czego zacząć.
klocilbym sie, gdzie tutaj jest jakas minimalizacja funkcji wielu zmiennych? bo z tego co widze, to to jest problem NP-zupelny
szablozebna_zdzira napisał(a)
klocilbym sie, gdzie tutaj jest jakas minimalizacja funkcji wielu zmiennych? bo z tego co widze, to to jest problem NP-zupelny
znalezienie minimum zmarnowanego materiału w funkcji położenia wycinanych elementów. poza tym nie twierdzę, że jest to optymalna/jedyna metoda.
zlecenia.przez.net? ;]