KI-Suche: Zustände, Graphen und Heuristiken

Lernziele

Suchprobleme als Zustandsraum mit Kosten modellieren. Nach dieser Lektion kannst du das Konzept erklären, ein kleines Beispiel umsetzen und typische Grenzen benennen.

Erklärung

Ein Suchproblem definiert Anfangszustand, Aktionen, Übergangsmodell, Zieltest und optional Pfadkosten. BFS findet bei gleichen Schritt-Kosten einen kürzesten Pfad; DFS spart oft Speicher, garantiert aber keinen kürzesten Weg. A* priorisiert g(n)+h(n); eine zulässige Heuristik überschätzt die Restkosten nicht.

Schrittweises Beispiel

Für ein Raster speichert ein Zustand (x, y). Verfolge besuchte Zustände, damit Zyklen nicht endlos erneut durchsucht werden. Bei variablen Kosten nutze eine Prioritätswarteschlange statt einfacher FIFO-Queue.

from collections import deque
frontier = deque([(0, 0)])
visited = {(0, 0)}
print(frontier.popleft())

Zusammenfassung

Modelliere Zustände sparsam und wähle die Frontier passend zu den Kosten.