Kauno Technologijos Universitetas
Informatikos fakultetas
Giljotininio pjaustymo euristika
Optimizavimo sistemu namu darbas
Darba atliko KTU IFM 6/2 grupes studente
Laima Kalinauskiene
Uzduotis
Turime baigtini skaiciu n ruosiniu, kuriu ilgiai ir plociai zinomi,
bei turime pjaustoma plokste, kurios matmenys taip pat zinomi.
Tikslas- isdelioti ruosinius taip, kad gautas atlieku plotas butu minimalus.
Darbe naudojama giljotininio pjaustymo euristika
Nuskaitomi duomenys yra surusiuojami. Vertingiausias ruosinys yra tas, kuris turi ilgiausia krastine.
Darbo pradzioje issirenkamas vertingiausias ruosinys. Kadangi tai naujas pjuvis, todel pirmasis ruosinys talpinamas pjaustomos plokstes kairiajame virsutiniame kampe.
Patalpintas ruosinys pazymimas kaip panaudotas. Ieskomas kitas vertingiausias ruosinys, kuris yra nepanaudotas.
Rastas ruosinys talpinamas prie anksciau rasto taip, kad jie sudarytu ruosini, kuris uzimtu maziausia galima plota.
Prie gauto metaruosinio talpinami kiti vertingi ruosiniai pagal anksciau aprasyta taisykle. Tai vykdoma tol, kol susidaro giljotininis pjuvis.
Giljotininis pjuvis susidaro tuomet, kai horizontaliame ar vertikaliame isdestyme nebeimanoma isdestyti ne vieno nepanaudoto ruosinio taip, kad sumazetu atlieku plotas.
Kai susidaro tokia situacija, tai laikoma, kad kitas pjuvis bus naujas ir viskas kartojama isnaujo.
Vartotojo vadovas
Virsuje pateikiami nagrinejamo ploto ismatavimai: plotis (width) ir aukstis (height), pradines ju reiksmes 100 ir 100. Sias reiksmes galima keisti.
Jei vartotojas siuos laukus palieka tuscius, tuomet pagal nutylejimu ju reiksmes yra 100 (plotis) ir 100 (aukstis). Zemiau po uzrasu "Size of patterns" reikia ivesti ruosiniu matmenis.
Ruosiniu matmenys nurodomi tokiu budu:
Programa
Paleidimas cia.
Kuo mano darbas geresnis uz originala
1) Siame darbe naudojama nauja geresne euristika.
Darbas atliktas remiantis Dariaus Kalinausko darbu. Ji galima rasti cia.
50,40
30,20
20,40
60,40
30,10
20,30
Jei ruosinio matmenys tokie, kad jis negali tilpti i pjaustoma plokste, tai sis ruosinys bus atmestas.
Ivedus duomenis reikia spausti Run. Jei duomenys apie ruosinius bus neivesti, tuomet bus isvestas pranesimas: "No data entered. Please enter some data in field 'Size of patterns' ". Ivedus duomenis vel
spaudziama Run. Po kiek laiko programa sugeneruoja ir
pateikia rezultata. Norint ivesti naujus duomenis reikia spausti Clear. Senos reiksmes istrinamos ir galima ivedineti naujus duomenis.
Programos iseities tekstas yra cia.
2) Skaiciavimai atliekami per trumpesni laika.
3) Si programa labiau isbaigta nei originali.
4) Vartotojas gali pats nurodyti pjaustomos plokstes ismatavimus.
5) Vartotojas gali pats nurodyti ruosiniu ismatavimus.