Intelligente Agenten und Suchalgorithmen: Best-First und Breitensuche

Intelligenter Agent

Ein intelligenter Agent ist eine Einheit, die ihre Umgebung wahrnimmt, diese Wahrnehmungen verarbeitet und in einer vernünftigen Umgebung reagiert oder eine Handlung ausführt, d.h. korrekt und mit dem Ziel, ein erwartetes Ergebnis zu maximieren. Agenten arbeiten in Umgebungen. Es gibt verschiedene Arten von Umgebungen:

• Erreichbar vs. Unzugänglich: In einer erreichbaren Umgebung können Sensoren alle relevanten Informationen übertragen.
• Deterministisch vs. Nicht-Deterministisch: In einer deterministischen Umgebung kann der nächste Zustand aus dem aktuellen Zustand und den Aktionen des Agenten abgeleitet werden.
• Episodisch vs. Nicht-Episodisch: Episodische Umgebungen sind einfacher, da der Agent nicht vorausschauend denken muss.
• Diskret vs. Kontinuierlich: Eine diskrete Umgebung besteht aus einer Reihe von klar definierten, konkreten Aktionen. Schach ist diskret, da es eine feste Anzahl von möglichen Zügen gibt.
• Statisch vs. Dynamisch: Eine dynamische Umgebung kann sich während der Argumentation des Agenten ändern. Eine statische Umgebung ändert sich nicht im Laufe der Zeit.

Best-First Suche

Wenn der Knoten die beste Schätzung zuerst erhält, wird er erweitert. Anstatt den "besten" Knoten zu erweitern, wird der Knoten erweitert, der nach unserer Bewertungsfunktion am besten erscheint. Dabei werden alle Knoten berücksichtigt, die zum aktuellen Zeitpunkt vorhanden sind. Mit den kumulativen Kosten (Uniform Cost Search) führt die Suche nicht unbedingt zum Ziel. Daher wird eine Schätzung der Kosten vom aktuellen Zustand zum Ziel verwendet (h(n)). Diese Strategie (Minimierung der geschätzten Kosten, um ein Ziel zu erreichen) wird manchmal als "gierige" Strategie bezeichnet. Die Bewertungsfunktion (h) kann beliebig sein, solange h(n) = 0, wenn n ein Ziel ist. Eine "gierige" Strategie ist anfällig für Fehler. Die Zeitkomplexität im schlimmsten Fall ist O(b^m), wobei m die maximale Tiefe des Suchraums ist.

Breitensuche

Ein Graphensuchalgorithmus, der am Wurzelknoten beginnt und alle benachbarten Knoten untersucht. Dann untersucht er für jeden dieser benachbarten Knoten seine unerforschten Nachbarknoten usw., bis er das Ziel findet. Er durchsucht den gesamten Graphen oder eine Sequenz vollständig, ohne Rücksicht auf das Ziel, bis er es findet. Er verwendet keine Heuristik. Im Algorithmus werden alle Kindknoten, die durch die Erweiterung eines Knotens entstehen, in eine FIFO-Warteschlange aufgenommen. In typischen Implementierungen werden Knoten, deren Nachbarn noch nicht untersucht wurden, als "offen" in einem Container (wie einer Warteschlange oder einer verlinkten Liste) abgelegt und später erneut untersucht, wobei sie dann in den Container "geschlossen" verschoben werden.

Algorithmus

1. Den Wurzelknoten in die Warteschlange einfügen.
2. Den Knoten aus der Warteschlange entnehmen und untersuchen.
   • Wenn das gesuchte Element in diesem Knoten gefunden wird, die Suche beenden und ein Ergebnis zurückgeben.
   • Den Pfad in die Warteschlange einfügen, falls es noch nicht untersuchte Nachfolger (direkte Kindknoten) gibt.
3. Wenn die Warteschlange leer ist, wurde jeder Knoten des Graphen untersucht, oder die Suche wird beendet und "nicht gefunden" zurückgegeben.
4. Schritt 2 wiederholen.

Verfahren

• Bei einem Startknoten s untersucht die Breitensuche systematisch die Kanten des Graphen, um alle von s aus erreichbaren Knoten zu "entdecken".
• Berechnung der Entfernung (kleinste Anzahl von Kanten) von s zu allen erreichbaren Knoten.
• Nach der Breitensuche wird ein Baum mit s als Wurzel erzeugt, der alle erreichbaren Knoten enthält.
• Der Pfad von s zu jedem Knoten in diesem Baum enthält die minimale Anzahl von Knoten. Es ist der kürzeste Pfad, gemessen in Anzahl der Knoten.
• Die Breitensuche expandiert die Grenze zwischen entdeckten und unentdeckten Knoten gleichmäßig. Sie erreicht Knoten in einer Entfernung von k erst, nachdem alle Knoten in einer Entfernung von k-1 erreicht wurden.