Sztuczna inteligencja/SI Moduł 6

Funkcja oceny

Wstęp

W poprzednim wykładzie poznaliśmy ogólny schemat przeszukiwania przestrzeni. Przyjrzeliśmy się również dokładniej ślepym strategiom – wszerz i w głąb. Obecnie skoncentrujemy się na przestrzeniach przeszukiwań, mających tę cechę, że istnieje funkcja $g:S\to R$ przyporządkowująca każdemu węzłowi $s\in S$ wartość liczbową, zwaną funkcją oceny. Zadanie przeszukiwania sprowadza się do znalezienia takiego węzła, dla którego funkcja oceny przyjmuje największą (albo najmniejszą) wartość.

Gdy funkcja oceny jest dowolna, wówczas rozwiązanie zadania przeszukiwania musi sprowadzić się do wygenerowania wszystkich węzłów. W takich przypadkach wystarczy posłużyć się dowolnym schematem ślepego przeszukiwania (przy czym wydaje się, że strategia wszerz będzie właściwsza ze względu na unikanie ścieżek nieskończonych).

Pole do popisu dla metod nieco bardziej wyrafinowanych otwiera się wówczas, gdy znajomość funkcji oceny w węźle s pozwala na jej szacowanie w węzłach sąsiadujących. W dalszym ciągu tej lekcji będziemy zakładać, że graf przestrzeni przeszukiwań jest grafem skierowanym oraz że funkcja oceny jest monotoniczna wzdłuż każdej ścieżki grafu przestrzeni przeszukiwań. Monotoniczność wzdłuż ścieżki oznacza, że spełniona jest następująca właściwość: dla każdego $s\in S$ dla każdego $s^{\prime }\in N(s)g(s^{\prime })\ge g(s)$.

Właściwość monotoniczności wzdłuż ścieżki spełnia wiele problemów decyzyjnych, przejawiających tę cechę, że rozwiązanie cząstkowe (tj. takie, gdzie tylko część decyzji została podjęta) jest oszacowaniem dolnym rozwiązania pełnego. Przykładem takiego problemu jest zadanie plecakowe, scharakteryzowane poniżej.

Zadanie plecakowe

Wyobraźmy sobie, że wyjeżdżamy na wakacje i pakujemy plecak. Możemy udźwignąć nie więcej niż W kilogramów. Załóżmy (dość nierealistycznie), że przedmioty, które mamy zabrać ze sobą, są jednakowo ważne, a każdy z nich ma wagę $w_i$ i przynosi nam korzyść $p_i$. Przedmiotów do zabrania jest więcej niż jesteśmy w stanie udźwignąć. Zadanie polega na tym, aby (nie dzieląc przedmiotów) wybrać te, które w sumie ważą nie więcej niż W, a ich zabranie przyniesie największą korzyść.

(W nieco mniej „dydaktycznej” i bardziej realistycznej wersji problem plecakowy to problem włamywacza w sklepie jubilerskim, którego worek ma ograniczony udźwig).

Rozwiązanie zadania plecakowego może być scharakteryzowane za pomocą wektora bitów. Jedynka na pozycji i odpowiada zabraniu przedmiotu, a zero – jego pozostawieniu.

Spróbujmy skonstruować przestrzeń przeszukiwań dla tego zadania z n przedmiotami. Węzeł grafu przestrzeni przeszukiwań to wektor n bitów, spełniający ograniczenie wagowe. Krawędzie łączą każda parę wektorów, które różnią się jednym bitem i są skierowane do wektora o większej liczbie bitów. Punktem startowym jest wektor samych zer.

Przykładowo, do zabrania mogą być 4 przedmioty, o wartościach wagi korzyści podanych w poniższej tablicy:

i	1	2	3	4
$p_i$	10	7	8	6
$w_i$	10	8	2	3

Niech W = 11

Przestrzeń przeszukiwań odpowiadająca temu zadaniu jest przedstawiona na poniższym rysunku.

Strategia napierw najlepszy

Monotoniczność wzdłuż ścieżki można wykorzystać do szacowania funkcji oceny stanów, osiągalnych poprzez sięganie do kolejnych sąsiadów stanu bieżącego. To zaś oznacza, że dysponujemy informacją, która może być użyteczna do sterowanie przeszukiwaniem. Możemy dojść do następującej reguły: jeżeli poszukiwany jest węzeł o najmniejszej (największej) wartości funkcji oceny, z listy węzłów $A_t$ należy wybrać ten, którego wartość funkcji oceny jest najmniejsza (największa). W ten sposób, lista węzłów $A_t$ staje się kolejką priorytetową.

Powyższa reguła prowadzi do strategii przeszukiwania zwanej „najpierw najlepszy”. W zalezności od tego, jaka funkcja pełni rolę rozstrzygającą o wyborze kolejnego węzła do rozwinięcia, mówimy o odmianach strategii najpierw najlepszy: są nimi metoda równomiernego kosztu (zysku), metoda zachłanna oraz metoda A*. Odmiany te będą dyskutowane poniżej.

Odrębnego komentarza wymaga sposób zarządzania zbiorem $A_t$. W przypadku ślepych strategii przeszukiwania, do zbioru $A_t$ dodawane są wszystkie węzły dotychczas nieobecne w $V_t$. W poinformowanych strategiach przeszukiwania, węzeł może mieć różną wartość funkcji oceny w zależności od tego, na której ścieżce się znajduje. Z tego powodu, węzeł s będzie charakteryzowany wartością funkcji oceny oraz węzłem, który poprzedza go na ścieżce. Dodanie węzła do zbioru $A_t$ nastąpi wówczas, gdy węzeł s nie występuje w zbiorze $V_t$, a także wtedy, gdy wartość funkcji oceny węzła s obecnego w $V_t$ jest niższa (w przypadku maksymalizacji funkcji oceny) bądź wyższa (przy jej minimalizacji) od wartości aktualnej węzła.

Przykładowo, niech węzeł s obecny w zbiorze $V_t$ ma wartość funkcji oceny 5, oszacowaną na ścieżce $p_1$. Załóżmy, że na ścieżce $p_2$ ma wartość funkcji oceny 6. Jeśli funkcja oceny jest maksymalizowana, to węzeł s zostanie dodany do zbioru $A_t$ z informacją, że wartość ta jest uzsykana na ścieżce $p_2$. Ponieważ taką samą metodą są traktowane wszystkie węzły, więc do rozróżnienia ścieżki ($p_1$ czy $p_2$) wystarczy zapamiętać węzeł poprzedzający s.

Strategia równomiernego kosztu (zysku)

Prezentację odmian strategii najpierw najlepszy zaczniemy od strategii równomiernego kosztu (przy minimalizacji funkcji oceny) lub maksymalnego zysku (przy jej maksymalizacji).

Zilustrujmy tę strategię na wprowadzonym już wcześniej przykładowym problemie plecakowym.

Ponieważ mamy do czynienia z zadaniem maksymalizacji funkcji oceny, z listy $A_t$ będziemy wybierać zawsze węzeł o najwyższej wartości funkcji oceny. Przegląd przestrzeni przeszukiwań będzie więc wykonywany w kolejności podanej poniżej (w nawiasach obok rozwiązań podane są wartości funkcji oceny).

Nr iteracji	$A_t$	$s_t$	$N(s_t)$	$V_t$
0	0000(0)	0000	0001(6), 0010(8), 0100(7), 1000(10)	0000
1	0001(6), 0010(8), 0100(7), 1000(10)	1000		0000,1000
2	0001(6), 0010(8), 0100(7)	0010	0011(14), 0110(15)	0000, 1000, 0010
3	0001(6), 0010(8), 0011(14), 0110(15)	0110		0000, 1000, 0010, 0110
4	0001(6), 0010(8), 0011(14)	0011		0000, 1000, 0010, 0110, 0011
5	0001(6), 0010(8)	0100	0101(13), 0110(15)	0000, 1000, 0010, 0110, 0011, 0100
6	0001(6), 0101(13)	0101		0000, 1000, 0010, 0110, 0011, 0100, 0101
7	0001(6)	0001	0011(14), 0101(13)	0000, 1000, 0010, 0110, 0011, 0100, 0101, 0001

Funkcję oceny g można traktować jako funkcję kosztu (bądź zysku). Przechodząc od węzła do węzła, zwiększamy koszt (zysk), który osiąga swoje maksimum wzdłuż danej ścieżki po osiągnięciu węzła końcowego (którego zbiór sąsiadów jest pusty).

Innym przykładem jest zagadnienie znajdowania najkrótszej drogi w grafie, na przykład drogi z miasta do miasta (rozwiązanie tego zadania może się okazać potrzebne gdy, spakowawszy plecak, udajemy się w podróż). Tu będziemy wykonywać minimalizację funkcji kosztu.

Niech przykładowym grafem będzie fragment sieci połączeń drogowych między wybranymi miastami Polski. Tabela odległości jest podana poniżej.

	Cz	Gd	Łd	Op	Po	Wa	Wr
Częstochowa	-	-	121	98	-	222	176
Gdańsk	-	-	340	-	296	339	-
Łódź	121	340	-	-	212	134	204
Opole	98	-	-	-	-	-	86
Poznań	-	296	212	-	-	310	178
Warszawa	222	339	134	-	310	-	-
Wrocław	176	-	204	86	178	-	-

Zadanie powyższe można reprezentować w postaci grafu ważonego, którego węzłami są miasta, a krawędziami – połączenia między nimi, przy czym waga krawędzi jest równa długości bezpośredniego połączenia między miastami.

Oznacza to, że funkcja oceny węzła jest zależna od rozwiązywanego zadania. Przykładowo, jeśli droga rozpoczyna się w Warszawie, wówczas wartość funkcji oceny węzeł Częstochowa będzie równą 222, natomiast jeśli droga zaczyna się w Łodzi, wartość ta wyniesie 121. Obowiązywać będzie zasada, że jeśli $s^{\prime }\in N(s)$ tzn. $s^{\prime }$ jest sąsiadem węzła s na wspólnej ścieżce, wówczas ich funkcje oceny spełniają warunek $g(s^{\prime })=g(s)+d(s,s^{\prime })$, gdzie $d(s,s^{\prime })$ jest odległością między nimi.

Załóżmy, że poszukujemy drogi z Gdańska do Opola. Prześledzimy kolejno odwiedzane miasta.

t	$A_t$	$s_t$	$N(s_t)$	$V_t$
0	Gd(0)	Gd	Po(296), Łd(340),Wa(339)	Gd(0)
1	Po(Gd,296), Łd(Gd,340), Wa(Gd339)	Po	Gd(Po,592), Wa(Po,606), Łd(Po,508), Wr(Po,474)	Gd(0), Po(Gd,296)
2	Łd(Gd,340), Wa(Gd,339), Wr(Po,474)	Wa	Gd(Wa,678), Po(Wa,649), Łd(Wa,473), Cz(Wa,561)	Gd(0), Po(Gd,296), Wa(Gd,339)
3	Łd(Gd,340), Wr(Po,474), Cz(Wa,561)	Łd	Gd(Łd,680), Po(Łd,552), Wa(Łd,474), Wr(Łd,504), Cz(Łd,461)	Gd(0), Po(Gd,296), Wa(Gd,339), Łd(Gd,340)
4	Wr(Po,474), Cz(Łd,461)	Cz	Wa(Cz,683), Łd(Cz,582), Wr(Cz,673), Op(Cz,559)	Gd(0), Po(Gd,296), Wa(Gd,339), Łd(Gd,340), Cz(Łd,461)
5	Wr(Po,474), Op(Cz,559)	Wr	Po(Wr,652), Łd(Wr,678), Cz(Wr,650), Op(Wr,560)	Gd(0), Po(Gd,296), Wa(Gd,339), Łd(Gd,340), Cz(Łd,461), Wr(Po,474)
6	Op(Cz,559)	Op	Wr(Op,645), Cz(Op,657)	Gd(0), Po(Gd,296), Wa(Gd,339), Łd(Gd,340), Cz(Łd,461), Wr(Po,474), Op(Cz,559)

Rozwiązaniem jest więc ścieżka Gd,Łd,Cz,Op; gdy podróżuje się wzdłuż tej ścieżki, węzeł Opole ma wartość funkcji oceny 559.

Funkcja heurystyczna

Funkcja oceny węzła bieżącego jest dolnym oszacowaniem funkcji oceny każdego węzła końcowego, który leży na ścieżce zawierającej węzeł bieżący. Jednak ścieżka ścieżce nierówna. W zadaniu plecakowym rozważanym wcześniej, węzeł 0000 (funkcja oceny 0) leżał na ścieżkach prowadzących do węzłów o wartościach funkcji oceny równych 13, 14 i 15. W przykładzie z trasami międzymiastowymi, z węzła Warszawa można było jechać do Wrocławia przez Katowice, Łódź albo Częstochowę, (nie wspominając Poznania i innych miast). Chciałoby się mieć sposób na określenie zawczasu, którą ścieżką podążać, nie czekając, aż stwierdzi się wartość funkcji oceniającej węzła kończącego ścieżkę.

Zadanie to ma spełniać druga funkcja, zwana funkcją heurystyczną. Pełni ona rolę oszacowania wartości funkcji oceniającej. Mówiąc dokładniej, funkcja heurystyczna $h:S\to R$ jest zdefiniowana w taki sposób, że dla węzła s, $g(s)+h(s)$ jest oszacowaniem wartości $g*=ma{x}_T(s)g(t)$, gdzie $T(s)$ jest zbiorem węzłów terminalnych zawartych przez ścieżkę zawierającą s.