Elementy Sztucznej Inteligencji (Wykład 2)
Drzewo przeszukiwania grafu
Lista OPEN – lista węzłów do przeanalizowania
Lista CLOSED – lista odwiedzonych węzłów, które nie są rozwiązaniami problemu
Szkielet klasycznego algorytmu
OPEN = {pusta}
CLOSED = {pusta}
1. Umieszczamy w OPEN węzeł początkowy
2. Wyjmujemy z listy OPEN węzeł W
3. Sprawdzamy czy jest on rozwiązaniem problemu. Jeśli tak to kończymy algorytm
4. Umieszczamy W na liście CLOSED, a jego potomków dodajemy do listy OPEN
5. Przechodzimy do punktu 2.
Lista OPEN (Dodawanie i zdejmowanie węzłów)
Dodajemy i zdejmujemy z początku
W = A
OPEN = {B, C, D}
CLOSED = {A}
W = B
OPEN = {E, F, C, D} CLOSED = {A, B}
Powyższy algorytm opiera się o przeszukiwanie wgłąb
Można go zaimplementować rekurencyjnie
You created this PDF from an application that is not licensed to print to novaPDF printer (
http://www.novapdf.com
)
Odmianą tego algorytmu jest:
Przeszukiwanie wgłąb z iteracyjnym pogłębianiem (do pewnej głębokości / pewnego poziomu)
Jeśli nie znajdziemy rozwiązania to zwiększamy głębokość
Istnieje też przeszukiwanie wszerz (dodajemy węzły na koniec)
OPEN = {
B
,
C
,
D
, E, F, G, H} CLOSED = {A, ... }
W metodach sztucznej inteligencji interesują nas algorytmy heurystyczne. W nich znajduje się funkcja oceniająca
(szacująca) jak blisko jesteśmy rozwiązania
Przykład na podstawie puzzli
Prawidłowe ustawienie elementów
1
2
3
8
0
4
7
6
5
Pomieszane ustawienie elementów
1
2
3
8
4
5
0
7
6
0 – puste pole
Chcemy znaleźć ciąg operacji doprowadzający do rozwiązania.
Trzeba sprawdzić, które klocki są na złych miejscach i jak daleko są od swoich miejsc (ile trzeba wykonać ruchów aby
umieścić je na właściwym miejscu).
Jeśli funkcja heurystyczna zakłada, że możemy ustawiać klocek na klocku to:
1 – dobre miejsce
2 – dobre miejsce
3 – dobre miejsce
4 – złe miejsce (potrzebny 1 ruch)
5 – złe miejsce (potrzebny 1 ruch)
6 – złe miejsce (potrzebny 1 ruch)
7 – złe miejsce (potrzebny 1 ruch)
You created this PDF from an application that is not licensed to print to novaPDF printer (
http://www.novapdf.com
)
1 + 1 + 1 + 1 = 4 – wartość funkcji heurystycznej zakładającej, że możemy ustawiać klocek na klocku
Inna funkcja heurystyczna może zakładać, że klocki są wyjmowane i wkładane na właściwe miejsce
Na podstawie funkcji heurystycznych konstruujemy graf
Istnieją różne algorytmy heurystyczne, np. „Hill Climbing”
Jest to algorytm naiwny, w którym generujemy potomków i jak znajdziemy lepszego potomka to do niego przechodzimy.
Przykładowo jesteśmy w górach i wchodzimy na szczyt krok po kroku. Generując następnego potomka (nasz następny krok)
sprawdzamy o ile jesteśmy wyżej i wybieramy tego potomka, który wygenerował najwyższą liczbę. Kontynuujemy algorytm.
Niestety „Hill Climbing” nie gwarantuje nam sukcesu, ponieważ możemy „wejść w ślepy zaułek” którym jest jakiś pagórek,
który nie generuje potomka dzięki któremu znajdziemy się wyżej w kolejnym kroku.
Algorytm „Best First Search”
Ma cechy przeszukiwania wszerze z funkcją heurystyczną
Lista OPEN jest kolejką priorytetową. Wyjmujemy węzeł o najwyższym priorytecie. W przypadku puzzli, im mniejsza wartość
funkcji heurystycznej, tym wyższy priorytet.
OPEN = {A(5)}
CLOSED = {pusta}
OPEN = {B(3),
C(2),
D(4)}
CLOSED = {A}
OPEN = {
B(3),
D(4), G(5), H(6)}
CLOSED = {A, C}
OPEN = {D(4), G(5), H(6), E(2),
F(1)
}
CLOSED = {A, C, B}
Algorytm A*
Funkcja heurystyczna h*(w) = f(w) + g*(w)
* - wartość przybliżona
f(w) – ilość kroków (połączeń węzłów). Przykładowo w powyższym rysunku od A do C ilość kroków jest równa 1, a od A do F
ilość króków jest równa 2. Jest to też nazywane kosztem dotarcia do węzła w
g*(w) – stara funkcja heurystyczna, czyli jak daleko węzeł w znajduje się od rozwiązania. Jeśli jest równa 0 to znaleźliśmy
rozwiązanie.
You created this PDF from an application that is not licensed to print to novaPDF printer (
http://www.novapdf.com
)
Można ograniczyć ilość używanej pamięci do listy OPEN poprzez ograniczenie wielkości listy analizowanych węzłów, ale to
nie gwarantuje znalezienia rozwiązania
W grach też występują algorytmy przeszukiwania
Algorytm MINIMAX
MINI – ruchy przeciwnika
MAX – nasze ruchy
Wartości w nawiasach oznaczają liczbowo ile mamy pionków na planszy (Szachy)
Na podstawie powyższego grafu możemy wyczytać, ze dla nas najlepszym wyjściem jest pójście w kierunku C.
Wyjaśnienie: Jeśli pójdziemy w kierunku B (zostanie nam 5 pionków) to przeciwnik pójdzie w kierunku F (zostaną nam 3
pionki). Jeśli pójdziemy w kierunku D (zostanie nam 10 pionków) to przeciwnik pójdzie w kierunku I (zostaną nam 2 pionki).
Najlepszy wyjście jest pójście w kierunku C, bo po ruchu przeciwnika zostanie nam 5 (G) pionków.
W tym algorytmie analizujemy drzewo do któregoś poziomu i aktualizujemy wartości w górę.
You created this PDF from an application that is not licensed to print to novaPDF printer (
http://www.novapdf.com
)
Algorytm NEGAMAX (?)
Funkcja heurystyczna STATIC (Gracz, Plansza) zwraca wartości <-N, N>
STATIC(Gracz, Plansza) = - STATIC(Przeciwnik(Gracz), Plansza)
MOVEGEN (Gracz, Plansza) – zwraca listę plansz
MINIMAX (Gracz, Poziom, Plansza) – zwraca strukturę S, która składa się z dwóch części
VALUE (S) – wartość (oblicza wartość planszy, w której byśmy się znaleźli)
PATH (S) – ścieżka czyli lista plansz optymalnych
MINIMAX (Gracz, Poziom, Plansza)
1. If(KONIEC (POZIOM) ) return (VALUE: STATIC (Gracz, Plansza), PATH = {pusta})
2. POTOMKOWIE = MOVEGEN(Gracz, Plansza) //lista plansz, do których moglibyśmy się udać
3. If (POTOMKOWIE == {pusta}) return (VALUE: STATIC (Gracz, Plansza), PATH = {pusta})
4. /* trzeba wyszukać potomka o wartości MAX */
BEST_VALUE = -N
BEST_PATH = {pusta}
//dla każdego P z listy POTOMKOWIE policzymy sobie
a. M = MINIMAX (Ptrzeciwnik(Gracz), Poziom + 1, P)
b. If (VALUE (M) >= BEST_VALUE)
{
BEST_VALUE = VALUE (M)
BEST_PATH = {P, PATH (M)}
//dodajemy P na początek, a na koniec to co zwróciła lista MINIMAX
}
5. Return (VALUE: - BEST_VALUE, PATH: BEST_PATH)
You created this PDF from an application that is not licensed to print to novaPDF printer (
http://www.novapdf.com
)