From WikiZMSI

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.