Problem No1

[Hallon]

Svojedobno sam imao zanimljiv problem. O optimizatorima temeljenim na genetskim algoritmima sam, čini mi se, govorio na znanosti. Sad o problemu:

Imate pravokutnik, drvenu ploču. Treba napraviti optimizator za piljenje stranica ormara.

Kako to treba izvesti? Korisnik upisuje skup pravokutnika (čisto dimenzije stranica ormara) koji se moraju ispiliti iz drvene ploče. Znači optimizator mora posložiti svaki od pravokutnika na drvenu ploču pazeći na slijedeće:
1) Pravokutnici se ne smiju preklapati
2) Paziti na širinu pile (pila ponekad može odnjeti i po par milimetara drva)
3) Pravokutnici ne smiju biti složeni kako bilo. Pila mora prolaziti kroz ploču od početka do kraja. Kad se otpili manji komad koji sadrži više pravokutnika, tada opet pila mora prolaziti kroz ploču, čime se ploča konstantno usitnjava. Znači, pila se ne može zaustaviti nasred ploče i vaditi van.
4) Svi pravokutnici (stranice ormara) se moraju posložiti se lijeve gornje strane drvene ploče, tako da ostane što je više moguće prostora s donje strane drvene ploče, pa zatim s desne. Prioritet ima donja strana drvene ploče. Korisnost ostatka je veličina maksimalnog pravokutnika koji se može u taj ostatak upisati. Znači težiti tome da ostatci budu u pravokutnoj formi, kako bi se kasnije mogli opet iskoristiti.

Kad bismo za optimizaciju koristili GA, trebalo bi zapravo samo dobro napraviti funkciju kvalitete iliti korisnosti...

Ima ko kakvu ideju?

[Shadowman]

Samo da kažem da imam ideja i da ovaj post nije prošao neprimjećen, ali sam sad previše zauzet da ih probam razraditi. Možda se javim ponovo.

[Hallon]

Mene je užasno yebal (i još me muči) ovaj prolaz pile...

Ima rješenja al su užasno spora. Ja sam išao simulirat pilu, al je bilo katastrofalno (kao ideja sux). Mora biti matematička metoda za to. Nije baš najjednostavnije... :top:

[Flo_Master]

Evo moga slaboga pokusaja.
Nisam razradjivao problem nego je ovo samo ideja koja ce se (prema dosadasnjem iskustvu) morati doraditi.


Probao bih metodu otvorene i zatvorene liste

Komad koji se odreze ide na zatvorenu listu.
Na otvorenoj listi su oblici (pravougaonici) i ostaci drveta.

Prvo se reze najveci komad.

Ostatak drveta (zajedno sa dijelovima koji nisu izrezani ide na otvorenu listu).
Onda se ta lista chekira i uzima se opet najveci komad za rezanje i gleda se koja ploca najvise odgovara. Kriterij neka bude maximalna iskoristivost drveta (mada moze biti i najbrze piljenje).

U principu, svaki komad se moze okrenuti na dva nacina (vodoravno i okomito) i treba istraziti sve kombinacije, tj. ispitati sve mogucnosti koje postoje i onda ih sortirati po kriteriju koji nam odgovara.

Komada sigurno nema bas puno pa je i broj kombinacija relativno mali.
Mozda jeste sporo, ali kad se jednom izracuna, nema potrebe za ponovnim proracunima.

Ajde, ukazivajte na nedostatke.

[Flo_Master]

Evo moga slaboga pokusaja.
Nisam razradjivao problem nego je ovo samo ideja koja ce se (prema dosadasnjem iskustvu) morati doraditi.


Probao bih metodu otvorene i zatvorene liste

Komad koji se odreze ide na zatvorenu listu.
Na otvorenoj listi su oblici (pravougaonici) i ostaci drveta.

Prvo se reze najveci komad.

Ostatak drveta (zajedno sa dijelovima koji nisu izrezani ide na otvorenu listu).
Onda se ta lista chekira i uzima se opet najveci komad za rezanje i gleda se koja ploca najvise odgovara. Kriterij neka bude maximalna iskoristivost drveta (mada moze biti i najbrze piljenje).

U principu, svaki komad se moze okrenuti na dva nacina (vodoravno i okomito) i treba istraziti sve kombinacije, tj. ispitati sve mogucnosti koje postoje i onda ih sortirati po kriteriju koji nam odgovara.

Komada sigurno nema bas puno pa je i broj kombinacija relativno mali.
Mozda jeste sporo, ali kad se jednom izracuna, nema potrebe za ponovnim proracunima.

Ajde, ukazivajte na nedostatke.

[Hallon]

M Flo, imaš jedan problem.

Dakle upičiš pilu u drvo i ravno rezeš dokraja ploče. S lijeve strane pile padne komad drveta (manji od ostatka s desne strane). Zatim uzmeš manji komad (onaj s lijeve strane) i iz njega ispiliš komade koji ti trebaju.

Znači prilikom prvog piljenja ti otpiliš 10-tak ploča, koje onda u 2., 3., 4., ... 11. piljenju odvajaš...

Neznam kako ćeš to s listama izvest. Ti onda trebaš odmah odabrati X ploča i staviti na jednu od svojih lista u istom prolazu. Postavlja se pitanje: Kojih deset ploča od recimo stotinjak ćeš u prvom prolazu staviti na jednu od lista??

Ovo mora ići nekom metodom optimizacije, no ovo piljenje strašno komplicira stvar.

[Flo_Master]

Hallon kaže:
Postavlja se pitanje: Kojih deset ploča od recimo stotinjak ćeš u prvom prolazu staviti na jednu od lista??


Samo jedna ploca se reze u jednom prolazu, a ne vise njih. Na kraju ce ispasti da ih se iz tog dijela na lijevoj strani izrezalo "toliko i toliko", ali o tome se u trenutku piljenja ne vodi racuna. Jedino sto je vazno koji oblik i koji komad drveta izabrati sa otvorene liste.
Svi ostaci piljenja se ponovo mjere (zbog sirine pile) i idu na otvorenu listu (izuzev onih koji su manji od najmanjeg oblika).

Sa otvorene liste biras uvijek najveci oblik i onda za taj oblik trazis koji komad drveta je najbolji. Naravno, ne moras uvijek odabrati najbolji, ali na kraju ces imati listu kombinacija koje su iz danog drveta ispilile sve potrebne elemente. Iz te liste ces na kraju odabrati rjesenje koje ti najvise odgovara.

Kada zatvorena lista sadrzi sve oblike, proces je gotov.

Ideja je da se koriste permutacije bez ponavljanja (mada treba imati u vidu da se jedan oblik moze postaviti i horizontalno i vertikalno).

[Hallon]

Flo_Master kaže:
Samo jedna ploca se reze u jednom prolazu, a ne vise njih. Na kraju ce ispasti da ih se iz tog dijela na lijevoj strani izrezalo "toliko i toliko", ali o tome se u trenutku piljenja ne vodi racuna. Jedino sto je vazno koji oblik i koji komad drveta izabrati sa otvorene liste.

Ali ti pilu ne možeš vijati. Ti ne možeš piliti pravi kut. Pila ide samo pravocrtno...

Te su daske debele po par centimetara. One se ne pile pilicom za šperploču, pa da bi mogao piliti krivulje. To je lisnata pila koja i pri najmanjem naprezanju puca...

Mislim da možda shvaćam o čemu pričaš, ali mi je mutno. Oćeš reći da uzmeš najveću ploču i za njega otpiliš komad drveta. Nakon toga, ono što ostane ide na manje ploče... ili štogod drugo?

[Flo_Master]

Hallon kaže:
Oćeš reći da uzmeš najveću ploču i za njega otpiliš komad drveta. Nakon toga, ono što ostane ide na manje ploče... ili štogod drugo?

Upravo to.

Prvo izrezes najvecu plocu. Prilikom rezanja imas dva ostatka: jedan veliki (koji je ostatak velike drvene plohe sa koje trebas izrezati sve ploce) i jedan manji (koji je ustvari otpadak od rezanja najvece ploce).
Oba ostatka stavis na otvorenu listu (a odrezanu plocu na zatvorenu listu) i onda rezes slijedecu po velicini plocu. Najmanje plocu rezes zadnju.
Sve otpatke (izuzev onih koji nisu dovoljni niti za najmanju plocu) nakon svakoga rezanja stavljas na otvorenu listu.

Mislim da tako radi svaki stolar. Ono sto ne moze vise iskoristiti nizasto, to baci, ali ono sto bi mu poslije moglo koristiti, to sacuva.

Sta velis?

[Hallon]

math bi rekla: zdravorazumsko razmišljanje... ali mi se sviđa. :top: