Was bisher geschah Daten, Information, Wissen explizites und implizites Wissen intelligente Agenten, wissensbasierte Systeme Wiederholung klassische Aussagenlogik Tableau-Kalkül für klassische Aussagenlogik Wiederholung klassische Prädikatenlogik Repräsentation und Verarbeitung von Wissen in Modallogiken (entscheidbare Fragmente der klassischen Prädikatenlogik): Repräsentation zustandsabhängigen Wissens, Tableau-Kalkül für Modallogik Repräsentation von zeitichem Wissen Temporallogiken, LTL Repräsentation von Wissen über Wissen (mehrerer Agenten) Repräsentation von begrifflichem Wissen Ontologien, Beschreibungslogiken 98 Problemlösung durch Suche in Graphen Beispiele: 1. Finden von Wegen in einem Graphen Aufgabe: gegeben: Graph G (Tafel) gesucht: Weg (Pfad) in G von Knoten u zu Knoten v Lösungsidee: Suche im Graphen 2. Münzenstapelspiel (für eine Person) (Beispiel aus der LV Theoretische Informatik) Aufgabe: gegeben: Stapel von n Münzen gesucht: Zugfolge bis zu einer Situation, in der kein Zug möglich ist erlaubte Züge: zwei Münzen von einem Stapel nehmen und auf beide Nachbarn verteilen Lösungsidee: Modellierung als Zustandsübergangssystem (Graph mit Markierungen) Suche im Graphen 99 Darstellung von Aufgabe und Lösung Aufgabe: gegeben: Menge V von Zuständen (evtl. unendlich) oft beschrieben durch Eigenschaften Startzustand s ∈ V Menge Z ⊆ V von Zielzuständen (oder Eigenschaften der Zielzustände) mögliche Übergänge zwischen Zuständen Übergangsrelation E ⊆ V × V Lösung: Folge von Zuständen (Weg von einem Start- zu einem Zielzustand) (Mitunter interessiert nur der erreichte Zielzustand.) Wissensrepräsentation: als Graph G = (V , E) (Zustandsübergangssystem): Knotenmenge V : Zustände (gerichtete) Kanten: Zustandsübergänge Entfaltung des Graphen zu einem Baum: Pfade im Graphen = Knoten im Baum 100 Problemlösen durch Suchen formale Darstellung des Problemes als Graph bzw. Baum formale Beschreibung der Lösung als Eigenschaft von Pfaden im Graphen Knoten im Baum Möglichkeiten zum Problemlösen: Pfadsuche im Graphen Knotensuche im Baum 101 Suche in Graphen (schon bekannte) Verfahren zur Suche in Graphen (und Bäumen): Tiefensuche (depth-first search): Suche zuerst in Teilbäumen eines noch nicht besuchten Nachbarn des aktuellen Knotens Breitensuche (breadth-first search): Suche zuerst in Teilbäumen eines noch nicht besuchten Knotens mit der geringsten Tiefe 102 Allgemeines Suchverfahren Daten: La Menge der noch zu expandierenden Knoten Lx Menge der expandierten Knoten s Startknoten Allgemeiner Suchalgorithmus: 1. La = {s}, Lx = ∅, gefunden = f 2. solange ¬ (gefunden ∨ La = ∅): 2.1 Verschiebe einen auf festgelegte Art ausgewählten Knoten u aus La in Lx (Abbruch falls u einen Lösung repräsentiert) 2.2 Füge alle Nachbarn von u, die La ∪ Lx nicht enthält, auf eine festgelegte Art in La ein prominente Spezialfälle: Tiefensuche Verwaltung von La als Stack Einfügen der Nachbarn an den Anfang der Liste La festgelegter Knoten wurde zuletzt in La eingefügt Breitensuche Verwaltung von La als Queue Einfügen der Nachbarn an das Ende der Liste La festgelegter Knoten wurde zuerst in La eingefügt 103 Beispiel Missionare + Kannibalen informale Problembeschreibung: Zu Beginn: 3 Missionare + 3 Kannibalen an einem Flussufer Ziel ist das Übersetzen aller Personen Es gibt nur ein Boot, welches höchstens zwei Personen fasst. Sobald an einem Ufer mehr Kannibalen als Missonare sind, werden die Missionare gefressen. formale Darstellung der Aufgabe: ◆ Zustände: ((ms , ks ), (mz , kz )) ∈ 4 mit ms + mz = 3 (Missionare) und ks + kz = 3 (Kannibalen) Startzustand: ((3, 3), (0, 0)) Zielzustand: ((0, 0), (3, 3)) Zustandsübergänge ((ms , ks ), (mz , kz )) → ((ms , ks ), (mz , kz )) 104 Eigenschaften von Suchverfahren Fairness: jeder Knoten wird expandiert Vollständigkeit: jede Lösung wird gefunden Optimalität: eine beste Lösung wird (zuerst) gefunden Zeitaufwand: größtmögliche Anzahl der Schritte von einem Start- zu einem Endzustand (Speicher-)Platzbedarf: größtmögliche Länge der Liste der noch nicht expandierten Knoten Laufzeit für Baum mit maximaler Tiefe t und maximalem Verzweigungsgrad d: Breitensuche: vollständig, (optimal) großer Zeitaufwand: O(d t ) großer Platzbedarf: O(d t ) Tiefensuche: unvollständig bei unendlichen Bäumen, nicht optimal großer Zeitaufwand: O(d t ) geringerer Platzbedarf: O(td) 105 Heuristische Suche – Motivation Heuristik: Effizienzsteigerung durch Zusatzinformationen (z.B. Erfahrungswerte) Problem mit mehreren Lösungen (z.B. Wege in Graphen) unterschiedliche Qualität der Lösungen (z.B. Länge des Weges) Suche nach optimalen Lösungen (z.B. kürzester Weg) falls vollständige Suche zu aufwendig Ziele: Wahl einer geeigneten Such-Reihenfolge, unter welcher gute Lösungen zuerst gefunden werden Verwerfen von Knoten, die wahrscheinlich nicht zu einer Lösung führen (beabsichtigte Verletzung der Fairness-Eigenschaft) 106 Schätzfunktionen Ziel: sinnvolle Auswahl der in jedem Schritt zu expandierenden Knoten unter Verwendung von Zusatzinformationen ❘ Bewertungsfunktion g : V ∗ → ≥0 zur Bewertung von Lösungen (Pfaden von Start- zu einem Zielzustand) (Pfadkosten) ❘ Schätzfunktion f : V → ≥0 (oder in eine andere geordnete Menge) wobei für jeden Zielknoten u gilt: f (u) = 0 Schätzung der Bewertung der Pfade, die den Knoten v enthalten (repräsentiert die Zusatzinformation) 107 Besten-Suche (best-first-search) Allgemeines Suchverfahren mit folgender Strategie zur Auswahl der in jedem Schritt zu expandierenden Knoten: Ordnung der zu expandierenden Knoten aufsteigend nach Wert der Schätzfunktion f : V → ≥0 ❘ Expansion des Knotens v mit dem geringsten Wert f (v ) zuerst Verwaltung von La als priority queue (oder sortierte Liste) Beispiel: Suche eines kürzesten Weges zwischen den Orten A und B Schätzfunktion: Luftlinienentfernung von B 108 Besten-Suche – Eigenschaften zwei Methoden: 1. Knoten mit großen Werten möglichst spät expandieren 2. Knoten mit großen Werten nicht expandieren Bestensuche mit einer beliebigen Schätzfunktion ist nicht immer optimal. Bestensuche nach Methode 1 (fair) ist vollständig Bestensuche nach Methode 2 ist nicht immer vollständig 109 Beispiel Schiebefax Aufgabe: Zustände 3 × 3-Matrix mit Einträgen {0, . . . , 8} (jede Zahl genau einmal, 0 leeres Feld) Zulässige Züge: Verschieben des leeren Feldes auf ein Nachbarfeld d. h. Vertauschen von 0 und einem Wert in einem Nachbarfeld (gleicher Zeilen- oder Spaltenindex) Zielkonfiguration 1 2 3 8 0 4 7 6 5 Aufgabeninstanz: gegebene Ausgangskonfiguration (Matrix) Lösung: Folge von zulässigen Zügen von der Ausgangszur Zielkonfiguration Bewertung den Lösung: Länge der Lösungsfolge 110 Greedy-Suche (kleinste Restkosten) Idee: Suche zuerst in Teilbäumen der noch nicht besuchten Knoten mit den gerigsten (geschätzten) noch aufzuwendenden Kosten Heuristische Funktion h : V → ≥0 h(u) ist Abschätzung des von Knoten u aus den noch notwendigen Kosten zum Erreichen eines Zielzustandes Heuristische Funktion h heißt nicht überschätzend gdw. für alle v ∈ V gilt h(v ) ≤ minimale Kosten aller Pfade von v zu einem Zielzustand Greedy-Suche: Besten-Suche mit Schätzfunktion f : V → ≥0 , wobei für jeden Knoten v ∈ V gilt ❘ ❘ f (v ) = h(v ) Eigenschaften der Greedy-Suche: vollständig? optimal? 111 Schiebefax – Heuristische Funktionen fi : {0, . . . , 8} → ◆ mit 1. Anzahl der Zahlen, die sich nicht an ihrer Zielposition befinden 2. weitester Abstand einer Zahl zu seiner Zielposition 3. Summe der Manhattan-Abstände jeder Zahl zu seiner Zielposition Qualität der Schätzfunktionen: gute Trennung verschiedener Zustände fair: zu jedem n ≥ 0 existieren nur endlich viele u ∈ V mit f (u) ≤ n 112 Bisherige Kosten ❘ Kostenfunktion k : V → ≥0 k (u) Kosten des besten (bisher bekannten) Pfades vom Startzustand zum Zustand u Kostenfunktion k : V → ❘≥0 heißt streng monoton wachsend , falls für alle Knoten v und alle Nachfolger u von v gilt k (u) < k (v ) Beispiele für Kostenfunktionen: Tiefe des Knotens im Suchbaum, maximale Entfernung vom Startknoten 113 Gleiche-Kosten-Suche (kleinste bisherige Kosten) (uniform-cost-search) Idee: Suche zuerst in Teilbäumen der noch nicht besuchten Knoten mit den bisher geringsten (bekannten) Kosten Gleiche-Kosten-Suche: Besten-Suche mit Schätzfunktion f : V → ≥0 , wobei für jeden Knoten v ∈ V gilt ❘ f (v ) = k (v ) Eigenschaften der Gleiche-Kosten-Suche: vollständig? optimal? Beispiele: Breitensuche (Kosten = Tiefe des Knotens) kürzeste Wege (Kosten = Abstand des Knotens vom Startknoten) Dijkstra-Algorithmus 114 A∗ -Suche (kleinste Gesamtkosten) Idee: Suche zuerst in Teilbäumen der noch nicht besuchten Knoten mit dem geringsten Wert der Schätzfunktion (Summe von bisherigen und geschätzen zukünftigen Kosten) Funktionen k : V → ≥0 – bisher bekannte Kosten von einem Startzustand zu v h : V → ≥0 – geschätzte Kosten von v zu einem Endzustand ∗ A -Suche: Besten-Suche mit Schätzfunktion f : V → ≥0 , wobei für jeden Knoten v ∈ V gilt f (v ) = k (v ) + h(v ) ❘ ❘ ❘ Eigenschaften der A∗ -Suche: vollständig? optimal? 115 Anwendungen Planungsprobleme und kombinatorische Suchprobleme, z.B. TSP Verlegen von Leitungen Schaltkreis-Layout Navigation (z.B. von Robotern) Scheduling Produktionsplanung 116