Algoritm randomizat - Randomized algorithm

Un algoritm randomizat este un algoritm care folosește un grad de aleatoriu ca parte a logicii sau procedurii sale. Algoritmul folosește de obicei biți uniform aleatori ca intrare auxiliară pentru a-i ghida comportamentul, în speranța de a obține performanțe bune în „caz mediu” peste toate alegerile posibile ale aleatoare determinate de biții aleatori; astfel, fie timpul de rulare, fie ieșirea (sau ambele) sunt variabile aleatorii.

Trebuie să facem distincția între algoritmi care utilizează intrarea aleatorie, astfel încât aceștia să se încheie întotdeauna cu răspunsul corect, dar unde timpul de funcționare așteptat este finit ( algoritmi Las Vegas , de exemplu Quicksort ) și algoritmi care au șansa de a produce un rezultat incorect. ( Algoritmii Monte Carlo , de exemplu algoritmul Monte Carlo pentru problema MFAS ) sau nu reușesc să producă un rezultat fie prin semnalarea unui eșec, fie prin eșecul terminării. În unele cazuri, algoritmii probabilistici sunt singurul mijloc practic de rezolvare a unei probleme.

În practica obișnuită, algoritmii randomizați sunt aproximați utilizând un generator de numere pseudorandomale în locul unei adevărate surse de biți aleatori; o astfel de implementare se poate abate de la comportamentul teoretic așteptat și de la garanțiile matematice care pot depinde de existența unui generator de numere aleatoare adevărat ideal.

Motivație

Ca exemplu motivant, luați în considerare problema găsirii unui „ a ” într-o serie de n elemente.

Intrare : o matrice de n ≥2 elemente, în care jumătate sunt „ a ” și cealaltă jumătate sunt „ b ”.

Ieșire : găsiți un „ a ” în matrice.

Oferim două versiuni ale algoritmului, unul din Las Vegas și unul din Monte Carlo .

Algoritmul din Las Vegas:

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

Acest algoritm reușește cu probabilitatea 1. Numărul de iterații variază și poate fi arbitrar mare, dar numărul așteptat de iterații este

{\ displaystyle \ lim _ {n \ to \ infty} \ sum _ {i = 1} ^ {n} {\ frac {i} {2 ^ {i}}} = 2}

Deoarece este constant, timpul de funcționare așteptat pentru multe apeluri este . (A se vedea notația Big Theta ) ${\ displaystyle \ Theta (1)}$

Algoritmul Monte Carlo:

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

Dacă se găsește un „ a ”, algoritmul reușește, altfel algoritmul eșuează. După k iterații, probabilitatea de a găsi o „ a ” este:

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

Acest algoritm nu garantează succesul, dar timpul de rulare este limitat. Numărul de iterații este întotdeauna mai mic sau egal cu k. Luând k pentru a fi constant timpul de rulare (așteptat și absolut) este . ${\ displaystyle \ Theta (1)}$

Algoritmii randomizați sunt deosebit de utili atunci când se confruntă cu un „adversar” sau atacator rău intenționat care încearcă în mod deliberat să furnizeze o intrare proastă algoritmului (a se vedea complexitatea în cel mai rău caz și analiza competitivă (algoritm online) ), cum ar fi dilema prizonierului . Din acest motiv, întâmplarea este omniprezentă în criptografie . În aplicațiile criptografice, numerele pseudo-aleatorii nu pot fi utilizate, deoarece adversarul le poate prezice, făcând algoritmul efectiv determinist. Prin urmare, este necesară fie o sursă de numere cu adevărat aleatorii, fie un generator de numere pseudo-aleatorii sigure criptografic . Un alt domeniu în care caracterul aleatoriu este inerent este calculul cuantic .

În exemplul de mai sus, algoritmul Las Vegas oferă întotdeauna răspunsul corect, dar timpul său de rulare este o variabilă aleatorie. Algoritmul Monte Carlo (legat de metoda Monte Carlo pentru simulare) este garantat pentru a finaliza într-o perioadă de timp care poate fi mărginită de o funcție de dimensiunea de intrare și parametrul său k , dar permite o probabilitate mică de eroare . Observați că orice algoritm Las Vegas poate fi convertit într-un algoritm Monte Carlo (prin inegalitatea lui Markov ), oferindu-i un răspuns arbitrar, posibil incorect, dacă nu reușește să se termine într-un timp specificat. În schimb, dacă există o procedură eficientă de verificare pentru a verifica dacă un răspuns este corect, atunci un algoritm Monte Carlo poate fi convertit într-un algoritm Las Vegas executând algoritmul Monte Carlo în mod repetat până când se obține un răspuns corect.

Complexitatea computațională

Teoria complexității computaționale modelează algoritmi randomizați ca mașini probabilistice de Turing . Atât Las Vegas și algoritmi Monte Carlo sunt luate în considerare, și mai multe clase de complexitate sunt studiate. Cea mai de bază clasă de complexitate randomizată este RP , care este clasa problemelor de decizie pentru care există un algoritm randomizat eficient (timp polinomial) (sau mașină probabilistică de Turing) care recunoaște instanțele NO cu certitudine absolută și recunoaște instanțele DA cu o probabilitate de cel puțin 1/2. Clasa de complement pentru RP este co-RP. Se spune că clasele de probleme care au algoritmi (posibil neterminatori) cu timp polinomial timp mediu de rulare a cazurilor a căror ieșire este întotdeauna corectă sunt în ZPP .

Clasa de probleme pentru care atât DA, cât și NO-instanțe sunt permise să fie identificate cu o anumită eroare se numește BPP . Această clasă acționează ca echivalentul randomizat al lui P , adică BPP reprezintă clasa algoritmilor randomizați eficienți.

Istorie

Din punct de vedere istoric, primul algoritm randomizat a fost o metodă dezvoltată de Michael O. Rabin pentru cea mai apropiată problemă de pereche în geometria de calcul . Studiul algoritmilor randomizați a fost stimulat de descoperirea din 1977 a unui test de primalitate randomizată (adică, determinarea primalității unui număr) de Robert M. Solovay și Volker Strassen . Curând după aceea, Michael O. Rabin a demonstrat că testul de primărie al lui Miller din 1976 poate fi transformat într-un algoritm randomizat. În acel moment, nu se cunoștea niciun algoritm practic determinist pentru primalitate.

Testul de primărie Miller-Rabin se bazează pe o relație binară între două numere întregi pozitive k și n care poate fi exprimată spunând că k "este un martor al compoziției lui" n . Se poate arăta că

Dacă există un martor al compoziției lui n , atunci n este compus (adică n nu este prim ) și
Dacă n este compus, cel puțin trei sferturi din numerele naturale mai mici de n sunt martori ai compoziției sale și
Există un algoritm rapid care, având în vedere k și n , stabilește dacă k este un martor al compoziției lui n .

Observați că acest lucru implică faptul că problema primării se află în Co- RP .

Dacă se alege în mod aleatoriu 100 de numere mai mici decât un număr compus n , atunci probabilitatea de a nu găsi un astfel de „martor” este (1/4) ^100, astfel încât, în cele mai multe scopuri practice, acesta este un bun test de primărie. Dacă n este mare, este posibil să nu existe alt test practic. Probabilitatea de eroare poate fi redusă într-un grad arbitrar prin efectuarea unor teste independente suficiente.

Prin urmare, în practică, nu există nici o penalizare asociată cu acceptarea unei probabilități mici de eroare, deoarece cu puțină grijă probabilitatea de eroare poate fi redusă din punct de vedere astronomic. Într-adevăr, chiar dacă a fost găsit un test de primalitate determinant în timp polinomial (a se vedea testul de primalitate AKS ), nu a înlocuit testele probabilistice mai vechi din software-ul criptografic și nici nu se așteaptă să o facă în viitorul previzibil.

Exemple

Sortare rapida

Quicksort este un algoritm familiar, utilizat în mod obișnuit, în care întâmplarea poate fi utilă. Multe versiuni deterministe ale acestui algoritm necesită timp O ( n ² ) pentru a sorta n numere pentru unele clase bine definite de intrări degenerate (cum ar fi o matrice deja sortată), cu clasa specifică de intrări care generează acest comportament definit de protocolul pentru selectarea pivotului. Cu toate acestea, dacă algoritmul selectează elementele pivot în mod uniform la întâmplare, are o probabilitate ridicată de a termina în timp O ( n log n ) indiferent de caracteristicile intrării.

Construcții incrementale aleatorii în geometrie

În geometria computațională , o tehnică standard pentru a construi o structură precum o carenă convexă sau triangulația Delaunay este de a permuta în mod aleatoriu punctele de intrare și apoi de a le introduce unul câte unul în structura existentă. Randomizarea asigură faptul că numărul așteptat de modificări ale structurii cauzate de o inserție este mic și, prin urmare, timpul de funcționare a algoritmului poate fi delimitat de sus. Această tehnică este cunoscută sub numele de construcție incrementală randomizată .

Min tăiere

Intrare : Un grafic G ( V , E )

Output : O taie partiționare nodurile în L și R , cu numărul minim de muchii între L și R .

Reamintim că contracția a două noduri, u și v , într - un grafic (multi) conduce la un nou nod u 'cu margini care unirea incidentului margini fie pe u sau v , cu excepția de orice muchie (e) conectarea u și v . Figura 1 prezintă un exemplu de contracție a nodurilor A și B . După contracție, graficul rezultat poate avea margini paralele, dar nu conține bucle auto.

Figura 2: Executarea cu succes a algoritmului Karger pe un grafic cu 10 vârfuri. Tăierea minimă are dimensiunea 3 și este indicată de culorile vârfului.

Figura 1: Contracția vârfului A și B

Algoritmul de bază al lui Karger:

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 C_i
        i = i + 1
    until i = m
    output the minimum cut among C₁, C₂, ..., C_m.
end

În fiecare execuție a buclei externe, algoritmul repetă bucla interioară până când rămân doar 2 noduri, se obține tăierea corespunzătoare. Timpul de rulare al unei execuții este și n denotă numărul de vârfuri. După m ori de execuții ale buclei exterioare, vom scoate tăierea minimă dintre toate rezultatele. Figura 2 oferă un exemplu de execuție a algoritmului. După execuție, obținem o tăietură de mărimea 3. ${\ displaystyle O (n)}$

Lema 1 - Fie k dimensiunea minimă a tăieturii și fie $C = {e 1, e 2, ..., e k}$ minima tăiată. În cazul în care , în timpul iterația i , nici o muchie $e \in C$ este selectată pentru contracție, atunci $C i = C$ .

Dovadă -

Dacă G nu este conectat, atunci G poate fi partiționat în L și R fără nici o margine între ele. Deci minul tăiat într-un grafic deconectat este 0. Acum, să presupunem că G este conectat. Fie $V = L \cup R$ partiția lui V indusă de $C : C = {{u, v} \in E : u \in L, v \in R}$ (bine definită deoarece G este conectat). Să considerăm o margine { u , v } din C . Inițial, u , v sunt vârfuri distincte. Atâta timp cât alegem o margine , $u$ și $v$ nu se îmbină. ${\ displaystyle f \ neq e}$ Astfel, la finalul algoritmului, avem două noduri compuse care acoperă întregul grafic, este unul format din nodurile L și celălalt constând din nodurile R . La fel ca în figura 2, dimensiunea tăierii minime este 1 și C = {( A , B )}. Dacă nu selectăm ( A , B ) pentru contracție, putem obține reducerea minimă.

Lema 2 - Dacă G este un multigraf cu vârfuri p și a cărui min tăietură are dimensiunea k , atunci G are cel puțin pk / 2 muchii.

Dovadă -

Deoarece tăierea min este k , fiecare vârf v trebuie să satisfacă gradul ( v ) ≥ k . Prin urmare, suma gradului este de cel puțin pk . Dar se știe că suma gradelor de vârf este egală cu 2 | E |. Urmează lema.

Analiza algoritmului

Probabilitatea ca algoritmul să aibă succes este 1 - probabilitatea ca toate încercările să eșueze. Prin independență, probabilitatea ca toate încercările să eșueze este

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

Prin lema 1, probabilitatea ca $C i = C$ este probabilitatea ca nici o margine a lui C să nu fie selectată în timpul iterației i . Luați în considerare bucla interioară și lăsați $G j să$ denoteze graficul după j contracții de margine, unde $j \in {0, 1, ..., n - 3}$ . $G j$ are $n - j$ vârfuri. Folosim regula lanțului posibilităților condiționale . Probabilitatea ca muchia aleasă la iterația j să nu fie în C , având în vedere că nu a fost aleasă nici o margine a lui C , este . De notat că $G$ $j$ are încă tăiate min de dimensiune k , deci de Lema 2, are încă cel puțin margini. ${\ displaystyle 1 - {\ frac {k} {| E (G_ {j}) |}}}$ ${\ displaystyle {\ frac {(nj) k} {2}}}$

Astfel ,. ${\ displaystyle 1 - {\ frac {k} {| E (G_ {j}) |}} \ geq 1 - {\ frac {2} {nj}} = {\ frac {nj-2} {nj}} }$

Deci, prin regula lanțului, probabilitatea de a găsi tăierea minimă C este

{\ displaystyle \ 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).}

Anularea dă . Astfel, probabilitatea ca algoritmul să aibă succes este cel puțin . Pentru că acest lucru este echivalent cu . Algoritmul găsește reducerea minimă cu probabilitate , în timp . ${\ displaystyle \ Pr [C_ {i} = C] \ geq {\ frac {2} {n (n-1)}}}$ ${\ displaystyle 1- \ left (1 - {\ frac {2} {n (n-1)}} \ right) ^ {m}}$ ${\ displaystyle m = {\ frac {n (n-1)} {2}} \ ln n}$ ${\ displaystyle 1 - {\ frac {1} {n}}}$ ${\ displaystyle 1 - {\ frac {1} {n}}}$ ${\ displaystyle O (mn) = O (n ^ {3} \ log n)}$

Derandomizare

Aleatoritatea poate fi privită ca o resursă, cum ar fi spațiul și timpul. Derandomizarea este apoi procesul de eliminare a întâmplării (sau de a utiliza cât mai puțin din ea posibil). În prezent nu se știe dacă toți algoritmii pot fi derandomizați fără a-și crește semnificativ timpul de funcționare. De exemplu, în complexitatea de calcul , nu se știe dacă P = BPP , adică nu știm dacă putem lua un algoritm arbitrar randomizat care rulează în timp polinomial cu o probabilitate mică de eroare și să-l derandomizăm pentru a rula în timp polinomial fără a utiliza aleatoriu .

Există metode specifice care pot fi utilizate pentru derandomizarea anumitor algoritmi randomizați:

metoda probabilităților condiționate , și generalizarea acesteia, estimatori pesimiste
teoria discrepanței (care este utilizată pentru derandomizarea algoritmilor geometrici)
exploatarea independenței limitate în variabilele aleatorii utilizate de algoritm, cum ar fi independența în perechi utilizată în hashul universal
utilizarea graficelor de expansiune (sau a dispersoarelor în general) pentru a amplifica o cantitate limitată de aleatorizare inițială (această ultimă abordare este denumită și generarea de biți pseudorandomiali dintr-o sursă aleatorie și duce la subiectul conex al pseudorandomiei)
schimbarea algoritmului randomizat pentru a utiliza o funcție hash ca sursă de întâmplare pentru sarcinile algoritmului și apoi derandomizarea algoritmului prin forțarea brută a tuturor parametrilor (semințe) posibili ai funcției hash. Această tehnică este de obicei utilizată pentru a căuta în mod exhaustiv un spațiu eșantion și pentru a face algoritmul determinist (de exemplu, algoritmi de grafic aleatori)

Acolo unde întâmplarea ajută

Când modelul de calcul este limitat la mașinile Turing , este în prezent o întrebare deschisă dacă abilitatea de a face alegeri aleatorii permite rezolvarea unor probleme în timp polinomial care nu pot fi rezolvate în timp polinomial fără această abilitate; aceasta este întrebarea dacă P = BPP. Cu toate acestea, în alte contexte, există exemple specifice de probleme în care randomizarea produce îmbunătățiri stricte.

Pe baza exemplului motivant inițial: având în vedere un șir exponențial lung de 2 ^k caractere, jumătate a și jumătate b, o mașină cu acces aleatoriu necesită 2 ^{k -1} căutări în cel mai rău caz pentru a găsi indicele unui a ; dacă este permis să se facă alegeri aleatorii, poate rezolva această problemă într-un număr polinomial așteptat de căutări.
Modul natural de a efectua un calcul numeric în sisteme încorporate sau sisteme cibernetice este de a oferi un rezultat care să se apropie de cel corect cu probabilitate ridicată (sau calculul probabil aproximativ corect (PACC)). Problema grea asociată cu evaluarea pierderii discrepanței dintre calculul aproximativ și calculul corect poate fi abordată în mod eficient recurgând la randomizare
În complexitatea comunicării , egalitatea a două șiruri poate fi verificată cu o anumită fiabilitate utilizând biți de comunicare cu un protocol randomizat. Orice protocol determinist necesită biți dacă se apără împotriva unui adversar puternic. ${\ displaystyle \ log n}$ ${\ displaystyle \ Theta (n)}$
Volumul unui corp convex poate fi estimat de un algoritm randomizat la o precizie arbitrară în timp polinomial. Bárány și Füredi au arătat că niciun algoritm determinist nu poate face același lucru. Acest lucru este adevărat necondiționat, adică fără a se baza pe nicio ipoteză teoretică a complexității, presupunând că corpul convex poate fi interogat doar ca o cutie neagră.
Un exemplu teoretic mai complex al unui loc unde întâmplarea pare să ajute este clasa IP . IP constă din toate limbile care pot fi acceptate (cu probabilitate mare) printr-o interacțiune polinomială lungă între un prover atotputernic și un verificator care implementează un algoritm BPP. IP = PSPACE . Cu toate acestea, dacă este necesar ca verificatorul să fie determinist, atunci IP = NP .
Într-o rețea de reacții chimice (un set finit de reacții cum ar fi A + B → 2C + D care operează pe un număr finit de molecule), capacitatea de a ajunge vreodată la o stare țintă dată dintr-o stare inițială este decisă, în timp ce se aproximează chiar și probabilitatea de atingerea vreodată a unei stări țintă date (folosind probabilitatea standard bazată pe concentrație pentru care reacția va avea loc în continuare) este indecisibilă. Mai exact, o mașină Turing limitată poate fi simulată cu o probabilitate arbitrară de mare de a funcționa corect din toate timpurile, numai dacă se folosește o rețea de reacție chimică aleatorie. Cu o rețea simplă de reacții chimice nedeterministe (orice reacție posibilă se poate întâmpla în continuare), puterea de calcul este limitată la funcții recursive primitive .

Vezi si

Note

Referințe

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest și Clifford Stein . Introducere în algoritmi , ediția a doua. MIT Press și McGraw – Hill, 1990. ISBN 0-262-03293-7 . Capitolul 5: Analiza probabilistică și algoritmii randomizați, pp. 91-122.
Dirk Draheim. „ Semantica calculului Lambda de tip probabilistic (Semantica lanțului Markov, comportamentul de terminare și semantica denotațională). ” Springer, 2017.
Jon Kleinberg și Éva Tardos . Proiectarea algoritmului . Capitolul 13: „Algoritmi aleatori”.
Fallis, D. (2000). „Fiabilitatea algoritmilor randomizați”. British Journal for the Philosophy of Science . 51 (2): 255-271. doi : 10.1093 / bjps / 51.2.255 .
M. Mitzenmacher și E. Upfal . Probabilitate și calcul: algoritmi randomizați și analiză probabilistică . Cambridge University Press, New York (NY), 2005.
Rajeev Motwani și P. Raghavan. Algoritmi aleatori . Cambridge University Press, New York (NY), 1995.
Rajeev Motwani și P. Raghavan. Algoritmi aleatori . Un sondaj asupra algoritmilor randomizați.
Christos Papadimitriou (1993), Complexitate computațională (prima ediție), Addison Wesley, ISBN 978-0-201-53082-7 Capitolul 11: Calcul aleatoriu, pp. 241-278.
Rabin, Michael O. (1980). „Algoritm probabilistic pentru testarea primalității” . Journal of Number Theory . 12 : 128–138. doi : 10.1016 / 0022-314X (80) 90084-0 .
AA Tsay, WS Lovejoy, David R. Karger, Eșantionare aleatorie în probleme de proiectare a tăieturii, fluxului și rețelei , Matematica operațiunilor de cercetare, 24 (2): 383-413, 1999.

Languages

In other projects