Home >Documents >INT A – Vorlesung, WS04/05 Prof. Dr. Wolfram Conen Oktober 2004

INT A – Vorlesung, WS04/05 Prof. Dr. Wolfram Conen Oktober 2004

Date post:01-Jan-2016
Category:
View:14 times
Download:1 times
Share this document with a friend
Description:
INT A – Vorlesung, WS04/05 Prof. Dr. Wolfram Conen Oktober 2004. Inhalte: - Formales und Inhalte - Einführung - Suche. Formales (1). Sie müssen die Übungsaufgaben abgeben bzw. bearbeiten (max. 2 Blätter nicht) Die Übungsaufgaben werden nicht benotet - PowerPoint PPT Presentation
Transcript:
  • INT A Vorlesung, WS04/05Prof. Dr. Wolfram ConenOktober 2004Inhalte: - Formales und Inhalte- Einfhrung- Suche

    (c) W. Conen, FH GE, INT A

  • Formales (1)Sie mssen die bungsaufgaben abgeben bzw. bearbeiten (max. 2 Bltter nicht)Die bungsaufgaben werden nicht benotetTeil der Aufgaben wird ein Vortrag zu einer grundlegenden Aufgabenstellung der KI seinFr diesen Vortrag knnen Sie bis zu 5 Bonuspunkte fr die Klausur erhaltenEs wird eine 90-120mintige Klausur am Ende geben mit einer 40%-Bestehensgrenze

    (c) W. Conen, FH GE, INT A

  • InhalteProblemlsen (Teil 1) / Suche Wissen + Logik (Teil 1: Aussagenlogik)Problemlsen (Teil 2) / Constraint SatisfactionLogik (Teil 2: Prdikatenlogik / Prolog)Problemlsen (Teil 3): Neuronale Netze, GA, SA durch die Natur motivierte VerfahrenProblemlsen (Teil 4): Markov, Bayes und anderes rationales Entscheiden

    (c) W. Conen, FH GE, INT A

  • Knstliche Intelligenz (KI)KI: Teilgebiet der Informatik, welches versucht, menschliche Vorgehensweisen der Problemlsung auf Computern nachzubilden, um auf diesem Wege neue oder effizientere Aufgabenlsungen zu erreichen, aus: Lmmel, Cleve: Knstliche Intelligenz, 2. Aufl. 2004, Hanser Verlag

    (c) W. Conen, FH GE, INT A

  • Problem 1 Missionare und KannibalenDrei Missionare und drei Kannibalen sind auf der selben Seite eines Flusses. Es gibt auf dieser Seite auch ein Boot, das ein oder zwei Leute aufnehmen kann. Problem: Finden Sie nun einen Weg, alle so auf die andere Seite zu bekommen, dass die Zahl der Kannibalen die Zahl der Missionare auf irgendeiner Seite des Flusses niemals berschreitet (dann wrden die Missionare nmlich gefressen ...). Sie haben 15 Minuten lsen Sie das Problem!

    (c) W. Conen, FH GE, INT A

  • Wie lst man solch ein Problem?Man sucht nach einer LsungAber zunchst mal mu man sich klar machen, WAS genau die Aufgabe istMan sucht nach einer gnstigen Repsentation des ProblemsGnstig ist sie, wenn man mit dieser Reprsentation leicht eine Lsung (fr das umformuliert, reprsentierte Problem) finden kann... und diese Lsung sich zurck bertragen lsst auf die ursprngliche Problemstellung also das tatschliche Problem lst!Und natrlich sollte die Reprsentation beherrschbar sein, also mglichst klein, verstndlich (wartbar), przise, usw.Dann beginnt die Suche nach einer Lsungsmethode.Oft hat man bereits eine Methode im Hinterkopf und schaut, ob man das Problem passend reprsentieren kann (z.B. Constraint Optimization, Genetic Algorithms, Neuronale Netze, sehen wir alles noch)Wenn man die Methode (ev. auch mehrere) ausgewhlt hat, dann beginnt die tatschliche Suche nach einer Lsung, und zwar auf der gewhlten Problemreprsentation

    (c) W. Conen, FH GE, INT A

  • Welche Probleme knnen auftreten?Man findet keine griffige Reprsentation, weil z.B.Informationen fehlen oder unscharf sindInformationen unsicher/unglaubhaft sind Man hat ein Problem vor sich, dassim allgemeinen unlsbar ist (Halteproblem)im allgemeinen hart zu lsen ist (NP-komplett, EXP) Man kennt keine sinnvolle Problemlsungsmethode fr die gefundene ReprsentationIn unserer Veranstaltungen werden Sie einige Methoden fr verschiedene Reprsentationen kennenlernen ...... und wenn die richtige nicht dabei ist, dann knnen Sie mit ihrem Wissen und ihrer Cleverness vielleicht einen (Er-)Finden!

    (c) W. Conen, FH GE, INT A

  • SucheAngenommen, sie wollen ein Problem lsen ... ... dann suchen sie nach einer LsungViele Probleme lassen sich als Graph-Probleme modellierenmanchmal ist das unmittelbar klar (MST, krzeste Wege, TSP)manchmal braucht man einen abstrakten Umweg:Das Problem spielt sich in einem bestimmten Realwelt-Ausschnitt ab, den man durch eine Menge von Dingen und (regelhaften) Beziehungen zwischen diesen Dingen beschreiben kannDiese Dinge (und damit der Ausschnitt) befinden sich zu jedem Betrachtungszeitpunkt in einem bestimmten ZustandModellieren kann man das z.B. durch Parameter/Variablen, denen Wertebereiche zugeordnet sind und zwischen denen Relationen bestehen.Ein Zustand entspricht dann einer konkreten Belegung der Parameter mit Werten

    (c) W. Conen, FH GE, INT A

  • Suche (Forts. Problemlsen als Suche)Aus den Wertebereichen und Beziehungen/Regeln ergeben sich die mglichen Zustnde des RealweltausschnittsEs steht eine Menge an Operatoren zur Verfgung, um einen Zustand in einen Folgezustand zu berfhrenEin Problem sieht dann wie folgt aus:Gesucht ist eine clevere Sequenz von Operatoranwendungen, die uns von einem gegebenen Ausgangszustand in einen gewnschten Zielzustand fhrt.Regelmig wollen wir zudem eine besonders gute Operatorsequenz finden (z.B. eine kostengnstige, wenn wir Kosteninformationen zu den Operatoren haben)

    (c) W. Conen, FH GE, INT A

  • Suche (Forts. Problemlsen als Suche)Ausgangszustand z1, Zielzustand z11Es gibt viele mgliche Pfade inkl. Sackgassen (z7,z8) und unerreichbare Zustnde (z10)z1z2z3z4o1o2o3z5z6z7z8z9z10z11z1z3z5z9z11

    (c) W. Conen, FH GE, INT A

  • Suche (Forts. Problemlsen als Suche)Schauen wir uns noch eine der Sackgassen anUm einen Weg zum Ziel zu finden, mssen wir einfach eine Entscheidung fr einen Operator zurcknehmen und ndernDas nennt man Backtracking!z1z2z3z4o1o2o3z5z6z7z8z9z10z11z1z3z5z8z8z9z11

    (c) W. Conen, FH GE, INT A

  • Suche (Forts. Problemlsen als Suche)Es gibt viele verschiedene Wege in diesem Zustandsgraphen (wieviele?), manche dieser Wege fhren zum Ziel, andere nichtUm garantieren zu knnen, dass wir das Ziel erreichen (oder sicher sein knnen, dass es nicht erreichbar ist), mssen wir ggfs. alle von z1 aus begehbaren Wege anschauenWie knnen wir das systematisch tun?z1z2z3z4o1o2o3z5z6z7z8z11z10z11z1z3z5z8z9

    (c) W. Conen, FH GE, INT A

  • Suche (Forts. Problemlsen als Suche)z1z2z3z4o1o2o3z5z6z7z8z9z10z11z1z3z5z8z9z1z3z4z5z8z9z11z11z2z6z6z7z7z8z9z8z9z11z11z5z8z9z11z5z9z11z9 z9z5z3z6z9z6z11z11z9z9z6z7z7z3z8z8z8z2z6z5z8z5z8z9z11z11z9z9z5z2z8z8z6z9z11z11z9z9z6z2z4z7z1z1z7z4z4Tiefensuche

    (c) W. Conen, FH GE, INT A

  • Suche (Forts. Problemlsen als Suche)z1z2z3z4o1o2o3z5z6z7z8z9z10z11z1z1z3z4z5z8z9z11z2z6z6z7z7z8z9z8z9z11z11z5z8z9z11z3z2z3z4z2z5z6z7z3z2z4z3z8z9z5z6z5z6z5z5z6z6z7z4z8z7z9z8z11z8z9z8z9z8z9z8z9z9z8z8z9z11z9212121234321234321234321 z1z11Breitensuche

    (c) W. Conen, FH GE, INT A

  • Tiefensuche fr ZustandsbumeHilfsdatenstruktur: Knoten k im Zustandsgraph sind mit einem Zustand beschriftet, erhltlich ber k.zustandGenereller Ablauf fr Tiefensuche in einem Zustandsgraphen mit Baumform:Algorithm tiefensuche(Knoten start)for each k 2 Kinder(start) doif k.zustand = zielzustand thenprint Ziel gefunden!; return true;else if tiefensuche(k) then return true;return false;Liefert sicher eine Lsung, wenn es eine gibt!Achtung: Die Reihenfolge der Kinderbesuche ist nicht vorgeschrieben, sie knnen frei whlen!

    (c) W. Conen, FH GE, INT A

  • Breitensuche fr ZustandsbumeWir verwenden eine FIFO-Queue queue (also eine Liste, an die hinten angefgt und vorne entnommen wird, FIFO steht fr first-in-first-out)Genereller Ablauf fr Breitensuche in einem Zustandsgraphen mit Baumform: Algorithm breitensuche(Knoten start)queue.append(start); // queue leer vor Beginnwhile (not queue.empty()) dok queue.deleteFirst(); // Knoten k besuchenif k.zustand = zielzustand thenprint Ziel gefunden!; return true;for each c 2 Kinder(k) do // Knoten k expandierenqueue.append(c);print Kein Ziel gefunden!; return false; Anmerkung: Man kann auch vor dem Einstellen der Kinder prfen, ob ein Zielzustand erreicht ist. Wir haben in der Vorlesung gezeigt, dass das generell Speicher und Tests spart. Trotzdem verwenden wir aus Grnden der Einheitlich (s. BestFirst) fr die Aufgaben diese Variante. Grenordnungsmig macht es keinen Unterschied...exponentiellen Zeit- und Speicheraufwand erfordern beide Algorithmen in Best- und Worstcase (DFS nur im Worst Case!)

    (c) W. Conen, FH GE, INT A

  • Breitensuche fr ZustandsbumeLiefert sicher eine Lsung, wenn es eine gibt!Achtung: Die Reihenfolge der Kinderbesuche ist nicht vorgeschrieben, sie knnen frei whlen!Bisher haben wir Zustandsrume in Baumform betrachtetDa funktionieren beide Verfahren gut: beide sind komplett, d.h. sie finden einen Zielzustand, wenn er existiert und erreichbar istWenn die maximale Tiefe des Baumes d ist und der flachste Zielzustand sich auf der Ebene m befindet und wir einen gleichmigen Verzweigungsfaktor b unterstellen, dannTiefensuche: best-case O(m), worst-case O(bd), average case: hngt von der Verteilung der Zielzustnde ber die Tiefen zwischen m und d abBreitensuche: best-case = average case = worst-case O(bm), falls eine Lsung vorhanden ist, sonst best-case = average case = worst-case O(bd)

    (c) W. Conen, FH GE, INT A

  • Suche fr allgemeine ZustandsgraphenProblem: ein Graph, der kein Baum ist, enthlt einen Kreis, d.h. gleiche Zustnde knnen bei der Reise durch den Graphen mehrfach auftreten!Was passiert, wenn wir unsere Algorithmen auf einen Graphen mit Kreis loslassen?Die Tiefensuche luft immer weiter geradeaus und kann sich in einer endlosen Schleife aufhngen Wenn es eine Lsung gibt, findet die Tiefensuche sie dann nicht!Wenn es keine Lsung gibt, merkt sie es nicht!Die Breitensuche expandiert gleiche Knoten mehrfachKein prinzipielles Problem, wenn es eine Lsung gibt dann wird diese auch gefunden (und zwar weiterhin die flachste) die Breitensuche ist also auch im Wiederholungsfall komplett!Wenn es allerdings keine Lsung gibt, dann merkt unser einfaches Verfahren zur Breitensuche das nicht!

    (c) W. Conen, FH GE, INT A

  • Beispiel: Suche in Kreisen mit TiefensucheDUIOBGEEMHDStartzustandZielzustandGEOBGEOBEGEEMHDEDUIGEOBOBGEOBGEUnendliche Zweige knnen in dem Baumentstehen, der die Wege durch den Zustands-graphen darstellt (also die Suche beschreibt)!

    (c) W. Conen, FH GE, INT A

  • SucheKann

Embed Size (px)
Recommended