Izpitno vprašanje RAČ2PRA 13700

Iz MaFiRaWiki

Vprašanje

Opiši metodo deli in vladaj.


Odgovor

Kot že samo ime pove, deluje tako, da problem, ki se ga lotimo, razdelimo (faza deli) in ga nato rešimo (faza vladaj). Pri tem lahko problem razdelimo na manjše podprobleme, ki naj bodo iste narave kot prvotni problem. Če je tudi podproblem preveč zahteven, ga delimo naprej. Tak postopek ponavljamo, dokler nismo sposobni rešiti podproblemov.

Deli je faza, ki problem razdeli na dva ali več podproblemov, ki jih nato rešimo vsakega posebej.

Vladaj je faza, v kateri moramo velikokrat rešitve podproblemov sestaviti v neko končno rešitev. Če je problem dovolj majhen (preprost), lahko pridemo do rešitve brez operacij deli in vladaj (združi).

Slikovni prikaz: deli in vladaj.


Algoritem:

deli in vladaj(a,dno,vrh, resitev)

/* rešimo problem določen s podatki adno, …, avrh */
   if problem majhen(dno,vrh) resi(a,dno,vrh,resitev)
   else
       s = deli(dno,vrh);
       deli in vladaj(a, dno, s, resitev1);
       deli in vladaj(a, s+1, vrh, resitev2);
       zdruzi(a,dno,s,vrh,resitev1,resitev2,resitev);

V metodi deli in vladaj problem najprej preverimo, če je dovolj enostaven (s klicem metode problem majhen) in če je, ga rešimo (s klicem metode resi). Če je problem preveč zahteven, ga razdelimo na dva podproblema in vsakega rešimo spet z metodo deli in vladaj. S tem dobimo dve delni rešitvi, ki ju združimo (metoda zdruzi) v skupno rešitev.


Sem spadata tudi tudi dva splošno uporabljena postopka za urejanje: urejanje z zlivanjem in hitro urejanje.

Osebna orodja