Sztuczna inteligencja/SI Moduł 7

Złożoność obliczeniowa metod przeszukiwania

Zadanie przeszukiwania rozwiązywaliśmy dotychczas w taki sposób, aby zagwarantować znalezienie maksimum bądź minimum globalnego funkcji. Przestrzeń przeszukiwań, która jest drzewem, była przeszukiwana zgodnie z pewnym porządkiem, przy czym określenie kolejności przeglądanych węzłów było elementem różnicującym odmiany algorytmu przeszukiwania. W efekcie prowadzi to do pełnego przeglądu przestrzeni. W tej lekcji zajmiemy się technikami, które wykorzystują elementy losowości. Prowadzi to do algorytmów przeszukiwania, które nie gwarantują pełnego przeglądu przestrzeni w skończonej liczbie kroków, za to są mniej kosztowne obliczeniowo.

Motywacją wykorzystania elementów losowości w procesie przeszukiwania przestrzeni jest teoria złożoności obliczeniowej. Zajmuje się ona określaniem ilości operacji, potrzebnych do rozwiązania problemu, przy czym ta ilość operacji jest wyrażana jako funkcja ilości danych (parametrów) opisujących problem.

Załóżmy, że problem przeszukiwania, który rozwiązujemy, jest wynikiem rozwiązywania zadania scharakteryzowanego $n$ parametrami (na przykład liczbą przedmiotów, które można spakować do plecaka). Liczba węzłów przestrzeń przeszukiwań, wynikająca z tej liczby parametrów, da się oszacować jako $a{k}^n$, gdzie $k$ jest współczynnikiem rozgałęziania (dla problemu plecakowego równym 2), zaś $a$ jest stałą proporcjonalności. Pełny przegląd przestrzeni wymaga zatem rzędu $k^n$ operacji – mówimy, że złożoność obliczeniowa zadania przeszukiwania wynosi </math>o(k^n)</math>. Z punktu widzenia znajdowania węzła o najlepszej wartości funkcji oceny, oszacowanie powyższe ma pesymistyczny charakter – oznacza, że jeśli dane ułożą się niekorzystnie, metoda przeglądająca przestrzeń w sposób systematyczny natrafi na optymalny węzeł na końcu (co nie znaczy, że dla „korzystnych” danych nie natrafimy na węzeł optymalny nieco wcześniej niż po przejrzeniu wszystkich węzłów).

Zauważmy jednak, że jeśli rozwiązanie problemu wymaga określenia wartości $n$ parametrów, a przejście od jednego do drugiego węzła jest związane z określeniem wartości jednego parametru, wówczas węzeł optymalny od początkowego będzie dzielić $n$ krawędzi. Oznacza to, że gdybyśmy dysponowali „wyrocznią” wiedzącą z góry, na jakie wartości ustalać kolejne parametry, pesymistyczne oszacowanie liczby operacji wystarczających do wyznaczenia węzła optymalnego wynosiłoby $o(n)$. (W teorii złożoności obliczeniowej taki algorytm „z wyrocznią” ma swój odpowiednik w niedeterministycznej maszynie Turinga). Substytutem takiego algorytmu „z wyrocznią” jest algorytm, w którym wyrocznia jest zastąpiona sekwencją losowych decyzji. Siłą rzeczy, losowe decyzje jedynie z pewnym prawdopodobieństwem są zgodne z wyrocznią. Z tego względu należy powtarzać proces losowania aby zwiększyć prawdopodobieństwo, że choć raz uda się tę zgodność uzyskać.

Niniejsza lekcja jest poświęcona właśnie takim algorytmom z elementami losowości.

Algorytm losowego próbkowania

Przegląd metod zaczniemy od algorytmu losowego próbkowania. Algorytm ten tworzy zbiór węzłów $V$ używając poniższego schematu.

Algorytm losowego próbkowania

$V=0$

powtarzaj k razy

generuj losowo $s_k\in D$

$V=V\cup \{s_k\}$

Wraz z kolejnymi iteracjami algorytmu, zbiór odwiedzonych węzłów $V$ będzie coraz większy, a prawdopodobieństwo, że pokryje się on ze zbiorem wszystkich węzłów $D$, wzrasta do jedności.

W przestrzeni $R^n$ jesteśmy w stanie stosunkowo łatwo generować punkty rozkładem jednostajnym w kostce, czyli zbiorze spełniającym warunek: dla każdego i $l_i\le x_i\le h_i$.

Generacja punktu z rozkładem jednostajnym w takiej kostce odbywa się poprzez n-krotną realizację zmiennej losowej o rozkładzie jednostajnym na odcinku (0, 1) (można użyć wbudowanego generatora liczb losowych), co prowadzi do uzyskania zbioru wartości $u_i$. Na podstawie tak uzyskanych liczb losowych wyprowadza się wartości $x_i$ jako $x_i=l_i+u_i(h_i-l_i)$.

W przestrzeniach dyskretnych, w których węzły terminalne są osiągalne poprzez podanie ich numeru (np. przestrzeń wektorów bitowych), generacja węzła terminalnego może być wykonana poprzez losowanie z rozkładem jednostajnym wartości z zakresu 1...N (gdzie N jest liczbą węzłów terminalnych) i odczytanie węzła o wylosowanym numerze.

Pewien kłopot może natomiast sprawić wygenerowanie węzłów terminalnych w przestrzeniach przeszukiwań takich jak rozważane wcześniej przy okazji heurystycznych metod przeszukiwania. Wzmiankowany kłopot wynika z faktu, że dla każdego węzła umiemy jedynie wygenerować jego najbliższych sąsiadów. A zatem wygenerowanie węzła terminalnego musi być wieloetapowe poprzez generowanie kolejnych nieterminalnych węzłów pośrednich, poczynając od węzła $s_0$ według poniższej metody.