Upload
carlene-storrer
View
105
Download
0
Embed Size (px)
Citation preview
Praktikum KI
Teil II: Informierte Suche
Praktikum KI SoSe 2005
Überblick
Organisation des Praktikums Einführung in die Künstliche Intelligenz Suche nach einer „intelligenten“ Lösung Problemlösung mit Heuristiken Planung & Robotik Logik Expertensysteme Lernen
Praktikum KI SoSe 2005
Informierte Suche Informierte Suchstrategien
Greedy Search A* Search
Heuristiken Eigenschaften Entwicklung Beispiele
Praktikum KI SoSe 2005
Informierte Suche „Uninformierte“ Suchalgorithmen arbeiten den Suchraum
systematisch, aber ohne weiteres problemspezifisches Wissen ab
Mehr problemspezifisches Wissen kann die Suche schneller zum Ziel führen
Heuristiken bewerten die Güte eines Zustands und steuern dadurch die Suche
Praktikum KI SoSe 2005
Informierte Suche Wiederholung allgemeiner Suchalgorithmus mit Tree-
Search :
Noch nicht expandierte Nachfolgerknoten kommen in die „fringe“
Aus der fringe wird geeignet der nächste zu expandierende Knoten ausgewählt
Lübeck
Hamburg Rostock
Kiel WittstockBremen HannoverLübeck Lübeck
„fringe“
Wittstock
Praktikum KI SoSe 2005
Informierte Suche Allgemeiner Ansatz zur informierten Suche: Best-First
Search Der jeweils bzgl. einer Bewertungsfunktion f (n) beste
Knoten in der fringe wird expandiert(=> fringe ist eine Prioritätswarteschlange)
Bewertungsfunktion f(n) setzt sich aus Heuristik h(n) und Geschichte des Knotens g(n) zusammen
Spezialfälle dieses allgemeinen Ansatzes: Greedy Search A* Search Aber auch uninformierte Suchstrategien!
Praktikum KI SoSe 2005
Informierte Suche Beispiele:
Greedy Searchf(n) = h(n)
A*-Searchf(n) = g(n) + h(n)
Breitensuchef(n) = g(n)
Hierbei sind h(n) geschätze Kosten von Knoten n zum Ziel (Heuristik) g(n) bisherige Kosten auf dem Weg vom Startknoten bis Knoten n
Praktikum KI SoSe 2005
Anwendungsbeispiel: Kürzeste Strecke von Lübeck nach Berlin
Informierte Suche
h
Tatsächliche Streckenkosten
Geschätzte Kosten bis Berlin
Praktikum KI SoSe 2005
Anwendungsbeispiel: Greedy Search
Informierte Suche: Greedy
hHL
HH HRO
Praktikum KI SoSe 2005
Anwendungsbeispiel: Greedy Search
Informierte Suche: Greedy
hHL
HH HRO
WK HL
Praktikum KI SoSe 2005
Anwendungsbeispiel: Greedy Search
Informierte Suche: Greedy
HL
HH HRO
WK HL
HH BHRO
h
Praktikum KI SoSe 2005
Anwendungsbeispiel: Greedy Search
Informierte Suche: Greedy
hHL
HH HRO
WK HL
HH BHRO
Praktikum KI SoSe 2005
Informierte Suche: Greedy Was das Beispiel zeigt:
Gier ist nicht immer gut … Optimalität wird nicht erreicht
Was das Beispiel nicht zeigt (aber trotzdem stimmt): Greedy-Suche nicht vollständig, da Zykel möglich Zeitbedarf O(bm) Speicherbedarf O(bm)
(b…branching factor, m… maximale Tiefe des Suchbaums)
Praktikum KI SoSe 2005
Informierte Suche: A* Gibt es einen optimalen Algorithmus?
Es reicht nicht aus, nur die verbleibende Entfernung zum Ziel zu betrachten
Auch der bis dato zurückgelegte Weg ist entscheidend A*-Suche: f(n) = g(n) + h(n)
Bedingung(en) an die Heuristik Zulässig (Niemals überschätzen):
c(n,z) ≥ h(n), c(n,z) … kürzester Weg von n zum Ziel z Konsistent (bewirkt aufsteigende f-Werte entlang jedes Pfades):
h(n) ≤ c(n,n‘) + h(n‘), für n‘ Nachfolger von n
Damit A*-Suche mit Tree-Search optimal ist, reicht zulässig aus (sh. Nächste Folie)
Praktikum KI SoSe 2005
Informierte Suche: A* Beweis:
Sei z ein Zielknoten im Suchbaum, z‘ der optimale Zielknoten (=> h(z‘) = 0) und n ein Knoten auf dem optimalen Weg zum Ziel z‘
Dann gilt:f(n) = g(n) + h(n) ≤ g(n) + c(n,z‘) = g(z‘) = f(z‘) ≤ f(z)
Falls z nicht optimal ist, ist also f(n) < f(z) Damit wird n eher aus der fringe expandiert als z Mit der Expansion von n kommen dessen Nachfolger in die fringe Via vollständiger Induktion werden also alle Knoten des optimalen
Pfades vor z expandiert, damit also auch z‘.
Praktikum KI SoSe 2005
Anwendungsbeispiel: A* Search mit Tree-Search
Informierte Suche: A*
h
HH319=65+254
HRO313=120+193
HL234=0+234
Praktikum KI SoSe 2005
Anwendungsbeispiel: A* Search mit Tree-Search
Informierte Suche: A*
h
HH319=65+254
HRO313=120+193
WK343=250+93
HL483=240+243
HL234=0+234
Praktikum KI SoSe 2005
Anwendungsbeispiel: A* Search mit Tree-Search
Informierte Suche: A*
h
HH319=65+254
HRO313=120+193
WK343=250+93
HL483=240+243
KI455=159+296 HB
592=177+315
H464=214+250 WK
339=246+93
HL364=130+234
HL234=0+234
Praktikum KI SoSe 2005
Anwendungsbeispiel: A* Search mit Tree-Search
Informierte Suche: A*
h
HH319=65+254
HRO313=120+193
WK343=250+93
HL483=240+243
KI455=159+296 HB
592=177+315
H464=214+250 WK
339=246+93
HL364=130+234
HL234=0+234
HH681=427+254
B352=352+0
HRO569=376+193
Praktikum KI SoSe 2005
Anwendungsbeispiel: A* Search mit Tree-Search
Informierte Suche: A*
h
HH319=65+254
HRO313=120+193
WK343=250+93
HL483=240+243
KI455=159+296 HB
592=177+315
H464=214+250 WK
339=246+93
HL364=130+234
HL234=0+234
HH681=427+254
B352=352+0
HRO569=376+193
Praktikum KI SoSe 2005
Informierte Suche: A* Eigenschaften von A*-Search mit Tree-Search
Optimal für zulässige Heuristik Es wird kein Knoten mit f(n) > f(z‘) expandiert
=> Vollständig, falls alle Kantengewichte > ε > 0=> Speicherbedarf O(bdz‘)=> Zeitbedarf O(bdz‘)
Was passiert bei Graph-Search? Ohne Zusatzvoraussetzungen / Zusatzaufwand geht Optimalität
verloren Für Optimalität: Es muss sichergestellt werden, dass immer der
kürzeste Weg zum Knoten gespeichert wird Extra Überprüfung für jeden Knoten oder Konsistente Heuristik verwenden
Praktikum KI SoSe 2005
Heuristiken Wie erzeugt man Heuristiken?
Relaxieren des Problems Teilprobleme lösen (+ Musterdatenbanken anlegen) Kombination bekannter Heuristiken
Wie bewertet man Heuristiken? Dominanz
Praktikum KI SoSe 2005
Heuristiken: Relaxierung Relaxieren des Problems an einem Beispiel:
Für 8-Puzzle gelten folgende Regeln: Man darf einen Stein nur um ein Feld bewegen Man darf einen Stein nur auf ein freies Feld bewegen
Praktikum KI SoSe 2005
Heuristiken: Relaxierung Verzichte nun auf einzelne Regeln (Relaxieren des
Problems) Lösung wird einfacher Jede Lösung des komplizierten Problems ist auch Lösung des
relaxierten (einfachen) Problems, da dessen Regeln natürlich eingehalten werden
Die beste Lösung des relaxierten Problems ist besser oder gleich der Lösung des komplizierten Problems und ist somit zulässige Heuristik für das komplizierte Problem
Es gilt auch, dass die so erhaltenen Heuristiken konsistent sind (warum?)
Praktikum KI SoSe 2005
Heuristiken: Relaxierung Beispiel: Keine Regeln
Lösung: Jeden Stein direkt auf seinen Platz „schieben“ h1(n) = Anzahl der falsch platzierten Steine Im Bild: h1(n) = 6
Praktikum KI SoSe 2005
Heuristiken: Relaxierung Beispiel: Mehrfachbelegung eines Feldes erlaubt
Verzicht auf Regel „ Man darf einen Stein nur auf ein freies Feld bewegen“
Lösung: Steine nacheinander in e(S) Zügen auf ihren Platz schieben
e(S) = Manhattendistanz h2(n) = ΣSe(S) Im Bild: h2(n) = 14
Praktikum KI SoSe 2005
Heuristiken: Relaxierung Beispiel: Springen von Steinen erlaubt
Verzicht auf Regel „ Man darf einen Stein nur um ein Feld bewegen“
Lösung: ?
Praktikum KI SoSe 2005
Heuristiken: Dominanz Das 8-Puzzle ohne Regeln ist Relaxierung des 8-Puzzles
mit der Regel „Steine nur um ein Feld bewegen“ Damit gilt h1(n) ≤ h2(n) Man sagt „Heuristik h2 dominiert h1“ Konsequenz: Die A*-Suche mit h2 liefert immer schneller
Ergebnisse als die Suche mit h1
Beweis (Gilt nur für konsistente Heuristiken! Warum?): A*-Suche expandiert alle Knoten n mit f(n) < f(z‘) und keinen mit
f(n)> f(z‘) Für Zielknoten z‘ gilt h(z‘)=0, also f(z‘)=g(z‘) unabhängig von der
Heuristik Damit gibt es für h1 < h2 mehr Knoten, die noch expandiert
werden, d.h. Knoten mit
g(n) + h1(n) = f1(n) < f(z‘) < f2(n) = g(n) + h2(n)
Praktikum KI SoSe 2005
Heuristiken: Teilprobleme lösen Heuristiken durch das Lösen von Teilproblemen gewinnen
Beispiel: 8-Puzzle, bringe die Steine 1-4 in die richtige Reihenfolge
Ist einfacher, da die entstehende Reihenfolge von 5-8 egal ist Somit auch zulässig Es gilt auch hier wieder, dass solche Heuristiken konsistent sind
(warum?)
Praktikum KI SoSe 2005
Heuristiken: Teilprobleme lösen Grundlegende Idee:
Alle möglichen Instanzen der Teilprobleme vorher lösen und Lösung abspeichern -> Musterdatenbank
Während der Suche nach der Lösung des Gesamtproblems für jeden Zustand die Instanz des Teilproblems bestimmen
Optimale Kosten der Lösung dieser Instanz des Teilproblems geben Heuristik für Lösung des Gesamtproblems
Eigentliche Lösung des Teilproblems interessiert nicht Datenstruktur: Z.B. Hash-Table
Praktikum KI SoSe 2005
Heuristiken: Maximum-Heuristik Was macht man, wenn man mehrere Heuristiken zur
Verfügung hat, die sich nicht dominieren?
Maximum bilden! h(n) = max {h1(n), …, hk(n)} Maximum zulässiger Heuristiken ist wieder zulässig Maximum konsistenter Heuristiken ist wieder konsistent