Zaawansowane algorytmy i struktury danych/Wykład 15

Abstrakt

W wykładzie tym zajmiemy się przedstawieniem głównych motywacji stojących za algorytmami randomizowanymi. Po krótkim wstępie przestawimy podstawowe pomysły używane w algorytmach randomizowanych. Na zakończenie tego wykładu zaprezentujemy dwa algorytmy randomizowane. Jednym z nich będzie algorytm rozwiązujący problem maksymalnego przekroju w grafie, a drugim algorytm aproksymacyjny szukający najdłuższej ścieżki w grafie.

Motywacja

Prostota: Jest to pierwszy i najważniejszy powód używania algorytmów randomizowanych. Istnieje wiele przykładów, w których efektywność prostego algorytmu randomizowanego może równać się (a nawet przerosnąć) efektywność algorytmu deterministycznego.

Przykład: Algorytmy sortujące. Istnieje wiele deterministycznych algorytmów sortujących działających w asymptotycznym czasie $O(n\log n)$, np. algorytm Merge-Sort. W praktyce bardzo często stosowanym algorytmem jest algorytm Quick-sort, który ma tylko oczekiwany czas działania $O(n\log n)$. Jednakże algorytm ten jest bardzo prosty do implementacji i działa zazwyczaj szybciej niż bardziej złożone algorytmy deterministyczne.

Szybkość: Dla niektórych problemów znane algorytmy randomizowane są dużo szybsze od tych deterministycznych. Może tak być, ponieważ dla algorytmów randomizowanych żądamy często tylko aby poprawna odpowiedź była zwrócona z dużym prawdopodobieństwem, bądź aby działały one w oczekiwanym czasie wielomianowym. To oznacza, że w niektórych przypadkach algorytm randomizowany może w ogóle nie znaleźć poprawnej odpowiedzi lub może ją znaleźć, ale po bardzo długim czasie.

Przykład: Sprawdzanie czy wielomian wielu zmiennych jest zerowy. Nie ma żadnego znanego algorytmu deterministycznego działającego w czasie wielomianowym, który by określał czy dany wielomian wielu zmiennych jest zerowy. Jednakże istnieje bardzo prosty i efektywny algorytm randomizowany rozwiązujący ten problem poprzez wyliczenie wartości danego wielomianu w losowym punkcie. Należy zaznaczyć, że taki algorytm jest bardzo przydatny, gdy taki wielomian jest przedstawiony nie wprost i możemy tylko wyznaczać jego wartość.

Algorytmy online. Algorytmy online są algorytmami, które podejmują decyzje na podstawie częściowej wiedzy na temat danych wejściowych, na przykład gdy przyszłe dane wejściowe nie są znane. W takiej sytuacji losowość jest użyteczna, ponieważ pozwala na uniezależnienie się od nieznanego ciągu danych, który może być dobrany w sposób pesymistyczny.

Złożoność komunikacji. W tym przypadku randomizacja też jest przydatna.

Przykład: Rozważmy grę z dwoma graczami: Ula i Piotr. Każdy z nich ma ciąg $n$-bitów i chcą je porównać, aby sprawdzić czy są one takie same. Jednakże, za każdy wysłany bit muszą zapłacić. Najlepszy algorytm deterministyczny dla tego problemu wymaga wysłania $n$ bitów. Zasadniczo to jest równoważne wysłaniu przez Ulę całego ciągu do Piotra. Z drugiej poprzez użycie randomizacji wymagana komunikacja może być zredukowana, jednak przy osłabieniu wymagań, a mianowicie możemy tylko żądać, aby protokół się powiódł z wysokim prawdopodobieństwem. W tym celu Ula i Piotr muszą posiadać ten sam ciąg $n$ losowych bitów, a ciągi są porównane poprzez porównanie jednobitowej wartości iloczynu skalarnego ciągu z tym ciągiem losowym.

Ważne pomysły

Zanim przedyskutujemy główne pomysły stosowane w algorytmach randomizowanych, trzeba zaznaczyć, że algorytmy randomizowane to nie to samo, co analiza probabilistyczna. W analizie probabilistycznej, (deterministyczne) algorytmy są analizowane przy założeniu losowych danych wejściowych, na przykład przy sortowaniu można zanalizować deterministyczny quick-sort (ze stałym punktem podziału) danych wejściowych, który jest losową permutacją $n$ elementów. Z drugiej strony, algorytmy randomizowane stosują przy działaniu losowy rzut monetą, co jest równoznaczne z wyborem algorytmu deterministycznego z talii algorytmów. Ponadto, algorytmy randomizowane dają gwarancję także w przypadku pesymistycznych danych wejściowych.

Liniowość wartości oczekiwanej. Podstawową właściwością zmiennych losowych, która znajduje zastosowanie w algorytmach randomizowanych, jest wykorzystanie liniowości wartości oczekiwanych. Niech $X$ i $Y$ będą zmiennymi losowymi. Zachodzi wtedy następująca równość:

${ℰ}[X+Y]={ℰ}[X]+{ℰ}[Y].$

Ważne tutaj jest, że ta równość nie wymaga niezależności pomiędzy $X$ i $Y$. Pozwala to nam uprościć obliczenia, które w przeciwnym wypadku mogłyby być dość skomplikowane. Następujący przykład dobrze to demonstruje.

Ćwiczenie

Przypuśćmy, że jest $26$ uczniów w klasie i nauczyciel ma ciastka, na których są litery alfabetu (każde ciastko ma inną literkę). Przypuśćmy, z nauczyciel rozdaje po jednym ciastku każdemu uczniowi. Jaka jest oczekiwana liczba uczniów, którzy dostaną ciastko z literą, która jest pierwszą literą ich imienia?

Aby odpowiedzieć na to pytanie, rozważmy losowe zmienne: $X_1,X_2,\dots ,X_{26}$, gdzie dla każdego $i$, $1\le i\le 26$ definiujemy

$X_i=\{\begin{array}{ll}1& \text{jeżeli }i\text{'ta osoba otrzyma właściwą literę,}\\ 0& \text{w przeciwnym przypadku.}\end{array}$

Ponieważ ciastka były losowo rozdzielone, prawdopodobieństwo tego, że $n$'ta osoba dostanie prawidłową literkę wynosi $\frac{1}{26}$. Dlatego mamy ${ℰ}[X_i]=\frac{1}{26}$ dla wszystkich $i$.

Ostatecznie, oczekiwana liczba osób z właściwą literką na ich ciastku wynosi:

${ℰ}[X_1+X_2+\dots +X_{26}]=\sum _{i=1}^{26}{ℰ}[X_i]=1$

Należy przy tym zaznaczyć, że nie poczyniliśmy żadnych założeń odnośnie pierwszej litery imion uczniów.

Liniowość wariancji. Jeżeli zmienne losowe są od siebie niezależne, to ich wariancja też jest liniowa. Dla $n$ niezależnych zmiennych losowych $X_1,X_2,\dots ,X_n$ mamy:

$Var(\sum _{i=1}^n{X}_i)=\frac{\sum _{i=1}^{n}Var(X_i)}{n^2}.$

Własność ta znajduje zastosowanie w połączeniu z nierównością Czebyszewa bądź Czernoffa, gdy chcemy obniżyć prawdopodobieństwo błędu, bądź wielkość tego błędu. Możemy wtedy pobierać losową próbę, tzn. pobrać małą próbę z dużego zbioru danych wejściowych. Zadany problem można rozwiązać na tej małej próbie, po czym uzyskanym wynikiem można posłużyć się dla problemu właściwego. Problem min-cut posiada algorytmy randomizowane, które korzystają z tej techniki. Także wyznaczenie liczby wartościowań spełniających formułę boolowską może być wykonane w ten sposób (zobacz Zadanie 2).

Ćwiczenie

Mamy daną populację $n$ osób, których wzrost nie przekracza $3m$. Jak przybliżyć średni wzrost w populacji, tak aby wynik z prawdopodobieństwem $\frac{3}{4}$ był różny od średniej o $10cm$?

Wybierzmy próbkę $k$ osób, niech $X_i$ dla $1\le i\le k$ oznacza zmienną losową będącą wzrostem wybranej osoby. Zauważmy, że niezależnie od rozkładu wysokości w populacji, mamy:

${\sigma }^2=Var(X_i)\le 9m^2$.

Policzmy średnią wzrostu populacji na podstawie próbki $k=225$ osób. Wtedy pierwiastek wariancji wyniku wynosić będzie

${\sigma }_k=\frac{\sigma }{\sqrt{k}}=\frac{3m}{\sqrt{225}}=\frac{3m}{15}=\frac{1}{5}m$,

wtedy z nierówności Czebyszewa dostajemy:

$\mathrm{Pr}(|{ℰ}[X_k]-\mu |<\frac{1}{2}\sigma )<\frac{1}{4}$

czyli

$\mathrm{Pr}(|{ℰ}[X_k]-\mu |<\frac{1}{10}m)<\frac{1}{4}$

Zauważ, że w celu przybliżenia średniej musieliśmy zbadać tylko stałą liczbę członków populacji.

Duża liczba świadków. Kolejny powód, dla którego algorytmy randomizowane są efektywne w znajdowaniu rozwiązania to taki, że często problem posiada dużo świadków na "tak" lub na "nie", na przykład przy sprawdzaniu, czy wielomian wielu zmiennych jest zerowy. Kiedy dany wielomian jest rzeczywiście zerowy, to wartość wielomianu w każdym punkcie wynosi zero. Natomiast gdy wielomian nie jest zerowy, wtedy istnieje duża liczba punktów, w których wielomian przyjmuje niezerową wartość (zobacz Zadanie 1). Dlatego znalezienie jednego świadka spośród wielu jest może być łatwo zrealizowane poprzez wybranie małej losowej próby.

Balansowanie obciążenia. Randomizacja jest bardzo dobrą metodą na rozłożenie obciążenia. Dla przykładu rozważmy sytuację w której mamy $n$ serwerów i $n$ zadań. Jeżeli każde z $n$ zadań zostanie przydzielone do jednego serwera w sposób losowy, wtedy z dużym prawdopodobieństwem żadna z maszyn nie otrzymuje więcej niż $\log n$ zadań. Możemy delikatnie poprawić tą prostą randomizowaną strategię: dla każdego zadania wybieramy losowo dwa serwery i przydzielamy to zadanie serwerowi o mniejszym obciążeniu. Można pokazać, że ten zmodyfikowany schemat z dużym prawdopodobieństwem nie przydzieli więcej niż $\log \log n$ zadań dla każdego serwera. W ten sposób, w przypadku miliona zadań, każdy serwer otrzyma co najwyżej pięć zadań. Stwierdzenie z dużym prawdopodobieństwem oznacza, że jakaś własność zajdzie z prawdopodobieństwem większym niż $\frac{1}{2}$.

Kolejny przykład na balansowanie obciążenia można odnaleźć w algorytmach dla tablicach hashujących.

Łamanie symetrii. W obliczeniach równoległych i rozproszonych ważne jest, aby złamać symetrię między procesorami. Na przykład w sieci Ethernet, kiedy dwie maszyny wysyłają pakiet danych w tym samym czasie, następuje kolizja. Nie wiadomo, który procesor powinien spróbować ponownie przesłać pakiet. Gdy uczynią to obydwa, znów nastąpi kolizja. Najprostszym sposobem na uniknięcie tej sytuacji jest złamanie symetrii poprzez randomizację, np. każdy procesor rzuca monetą i próbuje ponownie wysłać pakiet, gdy wypadła mu reszka. Kolejnym przykładem jest problem znalezienia doskonałego skojarzenia w grafie na maszynie równoległej. Ważne jest, aby wszystkie procesory obliczały to samo skojarzenie, jednak nie wiadomo które, bo jeszcze go nie znaleźliśmy. Tutaj można posłużyć się randomizacją w celu złamania symetrii pomiędzy różnymi możliwymi skojarzeniami i odizolowaniem pojedynczego skojarzenia.

Derandomizacja. Niektóre proste algorytmy randomizowane mogą być przerobione na (nie takie proste) algorytmy deterministyczne poprzez derandomizację. Często w ten sposób dostaje się najefektywniejsze algorytmy deterministyczne.

Problem maksymalnego przekroju

W problemie maksymalnego przekroju dany jest graf $G=(V,E)$, a wynikiem jest podzieł zbioru wierzchołków na dwa podzbiory $(A,B)$. Krawędź jest rozcięta wtedy, gdy jej końce leżą po dwóch różnych stronach podziału. Istotą problemu jest znalezienie takiego podziału, który maksymalizuje liczbę krawędzi rozciętych. Problem ten jest NP-trudny. Używając randomizacji, skonstruujemy prosty $\frac{1}{2}$–aproksymacyjny algorytm dla tego problemu.

Niech $|V|=n$ i $|E|=m$.

Twierdzenie 1

Istnieje podział $(A,V-A)$ zbioru wierzchołków taki, że:

$\text{liczba krawędzi w zbiorze }>\frac{|E|}{2}=\frac{m}{2}$

Dowód

Budujemy zbiór $A$ (to znaczy jedną stronę podziału) włączając każdy wierzchołek do $A$ z prawdopodobieństwem $\frac{1}{2}$. Zadajmy teraz pytanie: jaka jest oczekiwana liczba rozciętych krawędzi dla podziału $(A,V-A)$? Aby odpowiedzieć na to pytanie, dla każdej krawędzi $(i,j)\in E$, zdefiniujmy

$X_{i,j}=\{\begin{array}{ll}1& \text{jeżeli krawędź }(i,j)\text{ jest rozcięta},\\ 0& \text{w przeciwnym przypadku}.\end{array}$

Możemy teraz napisać, że liczba rozciętych krawędzi wynosi:

$\text{Liczba rozciętych krawędzi }=X=\sum _{(i,j)\in E}{X}_{i,j}.$

Nasze pytanie sprowadza się teraz do wyznaczenia wartości ${ℰ}[X]$. Posłużymy się liniowością wartości oczekiwanych. Po pierwsze zauważmy, że ${ℰ}[X_{i,j}]=\frac{1}{2}$. Jest tak, ponieważ niezależnie od tego, czy $i$ jest w zbiorze $A$ czy nie, jest dokładnie jeden wybór dla $j$, który rozetnie krawędź $(i,j)$. Stąd otrzymujemy:

${ℰ}[X]=\sum _{(i,j)\in E}{ℰ}[X_{i,j}]=\sum _{(i,j)\in E}\frac{1}{2}=\frac{m}{2}.$

Aby zakończyć dowód, zaobserwujmy, że musi istnieć podział dla którego liczba rozciętych krawędzi jest równa co najmniej średniej, czyli $\frac{m}{2}$.

Twierdzenie to zobrazowane jest na następującej animacji.

Plik:Zasd ilustr s.svg

Zauważamy, że liczba rozciętych krawędzi w najlepszym podziale nie może przekraczać $m$. Powyższy algorytm daje nam przecięcie wielkości $\frac{m}{2}$. Stąd oczekiwana aproksymacja wyniku to $\frac{1}{2}$.

Uwaga

Istnieje prosty sposób na derandomizację powyższego algorytmu poprzez zastosowanie metody zachłannej. Włączamy pierwszy wierzchołek do $A$, a następnie analizujemy pozostałe wierzchołki, jeden za drugim. Włączamy do $A$ wierzchołek wtedy i tylko wtedy, kiedy po włączeniu wierzchołka rozciętych jest więcej krawędzi niż w przypadku uprzednio rozpatrywanych wierzchołków.

Problem długiej ścieżki

W problemie znalezienia długiej ścieżki dany mamy graf $G=(V,E)$ i liczbę całkowitą $k$. Problem ten polega na znalezieniu prostej ścieżki o długości $k$ w grafie $G$. Zauważmy, że dla $k=n-1$ problem ten jest równoznaczny ze znalezieniem ścieżki Hamiltona w grafie $G$. Pokażemy teraz algorytm, który działa w czasie wielomianowym dla $k=O(\frac{\log n}{\log \log n})$. Zadanie 3 polega na poprawieniu tego algorytmu tak, aby działał w czasie wielomianowym dla $k=O(\log n)$.

Główny pomysł to wykożystanie tego, że dla skierowanego acyklicznego grafu (DAG-u) istnieje algorytm działający w czasie wielomianowym znajdujący najdłuższą ścieżkę.

Ćwiczenie

Korzystając z programowania dynamicznego, podaj algorytm znajdujący najdłuższą ścieżkę w DAGu, który działa w czasie $O(|E|)$?

Zacznijmy od znalezienia porządku topologicznego $t_1,\dots ,t_n$ w zadanym DAGu $G=(V,E)$. Zauważmy, że ścieżki w $G$ mogą iść tylko zgodnie z tym porządkiem. Umożliwia nam to wyznaczenie długości najdłuższej ścieżki dynamicznie, tzn., długość najdłuższej ścieżki kończącej się w danym wierzchołku jest równa długości najdłuższej ścieżki kończącej się w jednym z jego poprzedników plus $1$.

Przypuśćmy, że przypisujemy wierzchołkom grafu $G$ wartości ze zbioru $\{1,2,\dots ,n\}$ losowo tak, że każda permutacja jest tak samo prawdopodobna. Ponadto, skierowujemy wszystkie krawędzie z grafu od mniejszych wartości do większych. W ten sposób otrzymujemy graf DAG, który oznaczamy przez $\overrightarrow{G}$.

Twierdzenie 2

Jeśli $G$ zawiera ścieżkę $P$ o długości $k$, to wtedy $P$ będzie skierowaną ścieżką w $\overrightarrow{G}$ z prawdopodobieństwem $\alpha =\frac{2}{(k+1)!}$

Dowód

Najpierw dla przykładu rozważmy ścieżkę nieskierowaną, przechodzącą przez wierzchołki $a,b,c,d$ w $G$ o długości $3$. Będzie to skierowana ścieżka w $\overrightarrow{G}$ wtedy i tylko wtedy, gdy albo $a<b<c<d$, albo $a>b>c>d$ w naszym przypisaniu. Generalnie, ścieżka $P$ długości $k$ będzie skierowaną ścieżką w $\overrightarrow{G}$ wtedy i tylko wtedy, kiedy $k+1$ wierzchołków na ścieżce $P$ będzie miało przypisane wartości w sposób albo ściśle rosnący, albo ściśle malejący. Ze względu na to, że wszystkie permutacje $k+1$ wierzchołków są jednakowo prawdopodobne i tylko dwie z nich dają ścieżkę skierowaną w $\overrightarrow{G}$, to wynika z tego, że $P$ będzie ścieżką skierowaną w $\overrightarrow{G}$ z prawdopodobieństwem $\alpha =\frac{2}{(k+1)!}$.

Wniosek 3

Jeżeli graf $G$ zawiera ścieżkę $P$ o długości $k$, to wtedy $\overrightarrow{G}$ zawierać będzie skierowaną ścieżką o długości $k$ z prawdopodobieństwem co najmniej $\alpha$.

Wniosek ten możemy wykorzystać do konstrukcji następującego algorytmu.

Algorytm znajduje w grafie ścieżkę długości $k$

---

 ZNAJDŹ-ŚCIEŻKĘ$(G,k)$
1  for $i=1$ to $\lceil \frac{1}{\alpha }\rceil$ do
2  begin
3    przypisz losową permutację $\{1,\dots ,n\}$ wierzchołkom $G$
4    używając tej permutacji skonstruuj $\overrightarrow{G}$
5    if udało się znaleźć w $\overrightarrow{G}$ ścieżkę długości $k$ then
6      return TRUE
7  end
8  return FALSE

Działanie tego algorytmu zobrazowane jest na następującej animacji.

Plik:Zasd ilustr t.svg

Twierdzenie 4

Powyższy algorytm znajduje ścieżkę o długości Parser nie mógł rozpoznać (błąd składni): {\displaystyle k = O(\frac{\log n}{\log \log n}})} , jeżeli taka istnieje, w randomizowanym czasie wielomianowym.

Dowód

Załóżmy, że istnieje ścieżka o długości $k$ w grafie $G$. Chcemy obliczyć prawdopodobieństwo tego, że nie znajdziemy ścieżki o długości $k$ w $\overrightarrow{G}$ we wszystkich $t$ próbach. Prawdopodobieństwo to jest takie samo jak prawdopodobieństwo, że $\overrightarrow{G}$ nie posiada skierowanej ścieżki o długości $k$ we wszystkich $t$ próbach.

$\mathrm{Pr}[\text{porażki we wszystkich }t\text{ próbach}]\le (1-\alpha {)}^t\le e^{-\alpha t}\le \frac{1}{e}.$

Pierwsza nierówność zachodzi, ponieważ w każdej próbie graf $\overrightarrow{G}$ nie posiada skierowanej ścieżki o długości $k$ z prawdopodobieństwem co najwyżej $(1-\alpha )$ (zgodnie z Wnioskiem 3), przy czym każda z prób jest niezależna. Druga nierówność jest konsekwencją tego, że $1+x\le e^x$, dla wszystkich $x$. Dlatego też algorytm znajdzie ścieżkę o długości $k$ (jeżeli taka istnieje) z prawdopodobieństwem co najmniej $1-\frac{1}{e}$. Czas działania algorytmu wynosi $t\times O(|E|)=\frac{(k+1)!}{2}\times O(|E|)$. Zauważ, że $(k+1)!\le (k+1{)}^k$, czyli po wstawieniu $k=\frac{c\log n}{\log \log n}$ otrzymujemy czas $O(m{n}^c)$, który jest wielomianowy dla każdej stałej $c$.