Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Algoritam za optimalno secenje materijala (sipke, etc.)

[es] :: Art of Programming :: Algoritam za optimalno secenje materijala (sipke, etc.)

[ Pregleda: 6296 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Zeromicin

Član broj: 31930
Poruke: 152
*.panet.co.yu.



Profil

icon Algoritam za optimalno secenje materijala (sipke, etc.)15.09.2006. u 17:03 - pre 213 meseci
Potreban mi je algoritam za optimalno secenje materijala, tj:
- imam metalne sipke odredjene duzine,
- imam skup elemenata razlicite duzine (manje od duzine sipke),
Potrebno je najoptimalnije iskombinovati elemente, tako da se dobije sto veca iskoriscenost matrerijala.



P.S. Da li bi mogao da se iskoristi knapsack algoritam (naravno uz odredjene modifikacije) za resenje ovog problema?

Inace kombinacija svakog elementa sa svakim (neki klasican metod) i racunanje iskoriscenosti dosta dugo traje tj n! tako da mi je potreban neki efikasniji algoritam...


cu.
 
Odgovor na temu

broker

Član broj: 2415
Poruke: 8514
212.62.59.*



+11 Profil

icon Re: Algoritam za optimalno secenje materijala (sipke, etc.)15.09.2006. u 17:06 - pre 213 meseci
Ne zaboravi debljinu reza.
 
Odgovor na temu

dimitar 16
Dimitar Misev
Makedonija

Član broj: 31509
Poruke: 134
62.162.20.*

Jabber: dimitarmisev@gmail.com


Profil

icon Re: Algoritam za optimalno secenje materijala (sipke, etc.)15.09.2006. u 19:31 - pre 213 meseci
Bas isti zadatak sam resavao na USACO (http://train.usaco.org).
U atachment je tekst zadatka i resenje.
Prikačeni fajlovi
 
Odgovor na temu

Zeromicin

Član broj: 31930
Poruke: 152
*.panet.co.yu.



Profil

icon Re: Algoritam za optimalno secenje materijala (sipke, etc.)15.09.2006. u 22:45 - pre 213 meseci
Dobro, debljina reza je po meni trivijalnost kod ovog problema...

Vazan mi je algoritam, mozda ne i algoritam nego sam pristup problemu ;)
 
Odgovor na temu

Zeromicin

Član broj: 31930
Poruke: 152
*.panet.co.yu.



Profil

icon Re: Algoritam za optimalno secenje materijala (sipke, etc.)24.09.2006. u 15:21 - pre 213 meseci
Pa sta je, zar se niko nije bavio ovim problemom?
 
Odgovor na temu

genuine
Dragisa Jankovic
Beograd

Član broj: 101510
Poruke: 33
194.106.175.*



Profil

icon Re: Algoritam za optimalno secenje materijala (sipke, etc.)25.09.2006. u 01:38 - pre 213 meseci
sta je optimalno iskoriscenje?

Necu vise da radim ,bre !
 
Odgovor na temu

Zeromicin

Član broj: 31930
Poruke: 152
*.panet.co.yu.



Profil

icon Re: Algoritam za optimalno secenje materijala (sipke, etc.)25.09.2006. u 07:45 - pre 213 meseci
Pod optimalnim iskoriscenjem se podrazumeva da uradis takvu(e) kombinaciju(e) elemenata, da imas sto manji otpad.
Npr.
duzina elemenata: 3,4,5,8
duzina sipke: 8

Kombinacija koja nije optimalna je npr:
- na prvu sipku od 8m stavi se: 3+4 (iskoriscenost 7m + 1m otpad) 87%
- na drugu sipku od 8m stavi se: 5 (iskoriscenost 5m + 3m otpad) 62%
- na trecu sipku od 8m stavi se: 8 (iskoriscenost 8m + 0m otpad) 100%
Potroseno je ukupno 3 sipke od 8 metara, iskoriscenost je 20 a otpad su dve sipke od 1m i 3m.
Broj secenja je 2+1=3

Kombinacija koje je optimalnija od prethodne:
- na prvu se stavi: 3+5 (iskoriscenost 8m + 0m otpad) 100%
- na drugu se stavi: 8 (iskoriscenost 8m + 0m otpad) 100%
- na trecu se stavi: 4 (iskoriscenost 4m + 4m otpad) 50%
Potroseno je 3 sipke od 8m, iskoriscenost je 20m, otpad je sipka od 4m.
Broj secenja je 1+0+1=2

Vidi se da je druga kombinacija optimalnija, jer je otpad jedna veca sipka potreban je manji broj rezova...

Ovo je samo neki primer sa malim brojem elemenata, tako da se ovo moze uraditi i rucno. Ukupan broj svih kombinacija je 4!.
Ali kod veceg broja elemenata broj kombinacija naraste id do 30! (za 30 elemenata), tako da brute force bas i nije najzgodniji algoritam za ovaj posao...

Meni se cini da je ovaj problem slican kao knapsack algoritam, sa kojim sam i probao nesto (a verovatno cu i nastaviti), ali ako neko ima neko prostije resenje...

P.S.
Na netu sam pronasao, kod vise izvora, da kod problema gde se broj "resenja" uvecava eksponencijalno, pozeljno je koristiti genetske algoritme (malo teze za implementaciju).
 
Odgovor na temu

genuine
Dragisa Jankovic
Beograd

Član broj: 101510
Poruke: 33
194.106.175.*



Profil

icon Re: Algoritam za optimalno secenje materijala (sipke, etc.)26.09.2006. u 01:52 - pre 213 meseci
Jos par pitanja... da li mozes da klasifikujes predmete u kategorije .. recimo sve sto se ralikuje za recimo par % stavis u kategoriju sipke duzine 4 +- 2% komada 10 i sl.. pa da umesto sa konkretnim primercima da radis sa kategorijama... nije najoptimalnije ali mislim da ne bi trebalo da % ili %% uticu na kvalitet algoritma... isto tako ako bi recimo sklapao sipke na osnovu kategoria mogao bi da primenis foru iz nekog algoritma za nalazenje minimalnog rasplinuceg stabla... fora je valjda da ako odaberes kombinaciju koja daje najmanju gresku od svih ostalih onda ona ulazi u krajnje resenje.. problem je kako je pronaci.. mozda ukoliko bi resenje trazio po intervalima .. recimo nadji sva resenja koja imaju gresku manju od 1%.. ako je samo jedno onda ga prihvati ako ih ima vise onda ih trazi polovljenjem intervala...

ja nisam neki programer sto se tice ovakvih zezancija.. nadam se da nisam previse lupao... ako jesam ne zamerite mi .. pozdrav...
Necu vise da radim ,bre !
 
Odgovor na temu

trodon
Nebojsa Brindic
CTO
Bincode Entertainment
Beograd

Član broj: 14115
Poruke: 219
*.dynamic.sbb.co.yu.

Sajt: bincode-entertainment.com


Profil

icon Re: Algoritam za optimalno secenje materijala (sipke, etc.)12.05.2007. u 15:43 - pre 205 meseci
Moze se reshiti i linearnim programiranjem (operaciona istrazivanja).
 
Odgovor na temu

Promaja
Beograd

Član broj: 145514
Poruke: 2
80.93.243.*



Profil

icon Re: Algoritam za optimalno secenje materijala (sipke, etc.)17.05.2007. u 10:26 - pre 205 meseci
Kao sto je neko ovde naveo i meni ovo mnogo vise lici na problem ranca.

A ukoliko te zainteresuje problem pakovanja i secenja preporucio bih ti da pogledas nesto o linearnom programiranju, genetskim i algoritmima simuliranog kaljenja
 
Odgovor na temu

[es] :: Art of Programming :: Algoritam za optimalno secenje materijala (sipke, etc.)

[ Pregleda: 6296 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.