Sztuczna Inteligencja



Pobieranie 294,48 Kb.
Strona1/4
Data06.12.2017
Rozmiar294,48 Kb.
  1   2   3   4

Sztuczna Inteligencja
Szukanie heurystyczne II
Algorytm Dijkstry.

Algorytm najkrótszej drogi w grafie, buduje drzewo najkrótszych dróg metodą zachłanną.

Drzewo S składa się tylko z korzenia, S = {Start}

Utwórz wszystkie możliwe węzły na danym etapie. Dla każdego oblicz odległość od celu.

Sortuj węzły według rosnących kosztów. Dodaj do S węzeł o najtańszym koszcie. Powtarzaj 2-5 aż dodanym węzłem będzie Cel

Drzewo szukania rośnie przez dokładanie węzłów. Algorytm gwarantuje znalezienie najkrótszej drogi. Złożoność dla grafu o n wierzchołkach jest rzędu O(n2)


Algorytmy minimalizacyjne

  • Meta-heurystyki na przeszukiwanie globalne całej przestrzeni.

  • Najłatwiej je stosować gdy każdy stan można ocenić niezależnie od drogi dojścia do tego stanu.

  • Mogą być kosztowne ale dla dużych przestrzeni poszukiwań pełne przeszukiwanie jest znacznie bardziej kosztowne.

  • Mogą nie być optymalne ale zwykle znajdują niezłe rozwiązania.
    Oparte są na metodach globalnej minimalizacji funkcji (heurystycznej) f(s), gdzie s to zbiór parametrów.


Algorytm wspinaczki

  • Hill-climbing, czyli wspinaczka – idź w kierunku wzrastającej wartości funkcji heurystycznej.

  • Równoważny szukaniu „najpierw najlepszy”, ale tu zastosowany do optymalizacji parametrów ciągłych, rozwija jedną ścieżkę.

  • Przełamuj impasy (identyczne koszty kilku dróg) w sposób przypadkowy.






  • Algorytm:

    Oceń stan początkowy; jeśli nie jest to cel wykonaj:

    Utwórz nowy stan;
    Jeśli nowy stan jest stanem celu zakończ.
    Jeśli nowy stan jest bliżej stanu celu przyjmij go;
    w przeciwnym przypadku zignoruj go.

    Jeśli nie można utworzyć nowych stanów zatrzymaj się.




Algorytm wspinaczki - wady

  • Lokalne minima.

  • Plateaux, czyli równiny.

  • Wąskie grzbiety.

W niektórych problemach mogą pomóc wielokrotne


starty z przypadkowych punktów.











  1   2   3   4


©operacji.org 2019
wyślij wiadomość

    Strona główna