Home

wfms

Impressum

Bilderkennung

Polymere

Medieninformatik

Pictures

Problemlösen durch Suchen oder Optimieren

Kapitel 2 - Problemlösen durch Suchen

Welche fünf Typen gehören zur Datenstruktur "Knoten eines Suchbaums"?

Der Zustand des Zustandsraums, dem v entspricht
Der Knoten der v erzeugt hat, also der Vater von v
Der zur Erzeugung von v verwendete Operator bzw. Aktion
Die Zahl der Knoten von der Wurzel zu v, was der Tiefe entspricht
Die Pfadkosten des Pfades vom Anfangszustand bis zu dem v entsprechendem Zustand

Was ist der Rand bei der Suche und welche Operationen muß dieser besitzen?

Zusätzlich zum Suchbaum wird eine Datenstruktur benötigt, um zwar schon erzeugte, aber noch nicht expandierte Knoten zu speichern. Diese Menge heißt Rand und wird als Liste implementiert und hat folgende Operationen:

Make-List - Erzeugt eine Liste aus gegebenen Elementen
Emtpy - prüft ob Liste leer ist
Remove-Front - entfernt erste Element aus Liste
Listing-FN - fügt eine Menge von Elementen in die Liste ein. Für das Einfügen gibt es verschiedene Möglichkeiten, welche auch die verschiedenen Varianten von Suchalgorithmen darstellen

Wie schaut der allgemeine Suchalgorithmus aus?

Function Allgemeine Suche(Problem,Listing-FN) return Solution or Error;
	Nodes = Make-List (Make-Node(Initial-State[Problem]));
	Loop do
		If (Empty(nodes)) return Error;
		Node = Remove-Front(nodes);
		If (State(node)== Zielprädikat[problem]) return node;
		Nodes=Listing-FN(nodes,Expand(node,Operators[Problem]))
End

Nennen sie alle blinden Suchverfahren?

Breitensuche
Kostengesteuerte Breitensuche
Tiefensuche
Tiefenbegrenzte Suche
Suche mit iterativen Vertiefen
Bidirektionale Suche

Welche Eigenschaften hat die Breitensuche?

Realisiert wird BFS über die allgemeine Suche mit einer Listenfunktion mit Tail-Insert. BFS ist vollständig, denn sie findet immer die Lösung, falls diese existiert. Außerdem findet BFS immer die Lösung mit dem kürzesten Pfad. Falls die Pfadkosten eine monoton wachsende Funktion der Tiefe des Suchbaums ist, dann ist BFS sogar optimal. Bei einem Verzweigungsfaktor von b und einer Tiefe von d liegt der Zeit- und Speicheraufwand von BFS bei O(b^d).

Optimalität:	ja
Vollständigkeit:	ja
Zeitaufwand :	O(b^m)
Speicherplatzbedarf:	O(b^m)

Welche Eigenschaften hat die Kostengesteuerte Breitensuche?

Es wird immer der Knoten als nächster aus dem Rand expandiert, der die geringsten Pfadkosten besitzt. Unter Bestimmten Voraussetzungen wird so eine kostengünstige Lösung gefunden. Die kostengesteuerte BFS findet die kostengünstigste Lösung, wenn sich die Kosten entlang eines Pfades an keiner Stelle verringern.

Optimalität:	ja
Vollständigkeit:	ja
Zeitaufwand :	O(b^m)
Speicherplatzbedarf:	O(b^m)

Welche Eigenschaften hat die Tiefensuche?

Allgemeine Suche mit Listenfunktion mit Head-Insert
Expandiert immer den Knoten auf der tiefstmöglichen Ebene
Speicherplatzaufwand ist linear b*m (m ist größte im Suchbaum vorliegende Tiefe)
Zeitbedarf ist O(bm), da im worst case alle Knoten expandiert werden müssen
Nachteil der Tiefensuche ist, dass sie in unendlichen Zweigen "hängen bleibt"
Deshalb ist auch nicht garantiert, dass die Tiefensuche eine optimale Lösung findet
Tiefensuche ist weder vollständig noch optimal

Optimalität:	nein
Vollständigkeit:	nein
Zeitaufwand :	O(b^m) (worst Case)
Speicherplatzbedarf:	*O(bm)**

Welche Eigenschaften hat die tiefenbegrenzte Suche?

Es wird die allgemeine Suche mit Operatoren, welche Tiefe kontrollieren implementiert. Zeitbedarf ist dann O(bl), wenn l die begrenzte Tiefe darstellt

Optimalität:	nein
Vollständigkeit:	nein
Zeitaufwand :	O(b^l)
Speicherplatzbedarf:	O(b*l)

Welche Eigenschaften hat die Suche mit iterativem Vertiefen?

Dies stellt eine tiefenbegrenzte Suche dar, welche iterativ mehrere Tiefenschnitte anwendet, um zu einem Ergebnis zu kommen.

Dieses Verfahren vereinigt die Vorteile der Breitensuche mit der der Tiefensuche
Sie ist vollständig und optimal
Die Suche mit iterativem Vertiefen ist das beste blinde Suchverfahren, da es auch auf große Suchbäume mit unbekannter Tiefe anwendbar ist.

Optimalität:	ja
Vollständigkeit:	ja
Zeitaufwand :	O(b^d)
Speicherplatzbedarf:	O(b*d)

Welche Eigenschaften hat die bidirektionale Suche?

Bei diesem Verfahren wird simultan vom Ausgangszustand vorwärts und vom Zielzustand rückwärts gesucht, bis sich die beiden Suchpfade in der Mitte treffen. Mit einem Verzweigungsfaktor b und einer Lösungstiefe d ist O(2b^d/2)=O(b^d/2). Folgende Voraussetzungen müssen gegeben sein:

Vorgänger eines Knotens muss erzeugbar sein
Alle Operatoren müssen umkehrbar sein, denn dann sind die Mengen der Vorgänger mit der der Nachfolger identisch
Falls es mehrere Zielknoten gibt, muss diese Suche als Mehrzustandsproblem durchführbar sein. Dies ist möglich, wenn die Zielzustände explizit gegeben sind. Sind nur Zielprädikate gegeben, so wird die Definition von Zuständen schwierig.
Es muss schnell prüfbar sein, ob ein Knoten schon in einem anderen Teil der Suche vorkommt
Es muss entscheidbar sein, welche Art der Suche in beiden Richtungen ablaufen soll.

Optimalität:	ja
Vollständigkeit:	ja
Zeitaufwand :	O(b^(d/2))
Speicherplatzbedarf:	O(b^(d/2))

Was bedeutet "informiert" im Gegensatz zu blinden Suchverfahren?

Bei blinden Suchverfahren kann nicht Einfluss auf die Knotenwahl genommen werden. Informiert bedeutet, dass man dies z.B. mit heuristiken beeinflussen kann.

Was sind heuristische Suchfunktionen?

Heuristische Suchalgorithmen versuchen den Suchpfad durch "Schätzen" zu optimieren und somit die Laufzeit zu verbessern. Es wird nun eine Evaluierungsfunktion benötigt, welche die richtige Reihenfolge für die Abarbeitung bestimmt. Die Knoten werden so geordnet, daß der mit der besten Bewertung als Erster expandiert wird. Eine Heuristik ist somit eine spezielle Form einer Evaluations-Funktion

Was ist unter Best-First-Search zu verstehen?

Es wird der Knoten zuerst expandiert, welcher wahrscheinlich am schnellsten zum Ziel führt. Eine von Problem zu Problem verschiedene Evaluations-Funktion hilft hier bei der Entscheidungsfindung. Diese Evaluierungsfunktion kann auch falsch liegen. Wichig ist, dass die Suchzeit im Ganzen sich aber verkürzt. Implementiert wird die Best-First-Suche wie die Breiten- und Tiefensuche auch mittels einer Queue. Nur werden hier vor jeder Expansion die Knoten anhand der Werte der Evaluations-Funktion sortiert. Beispielalgorithmen sind zum BSP Greedy, A*-Search und SMA*...

Welche heuristischen Suchfunktionen gibt es?

Greedy Suche
A*-Suche
Speicherbegrenzte Suche
A*-Suche mit iterativen Vertiefen - IDA*
Simply Memory-Bounded A* - SMA*

Wie funktioniert die Greedy Suche?

Der Knoten, welcher dem Zielzustandsknoten als am "Naheliegendsten" eingeschätzt wird, wird als Erster expandiert. Eine Funktion, welche solche Kosten schätzt, nennt man Heuristikfunktion. Eine heuristische Funktion h(n) stellt also die Kosten des billigsten Pfades von einem Knoten n zum Zielzustand dar. Jede beliebige Funktion kann als Heuristik verwendet werden. Es muss nur gelten h(n) = 0, falls n ein Zielknoten ist.
Die Greedy-Suche arbeitet nach dem Tiefensuchmuster und ist somit auch nicht optimal und nicht vollständig. Der Worst-Case Zeitbedarf ist O(bm), mit m als maximale Tiefe des Suchraumes.

Optimalität:	nein
Vollständigkeit:	nein
Zeitaufwand :	O(b^m) (worst Case)
Speicherplatzbedarf:	O(b*m)

Wie funktioniert die A*-Suche?

Durch Addition der heuristischen Funktion h und der Pfadkostenfunktion g erhält man die Funktion f(n) = g(n) + h(n). Dabei sind g(n) alle bisherigen Kosten und h(n) die aktuellen Kosten. Die A*-Suche arbeitet im Grunde wie Greedy. Es wird nur g(n) hinzuaddiert.
Hat die Funktion h die Eigenschaft, dass die Kosten eines Pfades bis zu einem Zielknoten nicht überschätzt werden, dann ist es eine zulässige Heuristik. Die Best-First-Suche unter Verwendung von f als Evaluierungsfunktion mit zulässigem h heißt A*-Suche. Eine heuristische Funktion, deren Werte entlang des Pfades niemals kleiner werden, nennt man monoton. Ist eine heuristische Funktion nicht monoton, dann kann sie durch die Pfadmaximierungsgleichung (Maximum bilden) in eine Monotone umgeformt werden.

Die A*-Suche ist optimal und vollständig, aber im Worst-Case exponentiell, da sie der Breitensuche ähnelt.

Optimalität:	ja
Vollständigkeit:	ja
Zeitaufwand :	O(b^m) (worst Case)
Speicherplatzbedarf:	O(b*m)

Wie funktioniert die speicherbegrenzte A-Suche mit iterativen Vertiefen - IDA

Arbeitet wie Suche mit iterativen Vertiefen, nur dass die Suche nicht strikt tiefenorientiert ist, sondern kostenorieniert.
IDA* ist optimal und vollständig und benötigt nur Speicherplatz, der proportional zum längsten Pfad, der untersucht wird, ist. Somit ist Speicherplatzaufwand linear.

Optimalität:	ja
Vollständigkeit:	ja
Zeitaufwand :	O(b^m) (worst Case)
Speicherplatzbedarf:	O(b*m)

Wie funktioniert die speicherbegrenzte Simply Memory-Bounded A* - SMA*

Der SMA* merkt sich Knoten, welche er schon mal expandiert hat. Somit wird Sucheffizienz erhöht. SMA* hat folgende Eigenschaften:

Benutzt allen verfügbaren Speicher
Vermeidet Zustandswiederholungen, soweit Speicher es erlaubt
Ist vollständig, wenn Speicher ausreicht, um kürzesten Suchpfad zu speichern
Ist optimal, wenn Speicher ausreicht, um kürzesten optimalen Lösungspfad zu speichern. Andernfalls liefert er die beste Lösung, die mit dem verfügbaren Speicher möglich ist.
Er ist optimal effizient, wenn der Speicher für den gesamten Suchbaum ausreicht.

Soll ein Knoten expandiert werden und es ist kein Speicher mehr frei, so wird ein Knoten aus der Liste entfernt. Solche entfernten Knoten heißen vergessene Knoten. Bevorzugt werden solche Knoten entfernt, welche keine gute Lösung versprechen, d.h. hohe f-Kosten haben. Im Vorgängerknoten eines entfernten Teilbaums werden aber Informationen über die Qualität des besten Pfades in dem entfernten Teilbaum abgelegt, um dadurch einen solchen Teilbaum im Falle des Falles wieder rekonstruieren zu können.

Problemlösen durch Optimieren

Wodurch definiert sich das Problemlösen durch Optimieren?

Der Unterschied zur Suche ist, daß bei Suche der Anfangszustand gegeben ist und die Lösung gesucht wird. Beim Optimieren ist die Lösung schon im Anfangszustand gegeben und es wird versucht eine bessere Lösung zu ermitteln.

Zielzustände werden über Zielfunktionen bewertet
Durch das Optimieren wird versucht einen besseren Zielzustand zu finden
Speichern immer nur einen Zustand

Welche drei Ansätze gibt es beim Optimieren?

Bergsteigen
Simuliertes Ausglühen
Genetische Algorithmen

Wie funktioniert das "Bergsteigen" als Optimierung?

Das Bergsteigen ist ein stures Suchen von besseren Werten. Gibt es mehrere bessere Knoten, muß via Zufallsfunktion einer selektiert werden.

Welche drei Probleme treten beim "Bergsteigen" auf?

Lokales Maximum

Stößt die Suche auf ein lokales Maximum, bleibt sie dort hängen und findet ein evtuelles globales Maximum nicht.

Plateau

Einmal auf einer Ebene sitzend, kann der Algorithmus nur raten, in welche Richtung fortgesetzt werden soll.

Grat

Man benötigt Operatoren, welche verhindern, daß die Suche entlang eines Grates hin und her pendelt.

Um diese Problemen aus dem Weg zu gehen, kann man die Suche durch Bergsteigen mehrfach von verschiedenen zufällig gewählten Startpunkten aus durchführen und die besten Werte nehmen.

Was ist simuliertes Ausglühen?

Die Idee ist, während der Suche in zufälligen Abständen Knoten mit schlechteren Werten auszuwählen, um auf diese Weise lokalen Maxima zu entgehen. Eine Variable T beschreibt im Algorithmus eine Art Temperatur (die die Wahrscheinlichkeit von Abwärtsschritten steuert)

T wird bei jeder Iteration inkrementiert
Anfangs ist T relativ hoch und es besteht somit eine hohe Wahrscheinlichkeit des Abwärtsgehens
Mit richtigen Parametern findet das Ausglühen also das globale Maximum
Ist vollständig und optimal, wenn ein entsprechend langer Zeitraum für das Ausglühen gegeben ist

Wie arbeiten genetische Algorithmen?

Dieser Ansatz ist aus der Evolutionstheorie abgeschaut. Man nimmt an das die Evolution immer optimale Pfade wählt und somit optimale Wesen hervorbringt.
Genetische Algorithmen laufen auf Populationen von Genomen (Folge von Genen = Bitstrings) ab. Sie erzeugen in großen Schleife neue Generationen von Genomen durch Anwendung der drei Operatoren Selektion, Kreuzung und Mutation. Dabei werden folgende Schritte durchgeführt:

Definiere die Genome und eine Fitneßfunktion (Überlebensfunktion davon abhängig) und erzeuge eine initiale Population von Genomen
Modifiziere die aktuelle Population durch Anwendung der drei Operatoren
Wiederhole den letzten Schritt solange, bis sich die Fitness nicht mehr erhöht

Ziel des Algorithmus ist, die Fitness der Genome zu maximieren. Die Fitnessfunktion (kann beliebig sein) bewertet jedes neu entstandene Genom. Dazu muss Genom in seinen ursprünglichen Phänotyp (Erscheinungsbild eines Genotyps) umgewandelt werden, denn auf ihm operiert die Fitnessfunktion. Nachteile von genetischen Algorithmen sind die schlechte Effizienz und die Notwendigkeit einer anspruchsvollen Fitnessfunktion. Beliebtes Anwendungsgebiet sind die neuronalen Netze, wo es vor allem auf die Fitnessfunktion ankommt.

Welche drei Operationen müssen genetische Algorithmen ausführen können?

Selektion

Ist das Aussondern von bestimmten Genomen zum Konstanthalten der Population.

Kreuzung

Führt das Auswählen der fittesten Genome und Verkettung bzw. Kombination dieser dar.

Mutation

Verändert ein oder mehrere zufällig gewählte Gene eines Genoms, wodurch ein neues Genom entsteht, um vor allem eventuellen lokalen Maxima entgehen zu können.

Kapitel 1	Intelligente Agenten
Agententypen, Eigenschaften einer Agentenumgebung, Problemformulierung, Problemtypen, Zustandsraum
Kapitel 2	Lösen durch Suchen
Knoten, Rand, allgemeiner Suchalgorithmus, blinde Suchverfahren, heuristische Suchfunktionen, Optimierung
Kapitel 3	Schlußfolgern
Wissensbasis, Inferenzmaschine, autonom, Wissensrepräsentation, Konsequenz, Inferenzen, Aussagenlogik
Kapitel 4	Logik 1. Ordnung
Eigenschaften und Bestandteile, Symbole und Sätze,Ortsbestimmung, Ableiten, Vorwärts- und Rückwärtsverkettung
Kapitel 5	Planen
Repräsentationen, Ziele und Aktionen, Situationsraum, Planraum, Kausale Kanten, Promotion, Demotion
Kapitel 6	Handeln
Bedingtes Planen, Ausführungsüberwachung, Unsicherheit, Evidenz, Wahrscheinlichkeitsaxiome, Bayessche Regel
Kapitel 7	Beobachten
Modell lernender Agenten, Performanzelement, Lernelement, Kritik, Problemgenerator, induktives Lernen
Kapitel 8	Neuronale Netze
Struktur, Begriffe, Rechenelemente, Perzeptron, Anwendungen

Quelle: Die Ausarbeitung basiert auf dem Skript von Prof. Dr. Werner Dilger