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: