algorytm - optymalne dopasowanie figur do powierzchni Opcje

[peter222]

Witam

Przymierzam się do takiego zadania i przyznam, że nie wiem od której strony to ugryźć. Może coś podpowiecie? Może ktoś zna do tego jakieś gotowe biblioteki?
Chodzi o to, że mamy daną powierzchnię (pojemnik) np. prostokąt 10m x 8m, do tego dostajemy kilkanaście figur o różnych kształtach (wyłączając koła, elipsy itp. - wszystko złożone z mniejszych kwadratów - podobnie jak w grze Tetris).
Zadanie jest takie, żeby algorytm pokazał jak optymalnie upchać te figury na danej powierzchni (czyli używając jak najmniejszej ilości takich pojemników).
Figura nigdy nie przekroczy rozmiaru podanej powierzchni.

Może mi ktoś podpowiedzieć od czego zacząć? Znacie jakieś gotowce na to?

Ten post edytował peter222 19.12.2017, 18:02:54

[r4xz]

Na pewno jest to jakiś typ problemu plecakowego. Tutaj np. bardzo ważne jest czy te figury składają się z kwadratów o takich samych rozmiarach?

[peter222]

Ooo, to jest dobry trop... dzięki!
Figury to generalnie mniejsze prostokąty od zadanej powierzchni ale zawierające wcięcia, stąd mogą przyjąć kształt np. litery L. Optymalne połączenie figur musi brać pod uwagę te wcięcia aby w miarę możliwości zrobić dopasowanie (aby nie marnować pustych przestrzeni).

[sabat24]

Na studiach się to u nas zwało algorytmami wykrojów. Implementację robiłem przy pomocy algorytmów genetycznych. Wpisz sobie w google: "Zmodyfikowany algorytm genetyczny dla dwuwymiarowego nieregularnego problemu optymalnego rozkroju" powinien Ci wyskoczyć PDF z Politechniki Krakowskiej z zarysem problemu.

Po angielsku szukaj: irregular shape cutting problem albo cutting stock problem

Ten post edytował sabat24 19.12.2017, 19:18:46

[peter222]

sabat24, to jest jeszcze bliższe mojego problemu - dzięki wielkie - będę studiował problem.