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 2019
wyślij wiadomość

    Strona główna
Komunikat prasowy
przedmiotu zamówienia
najkorzystniejszej oferty
Informacja prasowa
wyborze najkorzystniejszej
warunków zamówienia
istotnych warunków
sprawie powołania
Regulamin konkursu
udzielenie zamówienia
przetargu nieograniczonego
zamówienia publicznego
Nazwa przedmiotu
Specyfikacja istotnych
modułu kształcenia
Rozporządzenie komisji
studia stacjonarne
wyborze oferty
Zapytanie ofertowe
Szkolny zestaw
Ochrony rodowiska
ramach projektu
prasowy posiedzenie
trybie przetargu
obwodowych komisji
zagospodarowania przestrzennego
komisji wyborczych
komisji wyborczej
Program konferencji
Wymagania edukacyjne
Lista kandydatów
szkoły podstawowej
która odbyła
Województwa ląskiego
Decyzja komisji
przedmiotu modułu
poszczególne oceny
Sylabus przedmiotu
szkół podstawowych
semestr letni
Postanowienia ogólne
przedsi biorców
produktu leczniczego
Karta przedmiotu
Scenariusz lekcji
Lista uczestników
Program nauczania
Projekt współfinansowany
Informacje ogólne
biblioteka wojewódzka
semestr zimowy