Algorytm optymalizacji rozkroju

0

Poszukuję materiałów, które w miare prosty sposób opiszą algorytm optymalizacji rozkroju (mogą być również w j. Angielskim).

Najfajniej, gdyby to były przykłady w dowolnym języku programowania.

Bardzo prosze o powstrzymanie się z komentarzami nic nie wnoszącymi do tematu.

0

Oj metod optymalizacji jest mnoooogo. Szukaj pod hasłem optymalizacja, musisz ją tylko dostosować do swojego problemu.

//edit
już była o tym mowa http://4programmers.net/Forum/viewtopic.php?id=76688

Chyba, że ci chodzi o metodę dokładną.

0

Raczej chodzi o konkretny przykład.

Tamten wątek czytałem, ale niewiele mi pomógł.

To znaczy. Napisałem coś, co nawet daje jakieś tam efekty. Kod jest napisany w SQLu i działa na takiej zasadzie:

jest lista wolnych obszarow (startujemy od jednego, o wymiarach stolu)
jest lista elementów

bierzemy elementy od najwiekszego (w m2) do najmniejszego. Szukamy dla niego obszaru wolnego jezeli obszar zostanie znaleziony - kladziemy element na tym obszarze, a obszar dzielimy na dwa mniejsze (linia podzialu jest definiowana w jednym z dwoch kierunków). Dostajemy w wyniku tego podziału dwanowe obszary, ktore zostaja dodane do listy obszarow wolnych (obszar, na ktorym polozylismy element jest usuwany z listy). w ten sposob zawsze dostajemy obszary wolne w krztalcie prostokata.

Oczywiscie obszary wolne wyszukiwane sa pod katem najblizszego pod wzgledem powierzchni (m2) i wymiarów.

Jeżeli obszar wolny nie zostanie znaleziony - system dodaje kolejny wolny obszar o wymiarach stolu.

Wszystko dziala fajnie, ale jest jeden szkopuł.

Okazuje się, że program w trakcie działania "tnie" obszary wolne na pasy. Zdarza się, że jest zmuszony do dodania nowego stolu, pomimo, ze gdyby wziął dwa obszary sasiadujace, to element, ktory chcemy tam umiescic spokojnie wszedł by w takie połączone oszary.

Owszem - można pokusić się o napisanie procki, ktora będzie łączyła obszary, ale czuje, ze nie tędy droga.

Np. nie obsługuję obracania elementów (w niektórych przypadkach wymogi produkcji elementow nie pozwalaja na obroty - ale to sie da obsłużyć odpowiednim znacznikiem elementu).

Generalnie nie mam żadnej pewności, czy ta metoda jest optymalna.

Niestety - czas goni. Klient jest napalony na włączenie tej funkcjonalności to reszty systemu (bo w wyniku nieporadności pracowników ma duże straty na materiale), a ja kręcę się w kółko.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0