AIMA Notizen

Inhalt

• heuristische Suchstrategien versuchen, zunächst den "besten" Knoten für die weitere Suche zu expandieren
• wir kennen bereits g(n), die Kosten, den aktuellen Knoten zu erreichen
• wir suchen f(n), die Kosten eines Pfades bis zum Ziel, die wir aber nur schätzen können
• h(n) ist die geschätzte (Heuristik-)Funktion der Kosten vom aktuellen Knoten bis zum Ziel
  
• heuristische Suchstrategien
• generell expandieren wir die Knoten, die ein minimales f(n) haben -> best-first bzw. seemingly best-first
  
• gierige Suche (greedy best-first search)
• f(n) := h(n)
• wir wählen immer den wahrscheinlich nächsten Knoten zum Ziel
• nur bei Sackgassen wird rückgesetzt (backtracking)
  
• ähnlich der Tiefensuche
• nicht optimal, weil schlechte Lösungen gefunden werden können
• für h(n) = 1 identisch mit Tiefensuche
  
• A*-Suche
• f(n) := g(n) + h(n)
• Breitensuche, ber der wir immer den Knoten mit den niedrigsten zu erwartenden Gesamtkosten expandieren
• benötigt eine optimistische Heuristik die niemals die Kosten zum Ziel überschätzt um optimal zu sein
• dadurch wird im Zweifel lieber ein Knoten zuviel expandiert als einer zu wenig
  
• bei der Suche in Graphen: Heuristik muss außerdem monoton sein
• kein anderer Algorithmus kann optimal sein und weniger Knoten expandieren als A*
• üblicher Nachteil der Breitensuche: alle teilexpandierten Knoten müssen im Speicher gehalten werden
• ein Ausweg: Tiefensuche und iterative Erhöhung der maximalen Kosten
• geht nur für ganzzahlige Kosten und ist nicht immer günstig
  
• Recursive best-first search (RBFS)
• die Heuristik wird näher am Ziel genauer, deswegen wird f(n) näher zum Ziel hin größer
• ähnlich normaler best-first Suche
• aber wenn die erwarteten Kosten der besten Alternative auf dem aktuellen Pfad geringer sind wird rückgesetzt und dabei die Kosten des besten Blattes in den rückgesetzten Knoten übertragen
• geringe Speicherkomplexität, aber möglicherweise hohe Laufzeit, wenn ständig zwischen zwei guten Alternativen gewechselt wird
• nutzt den zur Verfügung stehenden Speicher nicht optimal aus
  
• simplified memory-bounded A* (SMA)
• solange der Speicher ausreicht wie A*
• um Speicher zu befreien wird das schlechteste Blatt gelöscht und der Wert wird in den Vaterknoten übernommen (wie RBFS)
• Heuristik-Funktionen am Beispiel 8-puzzle
  
• h1 = Anzahl der falsch positionierten Teile
  
• h2 = Manhattan-Distanz der falsch positionierten Teile
• h2 dominiert h1, weil h2 > h1 -> h2 ist effizienter bei der Suche
  
• Heuristik-Funktionen können automatisch erzeugt werden, indem das Problem vereinfacht wird
• -> Lösungen vereinfachter Probleme sind zulässige Heuristiken des Ursprungsproblems
• Heuristiken können kombiniert werden: h = max(h1, h2, ...)
• Lösungen von Teilproblemen (vier Teile des 8-puzzles statt 8) sind zulässige Heuristiken
• Muster-Datenbanken speichern die Muster der Teilprobleme mit ihren Kosten
  
• disjunkte Muster-Datenbanken speichern Muster mehrerer Teilprobleme mit ihren Kosten ohne die der anderen Teilprobleme, nicht immer möglich
• Heuristiken können auch gelernt werden
  
• lokale Suche und Optimierungsprobleme
• wenn nur das Ziel, nicht aber der Pfad zählt
• keine Pfade, sondern Zustände
  
• hill-climbing
• greedy
• so noch nicht optimal
• viele Varianten:
• begrenzte Seitwärtsbewegung, um Plateaus zu überwinden
• nicht unbedingt der höchste Nachbar wird gewählt, sondern je nach Wahrscheinlichkeit auch ein weniger steiler Pfad eingeschlagen
• first-choice hill climbing, wählt den erstbesten besseren Folgezustand (wenn es viele tausend davon gibt)
• random-restart hill climbing führt hill climbing mehrfach aus und wählt das beste Ergebnis
• simuliertes Stählen/Härten
• gedanklich suchen wir nicht mehr den höchsten Berg, sondern das tiefste Tal
• Kombination aus herabrollen lassen und schütteln, um aus kleinen Kuhlen wieder herauszukommen
• am Anfang schüttelt man sehr stark und zum Ende hin schwächer
• im Algorithmus: ein zufälliger Nachfolger wird gewählt
• ist er besser, so wird er immer gewählt
• ist er schlechter, so wird er nur mit einer gewissen Wahrscheinlichkeit T (wie Temperatur) gewählt
• T ist am Anfang groß und wird mit der Zeit kleiner
• man kann zeigen, dass das globale Optimum gefunden wird, wenn T langsam genug sinkt
• local beam search
• aus k verschiedenen Zuständen werden jeweils die k besten Nachfolger ausgewählt
• Variante mit Stochastik
  
• genetische Algorithmen
• lokale Suche in kontinuierlichen Räumen
• Steigung berechnen und in die Richtung gehen
• wie sinnvoll ist das ganze in Digitalrechnern?
  
• Online-Suche
• offline: erst Berechnung, dann Ausführung
• online: Verschränkung von Suche und Aktion
• notwendig für Erforschung, da auf neue Kenntnisse reagiert werden muss
• wenn ich nicht ewig auf das Ergebnis der Berechnung warten kann
• ...
  

letzte Änderung: 22. Dezember 2004.