Sztuczna inteligencja/SI Moduł 6

Funkcja oceny

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'\in N(s)\quad g(s')\geq 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.

Przykład - 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}\,$	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle N(s_t)\,}	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 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), 0100(7), 0011(14), 0110(15)	0110		0000, 1000, 0010, 0110
4	0001(6), 0100(7), 0011(14)	0011		0000, 1000, 0010, 0110, 0011
5	0001(6), 0100(7)	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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s' \in N(s)} tzn. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s'\,} jest sąsiadem węzła Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s\,} na wspólnej ścieżce, wówczas ich funkcje oceny spełniają warunek Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle g(s') = g(s) + d(s, s')\,} , gdzie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle d(s, s')\,} jest odległością między nimi.

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

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle t\,}	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle A_t\,}	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 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ć funkcja heurystyczna. 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^{*}=\max _{T(s)}g(t)\,$, gdzie $T(s)\,$ jest zbiorem węzłów terminalnych zawartych przez ścieżkę zawierającą $s\,$.

Dość łatwo jest określić idealną funkcję heurystyczną dla każdego węzła $s\,$ powinna być ona równa $h^{*}(s)=g^{*}-g(s)\,$. Jednak znajomość wartości $g^{*}\,$ jest niemożliwa, gdyż wymagałaby przejrzenia wszystkich ścieżek zawierających $s\,$, a to byłoby równoważne wykonaniu pełnego przeszukania przestrzeni. Spróbujmy się zatem zastanowić nad właściwościami funkcji heurystycznej pożądanymi z punktu widzenia określenia, którą ścieżką podążać z węzła $s\,$, tak aby jak najszybciej dotrzeć do węzła końcowego o najlepszej (najwyższej albo najniższej) wartości funkcji oceny.

Założyliśmy na wstępie, że funkcja oceny jest monotoniczna wzdłuż ścieżki. Dla ustalenia uwagi przyjmijmy, że wartości funkcji oceny są niemalejące wzdłuż ścieżki, co oznacza, że dla każdego $s\in S$, dla każdego $s'\in N(s)$ zachodzi $g(s')\geq g(s)$.

Przyjmijmy także, że funkcja oceny jest minimalizowana. Zatem dla dowolnego węzła $s\in S$ zachodzi:

$g^{*}(s)=\min _{s'\in N(s)}g^{*}(s')$

zatem:

$g^{*}(s')\geq g^{*}(s)$

Łatwo sprawdzić, że idealna funkcja heurystyczna $h^{*}(s)\,$ spełnia warunek poprawności:

$h^{*}(s)=h^{*}(s')+g(s')-g(s)\,$

a zatem, ze względu na monotoniczność funkcji oceny, mamy:

$h^{*}(s')\leq h^{*}(s)$

Idealna funkcja heurystyczna jest więc nierosnąca wzdłuż ścieżki prowadzącej do rozwiązania.

Jak wykażemy później, każda funkcja heurystyczna powinna być funkcją monotoniczną – warunkuje to poprawność procesu przeszukiwania przestrzeni. Zachodzi zatem:

$h(s')\leq h(s)$

Załóżmy, że istnieje węzeł, dla którego:

$h(s)\leq h^{*}(s)$

Warunkiem wystarczającym zachowania monotoniczności funkcji heurystycznej jest wówczas gwarancja, że dla każdego węzła $s'\in N(s)$ zachodzi:

$h(t)\leq h^{*}(s')$

Tak więc, aby zagwarantować swoją monotoniczność, funkcja heurystyczna powinna dodatkowo spełniać warunek „nadmiernie optymistycznego szacowania” – jej wartość powinna być (w przypadku minimalizacji) nie większa niż wartość idealnej funkcji heurystycznej.

Strategie poszukiwania wykorzystujące funkcję heurystyczną

Funkcję heurystyczną wprowadza się w celu usprawnienia procesu poszukiwania najlepszego węzła końcowego.

Załóżmy, że dysponujemy idealną funkcją heurystyczną $h^{*}\,$. Oznacza to, że na każdym etapie przeszukiwania w zbiorze węzłów $A_{t}\,$ jesteśmy w stanie odnaleźć te, które prowadzą do optymalnego węzła końcowego. Wystarczy zauważyć, że jeśli obliczymy wartość $g(s)+h^{*}(s)\,$, otrzymamy $g^{*}(s)\,$. Porównując wartości węzłów z $A_{t}\,$, wybierzemy zawsze ten o najmniejszej wartości $g^{*}(s)\,$. W ten sposób dojdziemy do węzła końcowego w dokładnie takiej liczbie kroków, ile jest węzłów na ścieżce łączącej węzeł początkowy i najlepszy końcowy.

Jeśli nasza funkcja heurystyczna nie jest idealna, lecz spełnia warunek monotoniczności i jest dolnym ograniczeniem funkcji $h^{*}\,$, to nadal możemy wykorzystywać wartość sumy $g(s)+h(s)\,$ jako kryterium wyboru węzła z $A_{t}\,$. Nie mamy oczywiście gwarancji tak szybkiego znalezienia węzła optymalnego co przy funkcji heurystycznej $h^{*}\,$, niemniej jednak może to prowadzić do szybszego wyznaczenia rozwiązania niż gdyby posługiwać się wyłącznie funkcją oceny $g\,$. Opisana tu strategia przeszukiwania, posługująca się sumą $g(s)+h(s)\,$ jako kryterium wyboru węzła z $A_{t}\,$, nosi nazwę strategii $A^{*}\,$.

Istnieje wreszcie jeszcze jedna metoda, niejako dualna do strategii równomiernego kosztu: węzły z $A_{t}\,$ będą rozważane w kolejności najmniejszej wartości funkcji heurystycznej $h\,$, z całkowitym pominięciem funkcji oceny $g\,$. Ten sposób postępowania nazywany jest metodą zachłanną.

Powróćmy do przykładu komunikacyjnego i prześledźmy działanie metody zachłannej oraz metody $A^{*}\,$ na tym samym zadaniu.

Załóżmy, że wartości funkcji heurystycznej są podane na poniższym rysunku.

Metoda zachłanna będzie odwiedzać węzły w kolejności podanej w poniższej tabeli.

$t\,$	$A_{t}\,$	$s_{t}\,$	$N(s_{t})\,$	$V_{t}\,$
0	Gd(0)	Gd	Po(Gd,230), Łd(Gd,200), Wa(Gd,260)	Gd(500)
1	Po(Gd,230), Łd(Gd,200), Wa(Gd,260)	Łd	Gd(Łd,500), Po(Łd,230), Wr(Łd,80), Cz(Łd,90)	Gd(500), Łd(Gd,200)
2	Po(Gd,230), Wa(Gd,260), Wr(Łd,80), Cz(Łd,90)	Wr	Po(Wr,230), Łd(Wr,200), Cz(Wr,90), Op(Wr,0)	Gd(500), Łd(Gd,200), Wr(Łd,80)
3	Po(Gd,230), Wa(Gd,260), Cz(Łd,90), Op(Wr,0)	Op	Wr(Op,80), Cz(Op,90)	Gd(500), Łd(Gd,200), Wr(Łd,80), Op(Wr,0)
4	Po(Gd,230), Wa(Gd,260), Cz(Łd,90)	Cz	Wa(Cz,260), Wr(Cz,80), Op(Cz,0)	Gd(500), Łd(Gd,200), Wr(Łd,80), Op(Wr,0), Cz(Łd,90)
5	Po(Gd,230), Wa(Gd,260)	Po	Gd(Po,500), Wa(Po,260), Łd(Po,200), Wr(Po,80)	Gd(500), Łd(Gd,200), Wr(Łd,80), Op(Wr,0), Cz(Łd,90), Po(Gd,230)
6	Wa(Gd,260)	Wa	Gd(Wa,500), Po(Wa,230), Łd(Wa,200), Cz(Wa,90)	Gd(500), Łd(Gd,200), Wr(Łd,80), Op(Wr,0), Cz(Łd,90), Po(Gd,230), Wa(Gd,260)

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

Ze względu na fakt, że wartość funkcji heurystycznej nie zmienia się w kolejnych iteracjach, węzły będą odwiedzane dokładnie jeden raz (gdyż algorytm zauważa, że w zbiorze $V_{t}\,$ jest już węzeł i ma on tę samą wartość funkcji heurystycznej).

Zupełnie inaczej rzecz będzie się miała w przypadku algorytmu $A^{*}\,$, jak przedstawia poniższa tabela.

$t\,$	$A_{t}\,$	$s_{t}\,$	$N(s_{t})\,$	$V_{t}\,$
0	Gd(500)	Gd	Po(Gd,526), Łd(Gd,540), Wa(Gd,599)	Gd(500)
1	Po(Gd,526), Łd(Gd,540), Wa(Gd,599)	Po	Gd(Po,1092), Wa(Po,866), Łd(Po,708), Wr(Po,554)	Gd(500), Po(Gd,526)
2	Łd(Gd,540), Wa(Gd,599), Wr(Po,554)	Łd	Po(Łd,782), Wa(Łd,734), Wr(Łd,624), Cz(Łd,551)	Gd(500), Po(Gd,526), Łd(Gd,540)
3	Wa(Gd,599), Wr(Po,554), Cz(Łd,551)	Cz	Wa(Cz,943), Łd(Cz,782), Wr(Cz,717), Op(Cz,559)	Gd(500), Po(Gd,526), Łd(Gd,540), Cz(Łd,551)
4	Wa(Gd,599), Wr(Po,554), Op(Cz,559)	Op	Cz(Op,747), Wr(Op,725)	Gd(500), Po(Gd,526), Łd(Gd,540), Cz(Łd,551), Op(Cz,559)
5	Wa(Gd,599), Wr(Po,554)	Wr	Po(Wr,882), Łd(Wr,878), Cz(Wr,740), Op(Wr,560)	Gd(500), Po(Gd,526), Łd(Gd,540), Cz (Łd,551), Op(Cz,559), Wr(Po,554)
6	Wa(Gd,599)	Wa	Gd(678), Po(879), Łd(673), Cz(651)	Gd(500), Po(Gd,526), Łd(Gd,540), Cz(Łd,551), Op(Cz,559), Wr(Po,554), Wa(Gd,599)

Rozwiązaniem jest więc ścieżka Gd,Łd,Cz,Op.

Jak mogliśmy się przekonać, w przypadku naszego przykładu, metoda $A^{*}\,$ szybciej wyznaczyła ścieżkę optymalną niż metoda równomiernego kosztu. Ściślej mówiąc, optymalna ścieżka do węzła docelowego jest wyznaczona w mniejszej liczbie iteracji, choć i tak przegląd obejmuje wszystkie węzły.

Na tym tle wyjątkowo źle wypada metoda zachłanna. Ponieważ nie odróżnia ona węzłów, nie znając ich funkcji oceny i posługując się jedynie funkcją heurystyczną, nie jest ona w stanie znaleźć ścieżki optymalnej.

Przykłady funkcji heurystycznych

Właściwa definicja funkcji heurystycznej jest kluczowa z punktu widzenia efektywności przeszukiwania, lecz niestety jest mocno uzależniona od specyfiki rozwiązywanego zadania. Z tego powodu podamy dwa proste przykładów, licząc na wyrobienie właściwej intuicji.

Problem plecakowy

W tym problemie funkcja oceny jest maksymalizowana. W węźle $s\,$ mamy:

$g(s)=\sum _{i}p_{i}x_{i}\,$

Przez $w(s)\,$ oznaczmy wartość pozostałej do zapełnienia nośności plecaka:

$w(s)=W-\sum _{i}w_{i}x_{i}\,$

Przez $R\,$ oznaczmy zbiór przedmiotów nie włączonych do plecaka (identyfikowanych numerami):

$R(s)=\{i|x_{i}=0\}\,$

Odnajdźmy element:

$i^{*}={\mbox{arg max}}_{R(s),w_{i}\leq w(s)}p_{i}/w_{i}$

Łatwo sprawdzić, że taka postać funkcji heurystycznej nigdy nie ma wartości mniejszej niż idealna funkcja heurystyczna $h^{*}\,$, z dwóch powodów. Po pierwsze, współczynniki $p_{i}/w_{i}\,$ dla innych elementów niż $i^{*}\,$ mają mniejszą wartość, a po drugie, pozostała do zapełnienia nośność $w(s)\,$ może nie dać się zapełnić przedmiotami w całości (zostaną „luzy w plecaku”). Przykładem tego drugiego przypadku może być zadanie, w którym wagi plecaka są liczbami parzystymi, a nośność – liczbą nieparzystą.

Piętnastka

Piętnastka jest ulubioną łamigłówką podręczników sztucznej inteligencji. Gra toczy się na kwadratowej planszy zawierającej 16 pól. Piętnaście z nich jest zapełnione liczbami z zakresu 1-15, a jedno jest puste. Jeden ruch gry polega na przesunięciu na miejsce puste jednego z numerów z pól sąsiadujących (patrz rysunek poniżej).

Zadanie przeszukiwania polega na doprowadzeniu planszy do wybranego przez gracza ułożenia, wykonując przy tym jak najmniejszą liczbę ruchów. Funkcją oceny jest więc liczba ruchów, wykonanych od początkowego do bieżącego stanu planszy.

Jako funkcję heurystyczną można przyjąć liczbę pól znajdujących się nie na swoim miejscu. Niewątpliwą zaletą tej funkcji jest łatwa obliczalność, wadą jest jednak równe traktowanie przypadków prostych i trudnych. Przykładowo, plansze jak na rysunku poniżej mają jednakowe wartości funkcji heurystycznej ($h(s_{1})=h(s_{2})=8\,$).

Rozróżnienie między takimi przypadkami zapewnia wykorzystanie innej funkcji heurystycznej, która jest równa sumie odległości między aktualnym i docelowym położeniem każdej liczby. Odległości te są mierzone jako minimalna liczba ruchów, jaką należałoby wykonać, gdyby wszystkie inne pola nie były puste. Dla podanych wyżej plansz wartości tak liczonej funkcji heurystycznej wyniosą odpowiednio: $h(s_{1})=8,h(s_{2})=16\,$.