[ overflow @ 11.01.2002. 08:20 ] @
Verovatno mi je lose ime teme, ali u trenutku se nisam setio boljeg.
Da predjem na stvar. Interesuje me kako se resava problem kada imamo neku tablu (m x n dimenzija) i k proizvoljnih manjih tabli (dimenzija m1 x n1, m2 x n2 ... mk x nk), a zadatak je na sto optimalniji nacin/raspored rasporediti male table u okviru velike?

Evo, o ovom problemu sam dosta lupao glavu, ali posto nikad do sada nisam sreo ni slican problem nisam uspeo da ga resim, pa bih molio nekoga, ako nista vise onda bar neka uputstva ...
[ Stefa @ 11.01.2002. 13:56 ] @
Jel to znaci da zelis da manje matrice svojim rasporedom zauzmu sto manje prostora u velikoj ili nesto drugo?

Odgovori pa da razmislim...
[ overflow @ 12.01.2002. 01:58 ] @
Citat:
Stefa:
Jel to znaci da zelis da manje matrice svojim rasporedom zauzmu sto manje prostora u velikoj ili nesto drugo?

Odgovori pa da razmislim...


Moze ...
[ Stefa @ 15.01.2002. 15:23 ] @
Citat:
overflow:
Citat:
Stefa:
Jel to znaci da zelis da manje matrice svojim rasporedom zauzmu sto manje prostora u velikoj ili nesto drugo?

Odgovori pa da razmislim...


Moze ...



Dobar ti problem!

Iskreno receno nisam ni ja resavao tako nesto. Problem je moguce resiti ali je potrebna tacna lista zahteva. Prva nepoznanica za mene je sta smatrati pod neiskoriscenim prostorom?!? Potpuno je jasno da kako god da postavimo male matrice u veliku uvek ostaje isti slobodan prostor. E sad, ako se za slobodan prostor uzima kolicina prostora slobodna (na primer) sa leve strane od vec rasporedjenih matrica onda je to jedan od zahteva. Moze isto tako da se zahteva da slobodan prostor na kraju rasporedjivanja imao odredjeni oblik, sto dodatno odredjuje celu komplikaciju. Jedno je sigurno, mora da se ordedi tacna definicija termina 'slobodni prostor'. Toliko o bla, bla...

Kojim putem dalje?

Kako bih ja poceo rasporedjivanje? Sigurno da bi to bila najveca mala matrica. Uvek bi ta matrica bila postavljena u neki od uglova velike matrice. Nakon toga nastaju komplikacije. Ako kao sledecu malu matricu uzmemo prvu manju od vec prvopostavljene onda imamo problem gde je postaviti. O cemu se radi? Pretpostavimo da si najvecu malu matricu postavio u gornji levi ugao velike matrice. Sledeca po velicini mala matrica moze da se postavi teoretski na dva mesta:

I) Uz desnu ivicu prve male matrice i gornju ivicu velike matrice ili
II) Uz donju ivicu prve male matrice i levu ivicu velike matrice

Drugu malu matricu je samo teoretski moguce postaviti na gore navedena mesta zasto sto treba proveriti dali ima dovoljno mesta u velikoj matrici. Zasto ti sve ovo pisem? Zato sto sada znamo dobar deo zahteva. Evo i liste:

I) Male matrice rasporedjivati sortirane po velicini od najvece do najmanje
II) Paziti na potencijalno mesta za postavljanje
III) Po postavci svih malih matrica zavrsava se jedna rekurzija i proverava kolicina slobodnog prostora

Predlog algoritma:

10 rem i = indeksi sortiranih malih matrica
11 REM k = broj mogucih polozaja jedne male matrice
15
16 REM postavljanje pocetnog stanja
20 postavi najvecu malu matricu u gornji levi ugao male matrice
30 for i = 2 to n
40 nadji moguce polozaje male matrice i zapamti ih
50 postavi malu matricu u prvi nadjeni polozaj
60 next i
70
75 REM kombinacije rasporeda malih matrica
80 for i = 2 to n
90 for k = 2 to n1
100 postavi malu matricu u sledeci polozaj
110 for i2 = i + 1 to n
120 nadi moguce polozaje malih matrica i zapamti ih
130 postavi malu matricu u prvi nadjeni polozaj
140 next i2
145 izracunaj slobodan prostor i zapamti
150 next k
160 next i
170
180 nadji maksimalni slobodan prostor od ranije zapamcenih

Licno nisam istestirao algoritam tako da moze da bude pun rupa, ali i taj algoritam i nisam pisao da radi vec da objasni moju ideju moguceg resenja.

Nadam se da sam ti bar malo pomogao. Ako imas pitanja vezana za ovo moje izlaganje slobodno pisi. Problem je inace veoma kompleksan i nema konacnog resenja. Zasto? Zato sto je osnovne pojmove moguce definisati i kombinovati na milion nacina, da ne pricamo o uslovima u realnom zivotu koji ovaj problem mogu toliko da naprave slozenim da bi jedino resenje mogla da bude vestacka neuronska mreza. Ipak mislim da tako daleko ne bi zeleo da ides.

S' postovanjem, Stefa.
[ overflow @ 16.01.2002. 17:35 ] @
Ispravite me ako gresim, ali (bez uvrede) ocigledno je da vas algoritam nema primenu cak ni u teoretskom sistemu. To kazem iz sledeceg razloga. Vas algoritam pri svakom postavljanju druge po povrsini male matrice pamti slobodan prostor i na kraju svih mogucih kombinacija pokusava da pronadje maksimalan slobodan prostor. U cemu je greska? Pa kako god da postavimo manje matrice u nasu veliku ostace nam isti slobodan prostor, dakle nece se menjati. Sustina je ta da trazimo najoptimalniji raspored manjih matrica (u velikoj) koji doprinosi sto efikasnijem iskoriscenju povrsine velike matrice.
Kako najoptimalnije postaviti male matrice tako da ostatak prostora u velikoj matrici bude sto celovitiji i u nekim daljim operacijama sto upotrebljiviji.

Na ilustraciji ispod, prikazacu vam primer optimizacije prostora.



[ Stefa @ 17.01.2002. 12:49 ] @
Zdravo Gorane,

imam jedan predlog vezan za stil nase dalje komunikacije. Osetio si da sam malo :) stariji od tebe (pogodio si... imam 32 godine), ali to ne znaci da treba da mi se obracas sa Vi. Voleo bih da sve to svedemo na Ti. Nadam se da je predlog OK? Druga stvar je da sta god da napises je se sigurno necu uvrediti zato sto programiram skoro 20 godina i vec sam navikao da je sasvim normalna stvar da kada nesto radim (programiram) cesto i pogresim. Posetio sam tvoj sajt i tako stekao prvi utisak o tebi i prvi utisak je da ides u dobrom pravcu da bi postao IT profesianalac. Ja nemam svoj sajt, ali to ne znaci da ti necu odgovoriti ako imas pitanja vezana licno za mene.

A sada o nasem problemu...

...tacno je da uvek ostaje ista slobodna povrsina velike matrice, ali, ja mislim da se jos uvek nismo dogovorili o pojmu preostali slobodan prostor. Zasto? Zato sto kao sto si sam napisao "tako da ostatak prostora u velikoj matrici bude sto celovitiji i u nekim daljim operacijama sto upotrebljiviji" postavlja problem definicije prostalog slobodnog prostora. To znaci da osobine koje mora da poseduje buduci slobodni prostor mogu da imaju veliki uticaj na sam algoritam. Problem mozemo da okrenemo i naglavacke, kako moraju (u kom obliku ili uz koju ivicu itd...) da se grupisu male matrice da bi oblik buduceg slobodnog prostora bio najoptimalniji tj. najupotrebljiviji.

Sama ideja koji sam izneo svodi se na sledece:

1) Male matrice postavljamo u veliku poredjane po velicini (npr. povrsini)
2) Postavljamo male matrice prolazeci kroz kombinacije svih mogucih rasporeda.
3) Nakon postavke svih malih matrica (jedna iteracija) proveravamo koliko nam odgovara novokreirani slobodni prostor za dalju upotrebu

Moram da ti se izvinim ako nisam bio dorecen u prethodnoj poruci. Sve sto sam napisao bilo je na najopstijem nivou moguceg resenja tvog problema. Moze da se desi i to da se nismo razumeli. Ko zna, bitno da imamo dobru volju.

Sto se algoritma tice... javljam ti se posla gde bas i nemam mnogo vremena za testiranje. Kao sto sam ti napisao i sam mislim da nije bez bagova ali mi nije bio cilj da napisem program koji konkretno resava problem vec da na najkraci moguci nacin opisem ideju, a to je prolaz kroz sve moguce kombinacije sto nam u 100% slucajeva omogucava da odaberemo najbolje resenje.

Toliko za sada,

pozdrav Stefa

p.s. Da mozda ne resavas kroz taj problem pitanje optimalne iskoriscenosti materjala u proizvodnji?
[ leka @ 17.01.2002. 16:32 ] @
Izvinite sto upadam ovako...

mala digresija:
Skini YaBASIC (moja malenkost je codeveloper) - www.yabasic.de i zaboravi na brojeve linija... ;)
[ overflow @ 18.01.2002. 12:22 ] @
Za pocetak, sasvim mi odgovara dogovor o stilu nase komunikacije i zeleo bih da ti se zahvalim na finim recima koje si uputio meni licno. Pitanja vezana licno za tebe cu ti eventualno postaviti preko mejla kako bi se drzali diskusije.
Elem, preorjentisacu se u samom startu na blize definisanje pojma "celovitog i sto upotrebljivijeg prostora". Analizirajuci tako zamisljen prostor dolazim do zakljucka da je osnovno polaziste da takav prostor ne sme da sadrzi (na sebi) prazan prostor. Dakle, ako zamislimo jednu veliku matricu i ispunimo je celu istim elementima - recimo "X". I sve male matrice ispunim istim elementima - recimo "0". Potrebno je da po postavljanju malih matrica, ostatak velike matrice ne sme da ima u sebi "rupe" odnosno "0". Drugi vazan zakljucak je taj da takav prostor (odnosno oblik) treba da ima sto manje "krivina". Pod time podrazumevam da taj prostor treba da tezi obliku kvadrata.
Fokusiracu se sada na 3. stavku tvoje ideje. Interesuje me kakva bi bila ideja provere upotrebljivosti (odnosno, "koliko nam odgovara") tog slobodnog prostora ? Kako to realizovati (po mogucnosti algoritam) ? Da li bazirati taj algoritam na stavovima koje sam gore izveo ili treba jos nesto uzeti u razmatranje ?

Ovaj problem sam postavio iz znatizelje. Skoro sam bio na jednom stovaristu gde sam upravo i video program za optimalnu iskoriscenost materijala (konkretno ploce od iverice) pa me je zaintrigirao. Inace po zavrsetku ove diskusije i na osnovu podataka iz iste imam plan da napravim aplikaciju (koja ce imati neka ogranicenja i naravno nece biti na prodaju) i postavim je na besplatan download.
[ Stefa @ 18.01.2002. 12:50 ] @
Izgleda da moram da nacrtam par stvari da bi objasnio ideju. Potrebna mi je tvoja pomoc u tome. U jednoj od poruka si dodao sliku koja se nalazi na nekom sajtu. Reci mi gde ja mogu da ostavim svoje slicice da bi ih prikacio uz poruku.

Stefa.
[ overflow @ 18.01.2002. 18:09 ] @
Citat:
Stefa:
Izgleda da moram da nacrtam par stvari da bi objasnio ideju. Potrebna mi je tvoja pomoc u tome. U jednoj od poruka si dodao sliku koja se nalazi na nekom sajtu. Reci mi gde ja mogu da ostavim svoje slicice da bi ih prikacio uz poruku.

Stefa.


Pa postavi ih na www.geocities.com
i onda ih ovde prostim UBBC kodom (kodove imas na "Pomoc" stranici ovog foruma) ubaci ...
[ Stefa @ 21.01.2002. 14:29 ] @
Evo me...

nacrtao sam slicicu koja treba da pomogne u objasnjenju "dalje upotrebljivog slobodnog prostora". Kao sto vidis, na slici A buducu malu matricu priblizno kvadratnog oblika nemoguce je smestiti dok se pravougaonik idealno smesta u slobodni prostor. Na slici B imamo potpuno obrnut slucaj. Ono sto je interesantno je da mozemo na neki nacin oba slucaja da proglasimo za dobro rasporedjene male matrice. Postoji naravno i jos jedna realna komplikacija. To je orjentacija male matrice. Dobar primer za to moze da bude mala matrica sa brojem 1. Ta ista matrica moze da se postavi i horizontalno.

[img]http://www.geocities.com/stefa69/proba.bmp[/img]

Toliko za sada,

pozdrav Stefa.
[ overflow @ 21.01.2002. 16:10 ] @
Slika je kreirana na osnovu tvoje ilustracije.

Slika ispod



pokazuje da je svakako upotrebljivija tabla B za dalju obradu ... moze se zakljuciti da algoritam treba da se zasniva na sto manjem skartu. Dakle, postavljanje svih malih matrica u okviru velike kako bi se po zavrsetku tog procesa napravio sto manji skart/odbacaj materijala. Detaljnom analizom, vidimo da je u slucaju "A table" skart, odnosno materijal koji ce se po svemu sudeci (velika je verovatnoca) baciti, dosta veci nego u slucaju B. Pod skartom ovde podrazumevam povrsinu materijala koju je potrebno odbaciti da bi se dobila nova tabla ili poligon sastavljen iz manjeg broja povrsinski velikih tabli. Ukoliko mozda nije jasno sta sam hteo da kazem, recite pa cu to i ilustrovati.


Pozdrav,
Goran
[ Stefa @ 22.01.2002. 10:35 ] @
Zdravo...

sta mislis da za definiciju "buduceg upotrebljivog slobodnog prostora" uzmemo sledece:

"Kvalitet buduceg slobodnog prostora ceniti na osnovu maksimalne povrsine pravougaonika koji je moguce upisati."

To bi nam ujedno resilo i problem algoritma koji ispituje kvalitet novonastalog slobodnog prostora.

Stefa.

p.s. Ako to prihvatimo, mozemo da se vratimo postavkama algoritma.
[ overflow @ 24.01.2002. 09:15 ] @
Citat:
Stefa:
"Kvalitet buduceg slobodnog prostora ceniti na osnovu maksimalne povrsine pravougaonika koji je moguce upisati."


Savrseno ... to je to.
[ Stefa @ 29.01.2002. 10:56 ] @
Zdravo Gorane,

nisam ti se javljao zadnjih dana zato sto na poslu imam dosta obaveza. Trenutno pustamo projekt kod klijenta tako da stalno rade popravke bagova i doradjuju stvari koje smo ispustili. Nadam se da ce do kraja nedelje da se zavrsi ludi period pa cemo moci da nastavimo.

Pozdrav Stefa
[ jc denton @ 19.02.2002. 04:54 ] @
Jel bi mogao da se ovaj problem malo vise konkretizuje ?

Imam finu zamisao kako bi ovo moglo da se resi, cak i za nepravilne geometrijske oblike.

Brute force je u pitanju ali mislim da ne bi bilo problema za danasnje kompjutere posebno ako se optimizuje za neki set instrukcija.