Randomizirani algoritam

Randomizirani algoritam je algoritam koji koristi stepen slučajnosti kao deo svoje logike. Algoritam obično koristi uniformno raspoređene slučajne bitove kao pomoćni ulaz da vode njegovo ponašanje, u nadi da će se postići dobre performanse u "prosečnom slučaju", kada se u obzir uzmu svi mogući izbori slučajnih bitova. Formalno, učinak algoritma će biti slučajna promenljiva određena slučajnim bitovima; Prema tome, bilo tekuće vreme, bilo izlaz (ili oboje) su slučajne promenljive.

Potrebno je napraviti razliku između algoritama koji koriste slučajan ulaz da bi smanjili očekivano vreme izvršavanja ili zauzeće memorije, ali se uvek završavaju sa korektnim rezultatom (Las Vegas algoritam) za određeno vreme, i probabilističkih algoritama, kod kojih, u zavisnosti od slučajnog ulaza, postoji šansa da proizvedu netačan rezultat (Monte Karlo algoritam) ili da ne daju nikakav rezultat, bilo signaliziranjem greške ili neuspehom da se izvršavanje prekine.

U drugom slučaju, gde je u pitanju slučajano izvršavanje i nasumičan izlaz, termin "algoritam" za postupak je donekle upitan. U slučaju nasumičnog izlaza, to nije više formalno efektivni metod.

Kako god, u nekim slučajevima, probibalistički algoritmi su jedini praktičan način za rešavanje problema.

U uobičajenoj praksi, randomizirani algoritmi se aproksimiraju koristeći generator pseudoslučajnih brojeva umesto izvornih slučajnih bitova; takva primena može odstupati od očekivanog teorijskog ponašanja.

Motivacija

Kao motivacioni primer, razmotrimo problem pronalaženja elementa "a" u nekom nizu od n elemenata.

Ulaz: Niz od n≥2 elemenata, u kome je polovina ‘a’ elemenata, a drugu polovinu čine ‘b’ elementi.

Izlaz: Pronađeno neko ‘a’ u nizu.

Dajemo dve verzije algoritma, najpre Las Vegas algoritam, a zatim Monte Karlo algoritam.

Las Vegas algoritam:

findingA_LV(array A, n)
begin
    repeat
        Randomly select one element out of n elements.
    until 'a' is found
end

Ovaj algoritam postiže uspeh sa verovatnoćom 1. Dužina trajanja jednog poziva varira i može biti proizvoljno velika, ali očekivano vreme za većinu poziva je $\Theta (1)$. (Pogledaj veliko O)

Monte Karlo algoritam:

findingA_MC(array A, n, k)
begin
    i=0
    repeat
        Randomly select one element out of n elements.
        i = i + 1
    until i=k or 'a' is found
end

Ako je ‘a’ pronađeno, izvršavanje algoritma je uspešno, inače je neuspešno. Nakon k iteracija, verovatnoća pronalaska elementa ‘a’ je:

$\Pr[\mathrm {find~a} ]=1-(1/2)^{k}$

Ovaj algoritam ne garantuje uspeh, ali vreme izvršavanja je konstantno. Tokom mnogo poziva selekcija se izvršava očekivano 1≤k<2 puta, zato je vreme izvršavanja jednako $\Theta (1)$.

Randomizirani algoritmi su naročito korisni kada se suočavate sa zlonamernim "protivnikom" ili napadačem, koji namerno pokušava da "nahrani" loš ulaz u algoritam (pogledaj kompleksnost u najgorem slučaju i konkurentna analiza (online algoritam)) kao što je Dilema zatvorenika. Iz tog razloga je slučajnost sveprisutna u kriptografiji. U kriptografskim aplikacijama, pseudo-slučajni brojevi se ne mogu koristiti, jer ih protivnik može predvideti, praveći efektivan deterministički algoritam. Stoga je potrebno koristiti ili izvor zaista nasumičnih brojeva, ili kriptografski osiguran generator pseudo-slučajnih brojeva. Druga oblast gde se nasumičnost koristi je kvantno računarstvo.

U primeru iznad, Las Vegas algoritam uvek daje korektan odgovor, ali njegovo vreme izvršavanja je određeno slučajnom promenljivom. Monte Karlo algoritam (povezano sa Monte Karlo metoda za simulaciju) izvršava se u konstantnom vremenu (kao funkcija sa ulaznom veličinom), ali dozvoljava malu verovatnoću greške. Primetimo da se svaki Las Vegas algoritam može konvertovati u Monte Karlo algoritam (koristeći Markovljevu nejednakost) tako što će na izlazu biti proizvoljna vrednost, gde postoji mogućnost netačnog odgovora ukoliko ne uspe da se izvrši u određenom roku. Obrnuto, ako postoji efikasan postupak verifikacije kojim možemo proveriti da li je odgovor tačan, onda Monte Karlo algoritam može biti konvertovan u Las Vegas algoritam, pokretajući Monte Karlo algoritam u više navrata dok se ne dobije tačan odgovor.

Računarska komleksnost

Teorija kompleksnosti modeluje randomizirane algoritme kao probabilističku Tjuringovu mašinu. Oba algoritma, Las Vegas i Monte Karlo algoritam se razmatraju, i klase složenosti se proučavaju. Najosnovnija randomizirana klasa složenosti je RP (randomizirano polinomijalno vreme), što je klasa problema odlučivanja, za koju postoji efikasan (polinomijalno vreme) randomizirani algoritam (ili probabilistička Tjuringova mašina) koji prepoznaje negativne instance sa apsolutnom sigurnošću i pozitivne instance sa verovatnoćom od najmanje 1/2. Komplementna klasa za RP je komplement-RP.

Klasa problema gde se algoritmi izvršavaju u polinomijalnom vremenu i čiji izlaz je uvek korektan, naziva se i probabilističko polinomijalno vreme bez grešaka (en. zero-error probabilistic polynomial time, ZPP).

Klasa problema gde je dozvoljeno da se i DA i NE-instance identifikiju sa nekom greškom naziva se probabilističko polinomijalno vreme sa ograničenom greškom (en. Bounded-error probabilistic polynomial, BPP). Ova klasa se ponaša kao nasumični ekvivalent od P, odnosno BPP, i predstavlja klasu efikasnih nasumičnih algoritama.

Istorijat

Istorijski, prvi randomizirani algoritam bio je metod razvijen od strane Majkla Rabina za algoritam dve najbliže tačke u računarskoj geometriji.

Proučavanje randomiziranih algoritama bilo je podstaknuto 1977. godine otkićem randomiiziranog testa za proste brojeve (odnosno, određivanje da li je broj prost) od strane Soloveja i Štrasena. Ubrzo nakon toga, Majkl Rabin je pokazao da Miler-Rabinov test iz 1976. može biti pretvoren u randomizirani algoritam. U to vreme, ni jedan praktičan deterministički algoritam za proste brojeve nije bio poznat.

Miler-Rabinov test za proste brojeve zasniva se na binarnoj relaciji između dva pozitivna cela broja k i n koji se mogu izraziti rečima: " k je svedok složenosti broja n ". Može se pokazati:

• Ako postoji svedok složenosti broja n, onda je n složen broj (odnosno, n nije prost broj),
• Ako je n složen broj, onda su najmanje tri četvrtine prirodnih brojeva manjih od n svedoci njegove složenosti,
• Postoji brz algoritam koji, uz dato k i n, utvrđuje da li je k svedok složenosti broja n. Zapazimo da to znači da je problem određivanja da li je broj prost složenosti komplement-RP.

Ako se nasumično izabere 100 brojeva manjih od složenog broja n, onda je verovatnoća da se među njima ne nađe "svedok" jednaka (1/4)¹⁰⁰, tako da za većinu praktičnih primena, ovo je dobar test za određivanje složenosti broja. Ako je n veliko, može biti da ne postoji neki drugi praktičan test. Verovatnoća greške može biti redukovana na proizvoljan nivo obavljanjem više nezavisnih testova.

Iz tog razloga, u praksi, nema penala u vezi sa prihvatanjem male verovatnoće greške, jer, uz malo pažnje, verovatnoća greške može biti astronomski mala. Zaista, iako je u međuvremenu pronađen deterministički test, koji određuje da li je broj prost u polinomijalnom vremenu (pogledaj AKS), u praksi nije zamenio starije probabilističke testove u kriptografiji, niti se očekuje da se to dogodi u bliskoj budućnosti.

Primeri

Kviksort

Kviksort je poznat, često korišćen algoritam, gde nasumičnost može biti korisna. Bilo koja deterministička verzija ovog algoritma zahteva O(n²) vreme da sortira n brojeva za dobro definisanu klasu degenerisanih ulaza (kao što je već sortiran niz), sa specifičnom klasom ulaza koji generišu ovakvo ponašanje definisano protokolom za izbor pivota. Kako god, ako algoritam izabere pivot nasumice, ima dokazivo veliku verovatnoću da vreme izvršavanja bude O(n log n), nezavisno od karakteristika ulaza.

Randomizirane inkrementalne konstrukcije u geometriji

U računarskoj geometriji, standardna tehnika za izgradnju strukture kao što je konveksni omotač, ili Delanijeva triangulacija jeste da se nasumično permutuju ulazne tačke i onda jedna po jedna ubacuju u postojeću strukturu. Nasumičnost osigurava da je očekivani broj izmena u strukturi, izazvanih ubacivanjem, mali, i zato očekivano vreme izvršavanja algoritma može biti ograničeno odozgo. Ova tehnika je poznata kao randomizirana inkrementalna konstrukcija.

Verifikacija množenja matrica

Ulaz: Matrice A ∈ R^{m × p}, B ∈ R^{p × n}, i C ∈ R^{m × n}.

Izlaz: Tačno, ako C = A · B; netačno, ako C ≠ A · B

Dajemo Monte Karlo algoritam kao rešenje ovog problema.

 begin
   i=1
   repeat
       Choose r=(r1,...,rn) ∈ {0,1}n at random.
       Compute C · r and A · (B · r)
       if C · r ≠ A · (B · r)
           return FALSE
       endif
       i = i + 1
   until i=k
   return TRUE
 end

Vremenska složenost ovog algoritma je $O(kn^{2})$.

Teorema: Algoritam je tačan sa verovatnoćom od najmanje $1-\left({\frac {1}{2}}\right)^{k}$.

Dokazaćemo da ako $A\cdot B\neq C$ onda $Pr[A\cdot B\cdot r=C\cdot r]\leq 1/2$.

Ako je $A\cdot B\neq C$, po definiciji imamo $D=A\cdot B-C\neq 0$. Bez gubljenja na opštosti, možemo pretpostaviti da je $d_{11}\neq 0$.

Sa druge strane, $Pr[A\cdot B\cdot r=C\cdot r]=Pr[(A\cdot B-C)\cdot r=0]=Pr[D\cdot r=0]$.

Ako je $D\cdot r=0$, onda je prvi unos $D\cdot r$ jednak 0, što je

$\sum _{j=1}^{n}d_{1j}r_{j}=0$

Pošto $d_{11}\neq 0$, možemo rešiti za $r_{1}$:

$r_{1}={\frac {-\sum _{j=2}^{n}d_{1j}r_{j}}{d_{11}}}$

Ako popravimo sve $r_{j}$, osim $r_{1}$, jednakost važi za najviše jedan od dva izbora $r_{1}\in \{0,1\}$. Zato, $Pr[ABr=Cr]\leq 1/2$.

Prolazimo kroz petlju k puta. Ako je $C=A\cdot B$, algoritam je uvek tačan; ako $C\neq A\cdot B$, verovatnoća dobijanja korektnog odgovora je najmanje $1-\left({\frac {1}{2}}\right)^{k}$.

Minimalan rez grafa

Главни чланак: Kargerov algoritam

Ulaz: Graf G(V,E).

Izlaz:Minimalan rez grafa G, u kome su temena podeljena u L i R skupove, sa minimalnim brojem grana između L i R.

Podsetimo da kontrakcija dva čvora, u i v, u (multi)grafu daje novi čvor u', sa granama koje predstavljaju uniju grana incidentnih sa u ili v, osim za granu, ili grane koje spajaju u i v. Slika 1 daje primer kontrakcije temena A i B.

Nakon kontrakcije, rezultujići graf može imati paralelne grane, ali ne sadrži petlje.

Slika 2: Uspešno primenjen Kargerov algoritam na graf sa 10 čvorova. Minimalno smanjenje gafa je veličine 3 i označeno je bojama temena.

Slika 1: Kontrakcija temena A i B

Kargerov osnovni algoritam:

 begin
   i=1
   repeat
     repeat
        Take a random edge (u,v)∈ E in G
        replace u and v with the contraction u'
     until only 2 nodes remain
     obtain the corresponding cut result Ci
     i=i+1
   until i=m
   output the minimum cut among C1,C2,...,Cm.
 end

U svakom izvršavanju spoljne petlje, algoritam ponavlja unutrašnju petlju sve dok ne ostanu 2 čvora, i odgovarajući rez je dobijen. Vreme jednog izvršavanja je $O(n)$, gde n označava broj temena.

Nakon m izvršavanja spoljne petlje, na izlazu se nalazi minimum od svih rezultata. Slika 2 daje primer jednog izvršavanja algoritma. Nakon izvršavanja, dobijamo minimalan rez veličine 3.

Lema 1: Neka je k veličina minimalnog reza, i neka je C = {e₁,e₂,...,e_k} minimalan rez. Ako, tokom i-te iteracije, ni jedna ivica e ∈ C nije selektovana za kontrakciju, onda C_i = C.

Dokaz: Ako graf G nije povezan, onda G može biti particionisan u L i R skupove, bez ijedne grane između njih. Dakle, minimalan rez nepovezanog grafa je 0. Sada pretpostavimo da je G povezan. Neka je V=L∪R podela inukovana od strane C : C={ {u,v} ∈ E : u ∈ L,v ∈ R } (dobro je definisano, jer je G povezan). Razmotrimo granu {u,v} koja pripada C. Inicijalno, u,v su različita temena. Sve dok uzimamo granu f različitu od e, ne vršiti spajanje u i v. Zato, na kraju algoritma, dobijamo dva složena čvora koji pokrivaju čitav graf, od kojih se jedan sastoji od L, a drugi od R temena. Na slici 2, veličina minimalnog smanjenja je 1, i C = {(A,B)}. Ako ne bismo upotrebili (A,B) za kontrakciju, ne bismo dobili minimalno smanjenje.

Lema 2: Ako je G multigraf sa p čvorova, i čiji je minimalan rez veličine k, tada G ima najmanje pk/2 ivica.

Dokaz: Pošto je k veličina minimalnog reza, svaki čvor v mora zadovoljiti stepen (v) ≥ k. Zato, suma svih stepena čvorova je najmanje pk. Ali, pošto je poznato da je suma svih stepena čvorova jednaka 2|E|, lema je dokazana.

Analiza algoritma

Verovatnoća da će se algoritam izvršiti uspešno jednaka je 1 − verovatnoća da će svi pokušaji biti neuspešni.

Do nezavisnosti, verovatnoća da svi pokušaju budu neuspešni je

$\prod _{i=1}^{m}\Pr(C_{i}\neq C)=\prod _{i=1}^{m}(1-\Pr(C_{i}=C)).$

Iz leme 1, verovatnoća da je C_i = C je verovatnoća da ni jedna grana od C nije selektovana tokom i-te iteracije. Razmotrimo unutrašnju petlju i neka G_j označava graf nakon j kontrakcija grana, gde je j ∈ {0,1,...,n − 3}. G_j ima n − j čvorova. Iskoristimo pravilo lanca uslovne verovatnoće.

Verovatnoća da grana izabrana u j-toj iteraciji nije u C, što znači da ni jedna grana od C nije ranije izabrana, je $1-{\frac {k}{|E(G_{j})|}}$. Zapazimo da je G_j minimalan rez veličine k, pa iz leme 2, i dalje ima najmanje ${\frac {(n-j)k}{2}}$ grana.

Sledi: $1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}$.

Dakle, iz pravila lanca, verovatnoća pronalaska minimalnog smanjenja C je $Pr[C_{i}=C]\geq \left({\frac {n-2}{n}}\right)\left({\frac {n-3}{n-1}}\right)\left({\frac {n-4}{n-2}}\right)\ldots \left({\frac {3}{5}}\right)\left({\frac {2}{4}}\right)\left({\frac {1}{3}}\right).$

Otkazivanje daje $\Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}$. Zato je verovatnoća da algoritam uspe najmanje $1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}$. Za $m={\frac {n(n-1)}{2}}\ln n$, ovo je ekvivalentno sa $1-{\frac {1}{n}}$. Algoritam pronalazi minimalan rez sa verovatnoćom $1-{\frac {1}{n}}$, u vremenu $O(mn)=O(n^{3}\log n)$.

Derandomizacija

Nasumičnost može da se posmatra kao resurs, kao prostor i vreme. Derandomizacija je onda proces uklanjanja slučajnosti. Sa tačke gledišta računarske kompleksnosti, derandomizacija efikasnog randomiziranog algoritma je pitanje da li P = BPP ?

Postoje i specifični metodi koji mogu biti iskorišćeni za derandomizaciju konkretnih randomiziranih algoritama:

• Metod uslovne verovatnoće, i njegova generalizacija, Pesimistička procena,
• Teorija neslaganja (koristi se za derandomizaciju geometrijskih algoritama),
• Eksploatacija ograničene nezavisnosti slučajnih promenljivih koje se upotrebljavaju u algoritmu, kao što je poravnanje nezavisnosti koje se koristi u univerzalnom heširanju,
• Upotreba ekspanzionog grafa da pojača ograničenu količinu inicijalne slučajnosti (ovaj poslednji pristup je takođe poznat kao generisanje pseudo-slučajnih bitova iz nasumičnog izvora, i vodi do povezane teme o pseudo-slučajnosti).

Gde slučajnost pomaže

Kada je model izračunavanja ograničen na Tjuringovu mašinu, trenutno je otvoreno pitanje da li mogućnost pravljenja slučajnih izbora dozvoljava da neki problemi budu rešeni u polinomijalnom vremenu, a ne mogu biti tako rešeni bez ove mogućnosti; Ovo je pitanje da li je P = BPP. Međutim, u drugim kontekstima, postoje specifični primeri problema gde nasumičnost doprinosti striktnim poboljšanjima.

• Na osnovu početnog motivacionog primera: dat je eksponencijalno dug niz od 2^k karaktera, gde jednu polovinu čine "a", a drugu "b" karakteri. Mašina sa slučajnim pristupom zahteva najmanje 2^k−1 pretraga u najgorem slučaju da bi se vratio indeks od prvog pronađenog "a"; ako je dozvoljeno pravljenje nasumičnih izbora, očekivani broj pretraga može biti polinomijalan.

• Prirodan način vršenja numeričkog računanja u ugrađenim sistemima ili sajber-fizičkim sistemima, jeste da se obezbedi rezultat koji je približno jednak tačnom, sa velikom verovatnoćom uspeha. Veliki problem u vezi sa procenom gubitka (razlika između tačnog i približno tačnog rešenja) može se efikasno rešiti oslanjanjem na sučajnost.

• U komunikacionoj složenosti, jednakost dva niza može se utvrditi sa nekom pouzdanošću koristeći $\log n$ bitova komunikacije sa randomiziranim protokolom. Bilo koji deterministički protokol zahteva $\Theta (n)$ bitova za odbranu od jakog protivnika.

• Obim konveksnog tela može se proceniti randomiziranim algoritmom do proizvoljne preciznosti u polinomijalnom vremenu. Bárány i Füredi pokazali su da nijedan deterministički algoritam ne može da uradi isto to.

Literatura

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (1990). Introduction to Algorithms. Second Edition. MIT Press and McGraw–Hill. ISBN 0-262-03293-7.  Chapter 5: Probabilistic Analysis and Randomized Algorithms. стр. 91–122.
• Jon Kleinberg and Éva Tardos. Algorithm Design. Chapter 13: "Randomized algorithms".
• Fallis, D. (2000). „The Reliability of Randomized Algorithms”. The British Journal for the Philosophy of Science. 51 (2): 255—271. doi:10.1093/bjps/51.2.255. 
• M. Mitzenmacher and E. Upfal. Probability and Computing : Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (NY), 2005.
• Rajeev Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York (NY), 1995.
• Rajeev Motwani and P. Raghavan. Randomized Algorithms. A survey on Randomized Algorithms.
• Papadimitriou, Christos (1993). „11: Randomized computation”. Computational Complexity (1st изд.). Addison Wesley. стр. 241—278. ISBN 0-201-53082-1. 
• M. O. Rabin. (1980), "Probabilistic Algorithm for Testing Primality." Journal of Number Theory 12:128–38.
• A. A. Tsay, W. S. Lovejoy, David R. Karger, Random Sampling in Cut, Flow, and Network Design Problems, Mathematics of Operations Research, 24(2):383–413, 1999.