Algorytm losowy

Algorytm losowy to algorytm , który wykorzystuje pewien stopień losowości jako część swojej logiki lub procedury. Algorytm zwykle wykorzystuje jednolicie losowe bity jako pomocnicze dane wejściowe do kierowania swoim zachowaniem, w nadziei na osiągnięcie dobrej wydajności w „przeciętnym przypadku” we wszystkich możliwych wyborach losowych określonych przez losowe bity; zatem albo czas działania, albo wynik (lub oba) są zmiennymi losowymi.

Należy rozróżnić algorytmy, które wykorzystują losowe dane wejściowe, aby zawsze kończyły się poprawną odpowiedzią, ale gdzie oczekiwany czas działania jest skończony (algorytmy Las Vegas , np. Quicksort ), oraz algorytmy, które mają szansę na uzyskanie błędnego wyniku ( algorytmy Monte Carlo , na przykład algorytm Monte Carlo dla problemu MFAS ) lub nie dają rezultatu, sygnalizując awarię lub nie kończąc. W niektórych przypadkach algorytmy probabilistyczne są jedynymi praktycznymi sposobami rozwiązania problemu.

W powszechnej praktyce losowe algorytmy są aproksymowane przy użyciu generatora liczb pseudolosowych zamiast prawdziwego źródła losowych bitów; taka implementacja może odbiegać od oczekiwanego zachowania teoretycznego i gwarancji matematycznych, które mogą zależeć od istnienia idealnego prawdziwego generatora liczb losowych.

Motywacja

Jako motywujący przykład rozważmy problem znalezienia „ a ” w tablicy n elementów .

Dane wejściowe : Tablica n ≥2 elementów, w której połowa to „ a ”, a druga połowa to „ b ”.

Dane wyjściowe : Znajdź „ a ” w tablicy.

Podajemy dwie wersje algorytmu, jeden algorytm Las Vegas i jeden algorytm Monte Carlo .

Algorytm Las Vegas:

  

    
               
        findA_LV  (  tablica  A  ,  n  )  początek  powtórz  Losowo  wybierz  jeden  element  z  n  elementów  .  _  dopóki  „a”  nie  zostanie  znalezione

Ten algorytm działa z prawdopodobieństwem 1. Liczba iteracji jest różna i może być dowolnie duża, ale oczekiwana liczba iteracji to

{\ Displaystyle \ lim _ {n \ do \ infty} \ suma _ {i = 1} ^ {n} {\ Frac {i} {2 ^ {i }}}=2}

Ponieważ jest stały, oczekiwany czas pracy dla wielu wywołań wynosi ${\ Displaystyle \ Theta (1)}$ . (Zobacz notację Big Theta )

Algorytm Monte Carlo:

   

      0
    
               
            
            findA_MC  (  tablica  A  ,  n  ,  k  )  begin  i  :  =  repeat  Wybierz  losowo  jeden  element  z  n  elementów  .  i  :=  i  +  1  , dopóki  i  =  k  lub  „a”  nie  zostanie  znalezione

Jeśli zostanie znalezione „ a ”, algorytm się powiedzie, w przeciwnym razie algorytm zawiedzie. Po k iteracjach prawdopodobieństwo znalezienia „ a ” wynosi:

${\ Displaystyle \ Pr [\ operatorname {znaleźć ~ a}] = 1- (1/2) ^ {k}}$

Ten algorytm nie gwarantuje sukcesu, ale czas działania jest ograniczony. Liczba iteracji jest zawsze mniejsza lub równa k. Przyjmując, że k jest stałe, czas działania (oczekiwany i bezwzględny) wynosi ${\ Displaystyle \ Theta (1)}$ .

Losowe algorytmy są szczególnie przydatne w obliczu złośliwego „przeciwnika” lub atakującego , który celowo próbuje wprowadzić złe dane wejściowe do algorytmu (patrz złożoność najgorszego przypadku i analiza konkurencji (algorytm online) ), na przykład w dylemacie więźnia . Z tego powodu losowość jest wszechobecna w kryptografii . W zastosowaniach kryptograficznych nie można używać liczb pseudolosowych, ponieważ przeciwnik może je przewidzieć, dzięki czemu algorytm jest skutecznie deterministyczny. wymagane jest albo źródło prawdziwie losowych liczb, albo kryptograficznie bezpieczny generator liczb pseudolosowych . Innym obszarem, w którym losowość jest nieodłącznym elementem, są obliczenia kwantowe .

W powyższym przykładzie algorytm Las Vegas zawsze zwraca poprawną odpowiedź, ale czas jego działania jest zmienną losową. Algorytm Monte Carlo (powiązany z metodą Monte Carlo do symulacji) gwarantuje zakończenie w czasie, który może być ograniczony przez funkcję wielkości wejściowej i jej parametru k , ale dopuszcza małe prawdopodobieństwo błędu . Zauważ, że dowolny algorytm Las Vegas można przekształcić w algorytm Monte Carlo (poprzez nierówność Markowa ), wysyłając dowolną, być może błędną odpowiedź, jeśli nie zakończy się w określonym czasie. I odwrotnie, jeśli istnieje wydajna procedura weryfikacji, aby sprawdzić, czy odpowiedź jest poprawna, to algorytm Monte Carlo można przekształcić w algorytm Las Vegas, uruchamiając algorytm Monte Carlo wielokrotnie, aż do uzyskania poprawnej odpowiedzi.

Złożoność obliczeniowa

Teoria złożoności obliczeniowej modeluje losowe algorytmy jako probabilistyczne maszyny Turinga . Rozważane są zarówno algorytmy Las Vegas, jak i Monte Carlo oraz kilka klas złożoności . Najbardziej podstawową losową klasą złożoności jest RP , która jest klasą problemów decyzyjnych dla którego istnieje wydajny (w czasie wielomianowym) losowy algorytm (lub probabilistyczna maszyna Turinga), który rozpoznaje przypadki NIE z absolutną pewnością i rozpoznaje przypadki TAK z prawdopodobieństwem co najmniej 1/2. Klasą uzupełniającą dla RP jest co-RP. , że klasy problemów mające (prawdopodobnie nie kończące się) algorytmy z wielomianowym średnim czasem wykonywania przypadków, których wynik jest zawsze poprawny, są w ZPP .

Klasa problemów, dla których można zidentyfikować zarówno przypadki TAK, jak i NIE z pewnym błędem, nazywa się BPP . Ta klasa działa jako losowy odpowiednik P , tj. BPP reprezentuje klasę wydajnych algorytmów losowych.

Historia

Ważny kierunek badań algorytmów losowych w teorii liczb można prześledzić wstecz do algorytmu Pocklingtona z 1917 r., który znajduje pierwiastki kwadratowe modulo liczb pierwszych. Badanie losowych algorytmów w teorii liczb zostało zainspirowane odkryciem w 1977 r. Roberta M. Solovaya i Volkera Strassena losowego testu pierwszości (tj. określania pierwszości liczby) . Wkrótce potem Michael O. Rabin wykazał, że test pierwszości Millera z 1976 roku można przekształcić w losowy algorytm. W tamtym czasie nie był znany żaden praktyczny algorytm deterministyczny dla pierwszości.

Test pierwszości Millera-Rabina opiera się na relacji binarnej między dwiema dodatnimi liczbami całkowitymi k i n , którą można wyrazić, mówiąc, że k „jest świadkiem złożoności” n . Można to pokazać

Jeśli istnieje dowód na złożoność n , to n jest złożone (tj. n nie jest liczbą pierwszą ) i
Jeśli n jest złożone, to co najmniej trzy czwarte liczb naturalnych mniejszych niż n świadczy o jego złożoności, oraz
Istnieje szybki algorytm, który przy danych k i n sprawdza, czy k świadczy o złożoności n .

Zauważ, że implikuje to, że problem pierwszości występuje w Co- RP .

Jeśli ktoś losowo wybierze 100 liczb mniejszych niż liczba złożona n , to prawdopodobieństwo nie znalezienia takiego „świadka” wynosi (1/4) ¹⁰⁰ , więc w większości praktycznych celów jest to dobry test pierwszości. Jeśli n jest duże, może nie być innego praktycznego testu. Prawdopodobieństwo błędu można zredukować do dowolnego stopnia, przeprowadzając wystarczającą liczbę niezależnych testów.

Dlatego w praktyce nie ma kary związanej z zaakceptowaniem małego prawdopodobieństwa błędu, ponieważ przy odrobinie ostrożności prawdopodobieństwo błędu może być astronomicznie małe. Rzeczywiście, mimo że od tego czasu znaleziono deterministyczny test pierwszości w czasie wielomianowym (patrz test pierwszości AKS ), nie zastąpił on starszych testów probabilistycznych w oprogramowaniu kryptograficznym ani nie oczekuje się, że zrobi to w dającej się przewidzieć przyszłości.

Przykłady

Szybkie sortowanie

Quicksort to znany, powszechnie używany algorytm, w którym losowość może być przydatna. Wiele deterministycznych wersji tego algorytmu wymaga O ( n ² ) do posortowania n liczb dla pewnej dobrze zdefiniowanej klasy zdegenerowanych danych wejściowych (takich jak już posortowana tablica), przy czym specyficzna klasa danych wejściowych generujących to zachowanie jest zdefiniowana przez protokół dla wybór przestawny. Jeśli jednak algorytm wybierze elementy obrotowe w sposób jednolity losowo, ma udowodnione wysokie prawdopodobieństwo zakończenia w O ( n log n ) czas niezależnie od charakterystyki wejścia.

Randomizowane konstrukcje przyrostowe w geometrii

W geometrii obliczeniowej standardową techniką budowania struktury, takiej jak wypukła powłoka lub triangulacja Delaunaya , jest losowe permutowanie punktów wejściowych, a następnie wstawianie ich jeden po drugim do istniejącej struktury. Randomizacja zapewnia, że oczekiwana liczba zmian w strukturze spowodowanych wstawieniem jest niewielka, a więc oczekiwany czas działania algorytmu może być ograniczony z góry. Ta technika jest znana jako losowa konstrukcja przyrostowa.

Minimalne cięcie

Wejście : Wykres G ( V , E )

Dane wyjściowe : Przekrój dzielący wierzchołki na L i R , z minimalną liczbą krawędzi między L i R.

Przypomnijmy, że skrócenie dwóch węzłów, u i v , na (multi-)grafie daje nowy węzeł u ' z krawędziami będącymi sumą krawędzi padających na u lub v , z wyjątkiem dowolnej krawędzi łączącej u i w . Rysunek 1 przedstawia przykład skurczu wierzchołków A i B . Po skróceniu wynikowy wykres może mieć równoległe krawędzie, ale nie zawiera pętli własnych.

Rysunek 2: Udane uruchomienie algorytmu Kargera na grafie z 10 wierzchołkami. Minimalne cięcie ma rozmiar 3 i jest oznaczone kolorami wierzchołków.

Rysunek 1: Skurcz wierzchołków A i B

Podstawowy algorytm Kargera:

         zacznij  i = 1  powtórz  powtórz  Weź losową krawędź (u,v) ∈ E w G zamień u i v na skrócenie u'  aż  pozostaną tylko 2 węzły uzyskaj odpowiedni wynik cięcia C _i i = i + 1  aż  i = m wyjście minimalne przecięcie między C ₁ , C ₂ , ..., C _m .  koniec

W każdym wykonaniu pętli zewnętrznej algorytm powtarza pętlę wewnętrzną, aż pozostaną tylko 2 węzły, uzyskuje się odpowiednie cięcie. $wierzchołków$ wykonania jednego wykonania to a n oznacza Po m -krotnym wykonaniu pętli zewnętrznej wyprowadzamy minimalne cięcie spośród wszystkich wyników. Rysunek 2 przedstawia przykład jednego wykonania algorytmu. Po wykonaniu otrzymujemy cięcie w rozmiarze 3.

Lemat 1 — Niech k będzie minimalnym rozmiarem cięcia i niech $C = {e 1, e 2, ..., e k}$ będzie minimalnym cięciem. Jeżeli podczas iteracji i , żadna krawędź $e \in C nie$ zostanie wybrana do skrócenia, to $C i = C$ .

Dowód

Jeśli G nie jest spójny, to G można podzielić na L i R bez żadnej krawędzi między nimi. Zatem minimalna przerwa w rozłączonym grafie wynosi 0. Załóżmy teraz, że G jest spójny. Niech $V = L \cup R$ będzie podziałem V indukowanym przez $C : C = { {u, v} \in E : u \in L, v \in R}$ (dobrze zdefiniowane, ponieważ G jest połączone). Rozważmy krawędź { u , v } z C . Początkowo u , v są różnymi wierzchołkami. Dopóki wybieramy $.$ , $u$ v $nie$ łączą Zatem na końcu algorytmu mamy dwa węzły złożone obejmujące cały graf, jeden składający się z wierzchołków L , a drugi składający się z wierzchołków R . Jak na rysunku 2, rozmiar minimalnego cięcia wynosi 1, a C = {( A , B )}. Jeśli nie wybierzemy ( A , B ) do skrócenia, możemy uzyskać minimalne cięcie.

Lemat 2 — Jeśli G jest multigrafem z wierzchołkami p i którego min cut ma rozmiar k , to G ma co najmniej pk /2 krawędzi.

Dowód

Ponieważ minimalnym przecięciem jest k , każdy wierzchołek v musi spełniać stopień ( v ) ≥ k . Zatem suma stopni wynosi co najmniej pk . Ale dobrze wiadomo, że suma stopni wierzchołków równa się 2| E |. Następuje następujący lemat.

Analiza algorytmu

Prawdopodobieństwo, że algorytm się powiedzie, wynosi 1 — prawdopodobieństwo, że wszystkie próby zakończą się niepowodzeniem. Przez niezależność prawdopodobieństwo, że wszystkie próby zakończą się niepowodzeniem, wynosi

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

Zgodnie z lematem 1 prawdopodobieństwo, że $C i = C$ jest prawdopodobieństwem, że żadna krawędź C nie została wybrana podczas iteracji i . Rozważmy wewnętrzną pętlę i niech $G j$ oznacza wykres po skurczach krawędzi j , gdzie $j \in {0, 1, \dots, n - 3}$ . $G j$ ma $n - j$ wierzchołków. Korzystamy z reguły łańcuchowej możliwości warunkowych . Prawdopodobieństwo, że krawędź wybrana w iteracji j nie jest w C , biorąc pod uwagę, że żadna krawędź C nie została wcześniej wybrana, wynosi ${\ Displaystyle 1- {\ Frac {k} {| E (G_ {j}) |}}$ } Zauważ, że $ma$ $j nadal$ cięcie o rozmiarze więc zgodnie z Lematem nadal ma co najmniej

Zatem ${\ Displaystyle 1- {\ Frac {k} {| E (G_ {j}) |}} \ geq 1 - {\ Frac {2} nj}}={\frac {nj-2}{nj}}}$ .

Więc zgodnie z regułą łańcucha, prawdopodobieństwo znalezienia minimalnego cięcia C wynosi

{\ Displaystyle \ Pr [C_ {i} = C] \ geq \ lewo ({\ Frac {n-2} {n}} \ prawo) \ lewo ({\ 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).}

Anulowanie daje $\ Displaystyle \ Pr [C_ {i} = C] \ geq {\ Frac {2} {n (n-1)}}}$ . Zatem prawdopodobieństwo, że algorytm się powiedzie, wynosi co najmniej ${\ Displaystyle 1-\ lewo (1- {\ Frac {2} {n (n-1)}} \ dobrze)^{m}}$ . Dla ${\ Displaystyle m = {\ Frac {n (n-1)}} {2}} \ ln n}$ , to jest równoważne ${\ Displaystyle 1- {\ Frac {1 }{n}}}$ . Algorytm znajduje minimalne cięcie z prawdopodobieństwem $n$ czasie $Displaystyle O$ .

Derandomizacja

Losowość można postrzegać jako zasób, podobnie jak przestrzeń i czas. Derandomizacja jest zatem procesem usuwania losowości (lub wykorzystywania jej w jak najmniejszym stopniu). Obecnie nie wiadomo, czy wszystkie algorytmy można zderandomizować bez znacznego wydłużenia czasu ich działania. Na przykład w złożoności obliczeniowej nie wiadomo, czy P = BPP , tj. nie wiemy, czy możemy wziąć dowolny losowy algorytm, który działa w czasie wielomianowym z małym prawdopodobieństwem błędu, i zderandomizować go, aby działał w czasie wielomianowym bez użycia losowości .

Istnieją określone metody, które można zastosować do derandomizacji poszczególnych losowych algorytmów:

metoda prawdopodobieństw warunkowych i jej uogólnienie, estymatory pesymistyczne
teoria rozbieżności (która jest używana do derandomizacji algorytmów geometrycznych)
wykorzystanie ograniczonej niezależności zmiennych losowych używanych przez algorytm, takich jak niezależność parami używana w uniwersalnym mieszaniu
użycie grafów ekspandera (lub ogólnie dyspergatorów ) do wzmocnienia ograniczonej ilości początkowej losowości (to ostatnie podejście jest również określane jako generowanie pseudolosowych bitów z losowego źródła i prowadzi do pokrewnego tematu pseudolosowości)
zmiana randomizowanego algorytmu w celu wykorzystania funkcji skrótu jako źródła losowości dla zadań algorytmu, a następnie derandomizacja algorytmu przez brutalne wymuszenie wszystkich możliwych parametrów (ziarn) funkcji skrótu. Ta technika jest zwykle używana do wyczerpującego przeszukiwania przestrzeni próbki i uczynienia algorytmu deterministycznym (np. algorytmy grafów losowych)

Gdzie losowość pomaga

Kiedy model obliczeń jest ograniczony do maszyn Turinga , obecnie pozostaje otwarte pytanie, czy możliwość dokonywania losowych wyborów pozwala na rozwiązanie niektórych problemów w czasie wielomianowym, których nie można rozwiązać w czasie wielomianowym bez tej zdolności; to jest pytanie, czy P = BPP. Jednak w innych kontekstach istnieją konkretne przykłady problemów, w których randomizacja zapewnia znaczną poprawę.

Opierając się na początkowym przykładzie motywującym: biorąc pod uwagę wykładniczo długi ciąg 2 ^k znaków, pół a i pół b, maszyna o swobodnym dostępie wymaga 2 ^{k -1} wyszukiwań w najgorszym przypadku, aby znaleźć indeks a ; jeśli dozwolone jest dokonywanie losowych wyborów, może rozwiązać ten problem w oczekiwanej wielomianowej liczbie wyszukiwań.
Naturalnym sposobem przeprowadzania obliczeń numerycznych w systemach wbudowanych lub systemach cyberfizycznych jest dostarczenie wyniku zbliżonego z dużym prawdopodobieństwem do wyniku poprawnego (lub prawdopodobnie przybliżonego obliczenia poprawnego (PACC)). Trudny problem związany z oceną utraty rozbieżności między przybliżonym a poprawnym obliczeniem można skutecznie rozwiązać, stosując randomizację
W przypadku złożoności komunikacji równość dwóch łańcuchów można zweryfikować z pewną niezawodnością za pomocą bitów komunikacji ${\ displaystyle \ log n} z losowym protokołem.$ Każdy protokół deterministyczny wymaga $, jeśli$ silnym przeciwnikiem.
Objętość ciała wypukłego można oszacować za pomocą losowego algorytmu z dowolną precyzją w czasie wielomianowym. Bárány i Füredi wykazali, że żaden algorytm deterministyczny nie może zrobić tego samego. Jest to prawdą bezwarunkową, tj. bez polegania na jakichkolwiek założeniach teorii złożoności, przy założeniu, że ciało wypukłe może być badane tylko jako czarna skrzynka.
Bardziej teoretycznym przykładem miejsca, w którym przypadkowość wydaje się być pomocna, jest klasa IP . IP składa się ze wszystkich języków, które mogą być zaakceptowane (z dużym prawdopodobieństwem) przez wielomianowo długą interakcję między wszechpotężnym weryfikatorem a weryfikatorem, który implementuje algorytm BPP. IP = PSPRZESTRZEŃ . Jeśli jednak wymagane jest, aby weryfikator był deterministyczny, to IP = NP .
W sieci reakcji chemicznych (skończony zestaw reakcji, takich jak A+B → 2C + D, działających na skończonej liczbie cząsteczek), możliwość osiągnięcia danego stanu docelowego ze stanu początkowego jest rozstrzygalna, a nawet przybliżona prawdopodobieństwo kiedykolwiek osiągnięcie danego stanu docelowego (przy użyciu standardowego prawdopodobieństwa opartego na stężeniu, dla którego reakcja nastąpi jako następna) jest nierozstrzygalne. Mówiąc dokładniej, ograniczoną maszynę Turinga można symulować z dowolnie wysokim prawdopodobieństwem prawidłowego działania przez cały czas, tylko jeśli używana jest losowa sieć reakcji chemicznych. W przypadku prostej niedeterministycznej sieci reakcji chemicznych (każda możliwa reakcja może zachodzić jako następna) moc obliczeniowa jest ograniczona do prymitywne funkcje rekurencyjne .

Zobacz też

Notatki

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein . Wprowadzenie do algorytmów , wydanie drugie. MIT Press i McGraw-Hill, 1990. ISBN 0-262-03293-7 . Rozdział 5: Analiza probabilistyczna i algorytmy losowe, s. 91–122.
Dirka Draheima. „ Semantyka probabilistycznego typowanego rachunku lambda (semantyka łańcucha Markowa, zachowanie zakończenia i semantyka denotacyjna). ” Springer, 2017.
Jona Kleinberga i Évy Tardos . Projektowanie algorytmów . Rozdział 13: „Algorytmy losowe”.
Fallis, D. (2000). „Niezawodność losowych algorytmów”. The British Journal for the Philosophy of Science . 51 (2): 255–271. doi : 10.1093/bjps/51.2.255 .
M. Mitzenmacher i E. Upfal . Prawdopodobieństwo i obliczenia: algorytmy losowe i analiza probabilistyczna . Cambridge University Press, Nowy Jork (NY), 2005.
Rajeev Motwani i P. Raghavan. Randomizowane algorytmy . Cambridge University Press, Nowy Jork (NY), 1995.
Rajeev Motwani i P. Raghavan. Randomizowane algorytmy . Ankieta dotycząca losowych algorytmów.
Christos Papadimitriou (1993), złożoność obliczeniowa (wyd. 1), Addison Wesley, ISBN 978-0-201-53082-7 Rozdział 11: obliczenia losowe, s. 241–278.
Rabin, Michael O. (1980). „Algorytm probabilistyczny do testowania pierwszości” . Dziennik teorii liczb . 12 : 128–138. doi : 10.1016/0022-314X(80)90084-0 .
AA Tsay, WS Lovejoy, David R. Karger, Losowe pobieranie próbek w problemach związanych z cięciem, przepływem i projektowaniem sieci , Matematyka badań operacyjnych, 24 (2): 383–413, 1999.