274844713

1.2. Przykłady

a więc liczność |A’(6)| zbioru X(b) = {x € {0, l}^m : x^Ta < 6}. Czytelnik domyśla się z pewnością, skąd nazwa problemu. Dokładne obliczenie liczby rozwiązań jest trudne. Można spróbować zastosować prostą metodę Monte Carlo. Jeśli zmienna losowa X ma rozkład jednostajny na przestrzeni {0, l}^m, to P(X € X(b)) = \X{b)\/2^m. Wystarczy zatem oszacować to prawdopodobieństwo tak jak w trzech pierwszych przykładach w tym rozdziale. Generowanie zmiennej losowej o rozkłdzie jednostajnym na przestrzeni {0, l}^m sprowadza się do przeprowadzenia m rzutów monetą i jest dziecinnie proste. Na czym więc polega problem? Otóż szacowane prawdopodobieństwo może być astronomicznie małe. Dla, powiedzmy a — (1,..., 1)^T i b — m/3, to prawdopodobieństwo jest < _e-m/i8 (p_roszę się zastanowić jak uzasadnić tę nierówność). Przeprowadzanie ciągu doświadczeń Bernoulliego z takim prawdopodobieństwem sukcesu jest bardzo nieefektywne - na pierwszy sukces oczekiwać będziemy średnio > e^m/¹⁸, co dla dużych m jest po prostu katastrofalne.

Metoda, którą naszkicuję należy do rodziny algorytmów MCMC (Monte Carlo opartych na łańcuchach Markowa). Algorytm jest raczej skomplikowany, ale o ile mi wiadomo jest najefektywniejszym ze znanych sposobów rozwiązania zadania. Bez straty ogólności możemy przyjąć, że ai < • • • < a_m. Niech bo = 0 oraz bj = min{6, J2j=i ^ai}- Rozważmy ciąg zadań plecakowych ze zmniejszającą się prawą stroną nierówności, równą kolejno b = b_m, 6_m_i,..., b\, &o = 0. Niech więc X(bj) = {x € {0, l}^m : x^Ta < bj}. Zachodzi następujący „wzór teleskopowy”:

\X{b)\ = \X(b_m)\ =

\X(K)\

Will

l*(M

Oczywiście, \X{pą) = 1|, a więc możemy uznać, że zadanie sprowadza się do obhczenia ilorazów \X{bj-i)\/\X(bj)\ (pomijamy w tym miejscu subtelności związane z dokładnością obliczeń). Gdybyśmy umieli efektywnie generować zmienne losowe o rozkładzie jednostajnym na przestrzeni X(bj), to moglibyśmy postępować w dobrze już znany sposób: liczyć „sukcesy” polegające na wpadnięciu w zbiór X(&j_i) C X(bj). Rzecz jasna, możemy losować z rozkładu jednostajnego na kostce {0,1 }^m i eliminować punkty poza zbiorem X(bj), ale w ten sposób wpadlibyśmy w pułapkę, od której właśnie uciekamy: co zrobić jeśli przez sito eliminacji przechodzi jedno na > e^m/¹⁸ losowań?

Opiszemy pewne wyjście, polegające na zastosowaniu błądzenia losowego po zbiorze X(bj). Dla ustalenia uwagi przyjmijmy j = m, czyli bj = b. Losowy ciąg punktów X(0), A(l),..., X(n),. generujemy rekurencyjnie w taki sposób:

Listing.

A(0) := 0; for n = 0 to oo begin

X:=X(n); [ gdzie X = (Xi,..., X_m)

Gen I ~ U{1,..., m}; [ losujemy indeks do zmiany ]

Y := X; Y, = 1 - Xj; if y^Ta< 6 then A(n+1) := F else A(n+1) := X

end

end

Zaczynamy błądzenie w punkcie 0 = (0,...,0)^T. Jeśli w chwili n jesteśmy w punkcie X, to próbujemy przejść do nowego punktu Y, utworzonego przez zmianę jednej, losowo wybranej współrzędnej punktu X (0 zamieniamy na 1 lub z 1 na 0; pozostałe współrzędne zostawiamy bez zmian). Jeśli „proponowany punkt Y nie wypadł” z rozważanej przestrzeni X(b), to przechodzimy do punktu Y. W przeciwnym wypadku stoimy w punkcie X.