Metoda deli in vladaj

Iz MaFiRaWiki

(Preusmerjeno iz Deli in vladaj)

Metoda deli in vladaj je ena od metod za načrtovanje algoritmov. Pri njej nalogo rešujemo tako, da jo razdelimo na manjše naloge istega problema in iz rešitev manjših nalog sestavimo rešitev prvotne naloge. Postopek nadaljujemo rekurzivno, dokler ne dobimo dovolj majhne naloge, ki jih rešimo neposredno.
Kot že samo ime pove, deluje tako, da problem, ki se ga lotimo, razdelimo (faza deli) in ga nato rešimo (faza vladaj).


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

Slika:deli.jpg
Slika prikazuje deljenje problema na manjše podprobleme.

Ker je bil problem pretežak, da bi ga rešili, smo ga razdelili na podproblema A in B. Zaradi enakega razloga je podproblem A dalje razdeljen na podproblema AA in AB, enako tudi AB na podproblema ABA in ABB. Podproblemi B, AA, ABA in ABB so dovolj preprosti, da jih znamo rešiti brez nadaljnega deljenja.


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).

Slika:vladaj.jpg
Slika prikazuje združevanje rešitev posameznih podproblemov.

S takšnim postopkom velikokrat pridemo do rekurzivnih rešitev, čeprav to ni pravilo in obstajajo tudi rešitve, ki niso rekurzivne narave.



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.

Deli in vladaj - zgodovina

Sun-Tzu: Umetnost vojskovanja (~ 2500 let nazaj)

Če je tvoja vojska 10x številčnejša od sovražnikove, ga obkoli, če je petkrat močnejša, napadi, če je dvakrat večja, razbij njegovo na dva dela. Armado 100000 mož je veliko lažje premagati, če jo razbiješ na dva dela po 50000 mož in premagaš vsak del zase. Če želiš vladati, poskrbi, da so tvoji sovražniki med seboj razdeljeni in ne združeni. V sovražnikove vrste vnesi neenotnost – razdeli jih in lahko jih boš premagal. http://www.psywarrior.com/DivideandConquer.html


Umetnost vladanja:

Kaj je storil vladar, če je bilo ozemlje preveliko, da bi ga sam nadziral? Razdelil ga je na manjša območja, na njih postavil zaupnike. Vladar je tako nadziral le še zaupnike. Zaupniki so potem obvladovali svoja območja – če so bila še prevelika, so jih lahko razdelili tudi sami.

Umetnost pogajanja:

Kaj stori pogajalec, če je nasprotna stran premočna in jim ne more uspešno parirati? Doseže, da nasprotna stran razpade na manjše, med seboj nepovezane skupine. Z manjšimi skupinami se laže “pogaja” (uveljavlja svojo voljo). Če je katera od takih manjših skupin še vedno trdovratna, uporabi isto taktiko – doseže, da se prično preprirati med seboj in razpadejo na še manjše dele. Skupek doseženega iz takšnih posameznih pogajanj je zagotovo pogajalcu v prid.

Zgledi

Glej tudi

Osebna orodja