Sztuczna inteligencja/SI Moduł 6

From Studia Informatyczne

Spis treści

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') \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.

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.

Grafika:SI M6 01.png

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), 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 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' \in N(s) tzn. s'\, jest sąsiadem węzła s\, na wspólnej ścieżce, wówczas ich funkcje oceny spełniają warunek g(s') = g(s) + d(s, s')\,, gdzie 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.

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ć 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') \ge 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') \ge 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') \le 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') \le h(s)

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

h(s) \le 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) \le 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.

Grafika:SI M6 02.png

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 \le 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).

Grafika:SI M6 r3.png

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\,).

Grafika:SI M6 r4.png

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\,.