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.