Suche (2)

Günther Jena

Beispiele für Suchprobleme

• Lösen des 15-Puzzle oder Zauberwürfels
• Routenplanung
• Spiel-KI für Schach oder Go
• Genomsequenzierung
• Optimierungsprobleme

Terminologie

• Agent
• Zustand (und Initialer Zustand)
• Aktionen
• Übergangsmodel
• Zustandsraum
• Zieltest
• Pfadkosten
• Lösung

Agent

Ein Agent kann seine Umgebung wahrnehmen und in irgendeiner Weise auf diese Umgebung einwirken.

Zustand

Ein Zustand ist eine Konfiguration der Umgebung und des Agenten.

Initialer Zustand

Der Zustand, mit dem ein Agent anfängt zu arbeiten.

Aktionen

Alle Maßnahmen, die ein Agent nutzen kann, um von einem Zustand in einen anderen zu kommen.

Meist sind die möglichen Aktionen abhängig vom aktuellen Zustand.

actions(state: State) -> set[Action]

Übergangsmodel

Liefert uns den nächsten Zustand, abhängig vom aktuellen Zustand und der gewählten Aktion.

result(state: State, action: Action) -> State

Zustandsraum

Die Gesamtheit aller Zustände und der Übergänge dazwischen.

Zieltest

Stellt fest, ob der aktuelle Zustand ein Zielzustand ist.

goal(state: State) -> bool

Pfadkosten

Maßeinheit für die Kosten, die bei einem Pfad über mehrere Zustände entstehen.

Es gibt viele Wege zwischen Wien und Berlin, aber wir suchen den kürzsten oder schnellsten

Suchproblem

• Initialer Zustand
• Aktionen
• Übergangsmodel
• Zieltest
• Pfadkosten

Lösung

Eine Abfolge von Aktionen die vom initialen Zustand zu einem Zustand, welcher den Zieltest besteht, führt.

Optimale Lösung

Die Lösung mit den niedrigsten Pfadkosten

Lösungsansatz

• Start mit einer offenen Liste, die anfangs nur den initialen Zustand beinhaltet
• Wiederhole folgende Punkte
  • Wenn die offene Liste leer ist gibt es keine Lösung
  • Entnehme einen Zustand aus der offenen Liste
  • Wenn der Zustand den Zieltest besteht, habe wir eine Lösung
  • Finde weitere Zustand und füge sie zur offenen Liste