Strona główna

Szukanie heurystyczne I szukanie heurystyczne


Pobieranie 35.69 Kb.
Data18.06.2016
Rozmiar35.69 Kb.
Sztuczna Inteligencja
Szukanie heurystyczne I
Szukanie heurystyczne

  • Metody szukania heurystycznego

  • Definicja funkcji heurystycznej

  • Najpierw najlepszy
     Przesuwanka
     Szukanie zachłanne
     Szukanie A*

  • Algorytmy iteracyjne
     Wspinaczka
     Monte Carlo
     Symulowane wyżarzanie

  • Klasyfikacja algorytmów szukania
    Szukanie z więzami


Metody szukania heurystycznego

  • Ślepe szukanie nie używa informacji o możliwej strukturze drzewa lub celów; taka informacja może przyczynić się do optymalizacji procesu szukania.

  • Największym problemem w rzeczywistych zastosowaniach jest eksplozja kombinatoryczna liczby możliwych dróg.

  • Szukanie heurystyczne wykorzystuje informacje, które poprawiają efektywność procesu szukania.

  • Używają heurystyk, „reguł kciuka” by określić, która część drzewa decyzji rozwijać najpierw.

  • Heurystyki to reguły lub metody, które prawie zawsze gwarantują podjęcie lepszej decyzji.

  • Np. w sklepie z wieloma kasami dobrą reguła jest:
    stań przy kasie z najkrótszą kolejką. Ale ...

  • (1) jeśli stoi przy niej osobnik z furą zakupów;
    (2) lub nie ma przy niej kasjera;
    (3) lub przyjmują tylko gotówkę a chcesz na kredyt;
    ....
    to nie jest najlepsza decyzja.


Definicja Funkcji Heurystycznej

  • Funkcja h : R, gdzie to zbiór dozwolonych stanów, R to liczby rzeczywiste, odwzorowuje stany s ze zbioru na wartości h(s) służące do oceny względnych kosztów lub zysków rozwijania dalszej drogi przez węzeł odpowiadający s.



Węzeł A ma 3 potomków.
h(s1)=0.8, h(s2)=2.0, h(s3)=1.6
Wartości = koszty utworzenia węzła;

najtaniej jest utworzyć węzeł s1 i ten z punktu widzenia danej heurystyki jest najlepszym kandydatem.







Najpierw najlepszy (BestFS)

  • Kombinacja szukania w głąb (DFS) i szukania wszerz (BFS).

  • DFS znajduje dobre rozwiązania taniej niż BFS,
    BFS nie wpada w zamknięte pętle ani ślepe zaułki.




  • Metoda „najpierw najlepszy (BestFS) pozwala połączyć korzyści z obu metod.

  • Jest kilka wariantów tej metody.


BestFS – przykład






  • Dla przesuwanki użyteczna funkcja heurystyczna mierzy ile kwadratów zajmuje końcowe pozycje.


BFS1: szukanie zachłanne

  • Szukanie zachłanne (Greedy Search, GS) to jedna z najprostszych strategii BestFS.

  • Funkcja heurystyczna h(n) – ocenia pozostałe koszty dotarcia do celu (np. odległość od celu).

  • Szukanie zachłanne: “ocenianych kosztów dotarcia do celu”.

  • Najpierw rozwijany jest węzeł najbliższy.




  • W problemach szukania drogi możliwe są różne metryki:
    (1) Najkrótsza odległość Euklidesowa;
    (2) Odległość Manhattan, poruszanie się tylko po prostych poziomych i pionowych.

  • W innych problemach: oceny podobieństwa.


BestFS1: przykład GS z szukaniem trasy



Odległości od Bukaresztu miast na mapie Rumunii; hSLD(n) = odległości w linii powietrznej do miasta n.



BestFS1: szukanie trasy - graf


Szukanie zachłanne najkrótszej drogi do Bukaresztu.


Wartość funkcji heurystycznej h(n) - tu odległości mierzonej w linii prostej od Bukaresztu - podana jest w węzłach.


  • Znalezione rozwiązanie A S F B nie jest optymalne. Jest o 32 km dłuższe niż optymalna droga A S R P B.

  • Strategia zachłanna próbuje maksymalnie zmniejszyć różnicę redukując koszt dotarcia do celu, bez oceny czy na dłuższa metę jest to optymalne zachowanie.
    Chciwość to jeden z 7 grzechów głównych, ale zwykle się opłaca chociaż nie zawsze jest optymalną strategią.
    GS może źle wystartować i utknąć w ślepej uliczce, np. jadąc z Iasi do Fagaras zacznie od Neamt gdzie droga się kończy.


BestFS1: GS, własności

  • GS przypomina DFS rozwijając tylko jedną ścieżkę, wycofując się, kiedy trafi na ślepy zaułek.

  • GS ma te same problemy co DFS – nie jest to algorytm optymalny ani zupełny.

  • Złożoność GS w najgorszym razie wynosi O(bm), dla m kroków w głąb i średnio b możliwości.

  • Dobra funkcja heurystyczna powinna zredukować znacznie złożoność procesu szukania.

  • Zależy to od konkretnego problemu i od samej funkcji heurystycznej, nie można podać ogólnych ocen.


UCS - stałe koszty

UCS, Uniform Cost Search – szukanie przy stałych kosztach.

Rozwijaj węzły o najniższym koszcie; jeśli koszt przekroczy próg cofnij się i idź inną drogą.

Jeśli koszt wszystkich węzłów jest jednakowy to ó zwykłemu BS.

Przykład: koszty są po lewej stronie.





Programowanie dynamiczne.

  • Zasada „programowania dynamicznego”:

Jeśli najlepsza droga do celu G przechodzi przez pośredni węzeł P to najlepsza droga od startu S do P połączona z najlepszą drogą z P do G daje optymalne rozwiązanie.
Wniosek: szukając najlepszej drogi do celu wystarczy rozpatrywać tylko najkrótszą drogę do P (ale trzeba znać P).

Bardzo przydatna technika.


BestFS2: szukanie A*

  • GS minimalizuje koszty dojścia do celu h(n), nie jest to jednak algorytm zupełny ani optymalny.

  • Alternatywą jest minimalizacja g(n) kosztów dojścia do danego węzła – jest to metoda kompletna, optymalna, ale mało efektywna.

  • Metoda A* łączy obydwie funkcje heurystyczne, h(n) oraz g(n) w jednej funkcji heurystycznej oceniającej koszty najtańszego rozwiązania przechodzącego przez węzeł n, tzn. f(n) = g(n) + h(n).

BestFS2: algorytm A*

  • Rozpocznij od węzła początkowego i twórz nowe węzły {n} dopóki cel nie zostanie osiągnięty;

  • Posortuj nowe węzły {n} korzystając z funkcji
    f (n)= g(n) + h(n);

  • Odrzuć ścieżki zapętlone.
    Wybierz najlepszy węzeł n'

  • Zostaw tylko najtańszą ścieżkę do n'.
    Jeśli n' jest celem skończ;

  • Jeśli nie, rozwijaj dalsze węzły {n}, łącznie z n'





Własności:



  • Ponieważ wybierana jest najtańsza droga do danego węzła n żadna inna droga nie może obniżyć całkowitego kosztu (monotoniczność).

  • h(n) powinno być wiarygodną oceną kosztów dojścia do celu – zaniżenie wszystkich koszów nie przeszkadza.
    Algorytm A* jest w tym przypadku optymalny.

Ćwiczenie: udowodnić optymalność A*



Dlaczego A* jest optymalne?

o - optymalna droga z A do Z.

a i b - ścieżki z A do Z rozgałęziające się w węźle C.
Niech ścieżka a będzie częścią drogi optymalnej o a ścieżka b nie.

L(C,Z) - zaniżone koszty dojścia z C do Z.

Załóżmy, że A* wybierze ścieżkę b, czyli koszty będą


||A - C||a+L(C,Z) > ||A - C||b +L(C,Z)

Niech D będzie miastem poprzedzającym Z na drodze b;


wtedy L(D,Z)b = ||D - Z||b, czyli ||A - D||b+ L(D,Z)b= ||A - Z||b

Ale ||A - Z||b > ||A - Z||o bo b nie jest optymalne.

||A - C||a+ L(C,Z) £ ||A - Z||o bo a należy do o a L(C,Z) £ ||C-Z||o

||A - C||a+ L(C,Z) < ||A - D||b + L(D,Z)b= ||A - Z||b

więc A* zawsze wybierze a.

IDA*, czyli A* iteracyjnie pogłębiane.

Podobny do IDDF



  • Stosuj algorytm szukania w głąb.

  • Oceniaj całkowite koszty f (n)= g(n) + h(n) heurystyką A*.

  • Jeśli f (n) > T cofaj się; T jest tu zmiennym progiem.

  • Jeśli nie znaleziono rozwiązania zwiększ T i powtarzaj.

Wady: powtarza część ścieżek, ale i tak końcowe szukanie zajmuje najwięcej czasu.

Zalety: niewielka pamięć, jak DS, tylko szybsze.
Heurystyki dla 8-ki


  • Algorytmy szukania heurystycznego testuje się często na problemie przesuwanki.

  • Dla 8-ki jest 9!/2 or 181.440 możliwych stanów, dla 15-ki 653 mld.

  • W procesie szukania dobra funkcja heurystyczna zmniejsza liczbę rozpatrywanych stanów < 50.

  • Dwie funkcje, które nigdy nie przeceniają kosztów:
    1. h1 = liczba płytek na złych pozycjach – każdą trzeba przesunąć przynajmniej raz.
    2. h2 = suma odległości od celu, metryka Manhattan; każdy ruch zmniejsza odległość o 1; tu h1=8, h2 = 18


Przykład A* dla 8-ki

P


rzestrzeń stanów utworzona w czasie heurystycznego
szukania 8-ki.
f(n) = g(n) + h(n)
g(n) = odległość od startu
do stanu n.
h(n) = liczba elementów na złym
miejscu.

Przykłady pytań



  • Co to jest funkcja heurystyczna

  • Podaj metody szukania heurystycznego

  • Co to jest metoda zachłanna

  • Co to jest programowanie dynamiczne








©snauka.pl 2016
wyślij wiadomość