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 . (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:
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 .
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)100, 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(n2) 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.Seidel R. Backwards Analysis of Randomized Geometric Algorithms.
Verifikacija množenja matrica
Ulaz: Matrice A ∈ Rm × p, B ∈ Rp × n, i C ∈ Rm × n.
Izlaz: Tačno, ako C = A · B; netačno, ako C ≠ A · B
Dajemo Monte Karlo algoritam kao rešenje ovog problema.Michael Mitzenmacher, Eli Upfal. Probability and Computing:Randomized Algorithms and Probabilistic Analysis, April 2005. Cambridge University Press 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 .
Teorema: Algoritam je tačan sa verovatnoćom od najmanje .
Dokazaćemo da ako onda .
Ako je , po definiciji imamo . Bez gubljenja na opštosti, možemo pretpostaviti da je .
Sa druge strane, .
Ako je , onda je prvi unos jednak 0, što je
Pošto , možemo rešiti za :
Ako popravimo sve , osim , jednakost važi za najviše jedan od dva izbora . Zato, .
Prolazimo kroz petlju k puta. Ako je , algoritam je uvek tačan; ako , verovatnoća dobijanja korektnog odgovora je najmanje .
Minimalan rez grafa
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. thumb|340px|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. 300px|thumb|center|Slika 1: Kontrakcija temena A i B KargerovA. 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. 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. endU 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 , 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 = {e1,e2,...,ek} minimalan rez. Ako, tokom i-te iteracije, ni jedna ivica nije selektovana za kontrakciju, onda .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 i . 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: