Przeskocz do treści

Delta mi!

Loading

Jak się pozbyć losowości?

Wojciech Czerwiński

o artykule ...

  • Publikacja w Delcie: kwiecień 2017
  • Publikacja elektroniczna: 30 marca 2017
  • Autor: Wojciech Czerwiński
    Afiliacja: adiunkt, Instytut Informatyki, Uniwersytet Warszawski
  • Wersja do druku [application/pdf]: (80 KB)

W informatyce losowość jest bardzo przydatna. Często bardzo ułatwia rozumowania, pozwala na piękne i klarowne argumenty używające, na przykład, metody probabilistycznej. Nieraz łatwo znaleźć algorytm używający losowości (randomizowany) i działający szybko, podczas gdy znalezienie szybkiego algorytmu deterministycznego jest trudne lub w ogóle takiego nie znamy. Z losowością jest jednak pewien problem...

Chciałoby się wiedzieć coś na pewno, a nie tylko z dużą dozą prawdopodobieństwa. Szczęśliwie okazuje się, że czasami da się tę losowość wprowadzić, a potem wyeliminować. Ta ostatnia operacja, eliminacja losowości, nazywa się derandomizacją.

Przedstawimy dwie metody derandomizacji. Zrobimy to na przykładzie, choć użyte techniki będą zdecydowanie bardziej ogólne. Rozważmy graf =(V,E)G . Dla podzbioru wierzchołków S ⊆V nazwiemy jego cięciem zbiór |{(u,v) ∈E u ∈ S,v /∈ S}, czyli zbiór krawędzi, które mają dokładnie jeden koniec w S. Problem znajdowania S o największym cięciu jest NP-zupełny. Rozważmy jednak podobny problem: znajdowania S takiego, że jego cięcie jest wielkości co najmniej połowy zbioru wszystkich krawędzi, czyli | E /2.

Na pierwszy rzut oka nie jest wcale jasne, czy taki S istnieje. A więc na rozgrzewkę udowodnijmy to. Zachęcamy Czytelników do samodzielnej próby przed przeczytaniem rozwiązania. Rozwiązanie zaś jest zadziwiająco proste. Wylosujmy S, to znaczy każdy wierzchołek wrzućmy niezależnie do |S z prawdopodobieństwem 1/2. Wówczas każda krawędź z |E będzie należała do cięcia S z prawdopodobieństwem 1/2. A zatem średnia wielkość cięcia S to  E /2, czyli na pewno musi istnieć S taki, że jego cięcie ma wielkość przynajmniej  E /2. Powyższy dowód jest jednak niekonstruktywny, nie wynika z niego wcale, jak takie cięcie znaleźć. Oczywiście, możemy przejrzeć wszystkie możliwe zbiory S, ale to zajmie czas rzędu 2n, gdzie  V = n, a my chcemy znaleźć algorytm wielomianowy względem n.

Podamy dwie metody. Pierwsza nazywa się metodą warunkowych wartości oczekiwanych. Przypuśćmy, że przejrzeliśmy już pewien zbiór wierzchołków U i dla każdego z nich zdecydowaliśmy, czy będzie on należał do |S, czy nie. Jaka jest średnia wielkość cięcia S po tym ustaleniu? Przez E(T ,T′) oznaczmy zbiór krawędzi między zbiorami |T i T ′. Na razie wiemy, że do cięcia na pewno będzie należała każda krawędź z E(U , gdzie  ¯ S to dopełnienie zbioru S. Jeśli chodzi o krawędzie jeszcze nieustalone, to każda krawędź z |E(U będzie należała do cięcia z prawdopodobieństwem 1/2. A zatem średnia wartość cięcia po ustaleniu, co się stanie z wierzchołkami z U, wynosi | E(U . Umiemy to obliczyć w czasie wielomianowym, znając U oraz decyzję odnośnie S | na nim, czyli |U oraz |U Teraz już tylko krok do rozwiązania. Gdy bowiem decydujemy o pierwszym wierzchołku, czy wrzucić go do S, czy nie, to obliczamy, jaka będzie średnia wartość cięcia w obu przypadkach. Ponieważ średnia z tych dwóch liczb jest większa lub równa  E /2 (w tym przypadku równa), to jedna z nich też będzie większa lub równa. Wybieramy więc tę lepszą opcję i zabieramy się za drugi element. Przy dorzucaniu każdego nowego elementu wybieramy tę opcję, która daje większą średnią i w ten sposób po podjęciu decyzji dla wszystkich elementów |V otrzymujemy pewien zbiór |S, którego cięcie będzie większe lub równe | E /2.

Drugie rozwiązanie jest jeszcze bardziej zaskakujące. Zauważmy, że tak naprawdę nie potrzebujemy wcale, by każdy wierzchołek z |V był brany do |S niezależnie. Do tego, by każda krawędź (u,v) znalazła się w cięciu |S z prawdopodobieństwem 1/2, wystarczy, by wierzchołki u i v były wzięte do |S niezależnie , czyli wystarczy nam, by wybory były parami niezależne. A to jest dużo słabsze wymaganie! Co więcej, okazuje się, że z |k niezależnych zmiennych losowych 1,...,Xk |X o wartościach w {0,1} można łatwo skonstruować |2k zmiennych losowych parami niezależnych o wartościach w |{0,1}. Po prostu dla każdego podzbioru |A zmienna A X jest zdefiniowana jako xor (alternatywa wykluczająca) zmiennych iX | takich, że |i∈A. Nietrudno zauważyć, że dla dowolnych A, zmienne  |X A i  X | B są niezależne. Dla uproszczenia przyjmijmy, że | V = n jest potęgą dwójki. A więc nasz algorytm możemy zamienić na taki, który losuje najpierw logn bitów iX dla |i∈ {1,...,logn}, a potem gdy podejmuje losową decyzję, czy wrzucić jakiś wierzchołek z V do zbioru |S, korzysta ze zmiennych A.X Taki algorytm też w średnim przypadku skonstruuje cięcie wielkości | E /2. Zauważmy jednak, że zamiast losować te logn wartości możemy po prostu sprawdzić wszystkie możliwości ich wylosowań, których jest |2logn = n. Czyli faktycznie otrzymaliśmy wielomianowy algorytm deterministyczny: przegląda on wszystkie możliwości na 1,...,Xlogn, X dla każdej symuluje działanie losowego algorytmu, a na koniec wybiera najlepsze rozwiązanie.