PSI/LS/z2

From WikiZMSI

< PSI | LS

Algorytmy przeszukiwania

Celem laboratorium zapoznanie się z działaniem różnymi algorytmami przeszukiwania przestrzeni stanów.


Co należy wiedzieć zanim...:

  • Przeszukiwanie ma znaleźć ścieżkę wiodącą od stanu początkowego do końcowego (rozwiązania).
    • Aby tego dokonać tworzy się drzewo/graf przeszukiwania rozpoczynający się w punkcie startu i kończący się w rozwiązaniu.
    • Drzewo/Graf składa się z węzłów i krawędzi.
    • Węzły, to stany, a krawędzie to wykonane operatory.
    • Rozwinięcie węzła to proces wykonania wszystkich operatorów na danym węźle. Przez to powstają węzły potomne.
    • Strategie (algorytmy) przeszukiwania różnią się tym, że w różnej kolejności rozwijają węzły w drzewie/grafie.

Narzędzie do wykorzystania na zajęciach

Na zajęciach wykorzystany zostanie aplet AIspace Graph Searching prezentujący działanie różnych algorytmów przeszukiwania rozwiązując różne przykładowe grafy.


Zagadnienia na wejściówkę

  • Jak działają strategie Breadth First Search, Depth First Search, A*.
  • Wady i zalety strategi.
  • Co to jest funkcja heurystyczna.
  • Jaki wpływ na działanie strategii A* mają różne heurystyki.


  1. Z menu Algorithm wybierz kolejno Depth First Search, Breadth First Search oraz A* z heurystykami NUMBER OF TAILS OUT i CITY BLOCK.
  2. Wykonaj zestawienie opisujące:
    1. długość ścieżki do rozwiązania (wartość g)
    2. liczba przeszukanych węzłów (wartość po #)
    3. liczba węzłów w liście OPEN
    4. liczba węzłów w liście CLOSED
    5. wartość początkowa heurystyki
  3. Zapisz wnioski z analizy danych w tabeli.