35

Intelligente Systeme (Subject) / Suche (Lesson)

This lesson was created by Sogn.

Learn lesson

This lesson is not released for learning.

back  |  next 1 / 1

• Wie unterscheidet sich die uninformierte Suche zur informierten Suche? Die Strategien besitzen keinerlei zusätzliche Informationen und können lediglich Nachfolger erzeugen und finale Zustände von nicht-finalen unterscheiden.
• Welche Algorithmen für uninformierte Suche gibt es? Breitensuche (Breadth-First)Tiefensuche (Depth-First) Tiefenbegrenzte (Depth-Limited) Iteratives Verfahren (Iterative Deepening)
• Wie ist generell das Vorgehen der Suchalgorithmen? Wie unterscheiden sie sich? Die Knoten expandieren, bis man im Suchbaum das Ziel gefunden hat.Die Strategie entscheidet über die Reihenfolge.
• Wie funktioniert die Breitensuche? Vollständig? Optimal? Man beginnt beim Startknoten, von dort betrachtet man nun alle Nachbarn. Jetzt geht man zum äußersten neu entdeckten Knoten und betrachtet von diesen wieder seine Nachbarn, dann zum nebenstehenden usw. Die Breitensuche ist vollständig, da sie immer den flachsten Knoten finden wird, weil alle flacheren bereits erzeugt und nicht als Zielzustand erkannt worden sind. (Sofern endlich)Die Breitensuche ist optimal, sofern die Pfadkosten identisch sind.
• Wie funktioniert die Tiefensuche? Vollständig? Optimal? Man startet am Startknoten. Dann geht man so tief in den vom erstentdeckten Nachbarn ausgehenden Ast, wie es nur möglich ist. Geht es nicht weiter geht man eins zurück und zum rechten Nachbarn. Dort wieder so tief usw. Man geht an sich immer den linken Pfad.Die Tiefensuche ist bei unendlichen Tiefen oder Schleifen nicht vollständig. Wenn zb. Zweig a undenlich ist, wird die Lösung in Zweig b nie gefunden.Die Tiefensuche ist auch nicht optimal, da sie zB. einen Teilbaum bis zum Ende durchsuchen würde und dort schließlich eine Lösung fände, obwohl im anderen Teilbaum eine viel nähere Lösung vorliegt.
• Wie lässt sich das Problem von Schleifen bei unendlichen Suchbäumen mit DFS, umgehen? Mit der tiefenbeschränkten Suche, bei welcher Knoten, welche eine Tiefe > vorgegebene Tiefenbegrenzung besitzen, nicht weiter expandiert werden. Führt aber leider wieder zu Informationsverlust, wenn der Zielknoten darunter läge. Somit ist sie zumindest vollständig, aber nicht optimal.
• Wie funktioniert die uniforme Kostensuche? Es werden wie bei BFS alle Nachbarn betrachtet. Dann aber wird der mit denmomentan am geringsten Pfadkosten erweitert. Tabellarisch am besten zu lösen.Somit lässt sich für jede Schrittkostenfunktion die optimale Lösung finden.
• Welche Faktoren fließen in die Bewertung eines Suchalgorithmus mit ein? Vollständigkeit Optimalität Zeitkomplexität Speicherkomplexität
• Wie kann man die Breitensuche einsetzen, um kürzeste Pfade in einem Graphen zu berechnen? Durch eine Erweiterung zum Dijkstra Algorithmus.
• Wie funktioniert die Iterative Tiefensuche? Vollständig? Optimal? Bei dieser wird die max. Tiefe t jede Iteration um eins erhöht. Somit endet der Alogrithmus , wenn die Tiefe des flachsten Zielknoten erreicht ist. Sie kombiniert die beiden Vorteile von BFS und DFS. Sie ist somit sowohl vollständig, als auch optimal.
• Advertisement
• Welche Faktoren fließen in die Bewertung eines Suchalgorithmus mit ein? Vollständigkeit Optimalität Zeitkomplexität Speicherkomplexität
• Vergleich der uninformierten Suchalgorithmen in Bezug auf Speicher und Zeit! Breitensuche: Jeder generierte Knoten verbleibt im Hauptspeicher, somit gilt O(bd+1) Zeitaufwand ist exponentiell, beträgt ebenfalls O(bd+1) Tiefensuche:  Da es nur nötig ist einen einzigen Pfad von der Wurzel zu einem Blattknoten zu   speichern , können expandierte Knoten danach wieder entfernt werden. O(bm) Zeittechnisch wird es problematisch, sobald die Tiefe des Baumes sehr viel höher als die Tiefe der Lösung ist, da jeweils nur jeder Zweig gespeichert werden muss. O(bm) Tiefenbeschränkt: O(bt), wobei t = vorgegebene Tiefe O(bt) Iterative Suche: O(bd), wobei d = Tiefe des Zielknotens O(bd)
• Welche informierten Suchalgorithmen gibt es? Greedy First A*
• Pseudocode für Graphensuche? Function GraphSearch(graph, source_vertex, destination_vertex)    queue = [source_vertex]     for each vertex v in graph:        visited[v] = False  // a vector to indicate whether a vertex visted or not        parent[v] = UNDEFINED     while queue is not empty:        next_vertex = pop(queue)  // pop (): returns the first item and removes it from the list.        if next_vertex == destination_vertex:            return next_vertex        visited[next_vertex] = True        for each follow_vertex v of next_vertex:            if visited[v] == False                append v into queue                parent[v] = next_vertex         return failure
• Was ist der Unterschied der informierten zur uninformierten Suche? Wählt einen Knoten auf Basis einer Evaluierungsfunktion f(n) zur Expandierung aus.Die Evaluierungsfunktion wird als Kostenabschätzung konstruiert, sodass der Knoten mit der geringsten Bewertung zuerst erweitert wird.
• Wie funktioniert die gierige Suche? Warum gierig? Die „gierige“ Bestensuche8 (Greedy Best-first) versucht, den Knoten zu expandieren,der dem Ziel am nächsten liegt, mit der Begründung, dass dies wahrscheinlich schnellzu einer Lösung führt. Damit bewertet der Algorithmus die Knoten nur mithilfe derHeuristikfunktion, d.h. f(n) = h(n). Gierig weil er versucht in jedem Schritt, dem Ziel so nahewie möglich zu kommen.
• Wie sieht es bezüglich Optimalität und Vollständigkeit bei Greedy Search aus? Die Suche ist nicht optimal, da es auch insgesamt kürzere Lösungen geben könnte, welche voerst vom Knoten weiter entfernt sind, als immer durch naheliegende Knoten.Er ist für Bäume unvollständig, für Graphen jedoch nicht (sofern endlich). Bei Bäumen kommt es gern zu Endlosschleifen.
• Wie funktioniert die A* Suche? Wertet Knoten aus, indem sie g(n), die Kosten zur Erreichung des Ziels, und h(n), die Kosten, um von dem Knoten zum Ziel zu gelangen, verknüpft: f(n) = g(n) + h(n)
• Optimalität und Vollständigkeit von A*? Vorausgesetzt, die Heuristikfunktion h(n) erfüllt bestimmte Bedingungen, ist die A*-Suche sowohl vollständig als auch optimal. Heuristik muss zulässig sein. Kosten, um das Ziel zu erreichen, werden niemals überschätzt. Heuristik muss konsistent sein. (Graphensuche) Eine Heuristik ist konsistent, gdw. für jeden Knoten n und jeden Folgeknoten n‘ gilt, daß h(n)kleinergleich c(n,n‘) + h(n‘), wobei c(n,n‘) die Kosten für den Übergang von n nach n‘ sind.(Dreiecksungleichung) h(n) ≤ c (n, a, n') + h(n')
• Vergleich des Speicher und Zeitaufwandes von A* und Greedy First. A* ● Zeitaufwand○ Abhängig von Abweichung der Heuristik von den wahren Kosten● Speicheraufwand:○ Alle Knoten bleiben im Speicher.
• Verleich Speicher und Zeitaufwand von Greedy Search und A* Greedy Im ungünstigsten Fall ist die Zeit- und Platzkomplexität für die Versionder Baumsuche O(bm), wobei m die maximale Tiefe des Suchraumes darstellt. Miteiner guten Heuristikfunktion kann die Komplexität jedoch wesentlich reduziert werden. Wie weit diese Reduzierung möglich ist, hängt vom jeweiligen Problem und derQualität der Heuristik ab. A* ● Zeitaufwand   ○ Abhängig von Abweichung der Heuristik von den wahren Kosten● Speicheraufwand:   ○ Alle Knoten bleiben im Speicher.
• Warum sollte f(n) für die A* Suche eine Unterschätzung sein? Sobald f(n) überschätzt wird gilt ebenfalls, dass h(n) überschätzt wird, da f(n) = g(n) + h(n). Dies ist laut den Heuristikbedingungen nicht zulässig, dadurch gehen weitere eventuell bessere Lösungen verloren.
• Was bedeutet es , wenn bei A* f(n) = 0 ist? Es wird eine Breitensuche durchgeführt.
• Welche Auswirkung haben hohe Vernetzungen für DFS? Günstig, da die Tiefe d meistens sehr gering ausfällt. Speicher und Zeitaufwand sind abhänging von der Tiefe d.
• Was sind ideale bzw. ungeignete Werte für den Schwellenwert K? Bei Überschätzung: Reduzierung des Speicheraufwandes durch Wegwerfen von Pfaden, welche nicht Teil des Optimums sein können. Bei Unterschätzung gehen womöglich bessere Lösungen verloren. Bei Überschätzung werden zunehmend weniger Knoteneliminationen möglich.
• Sollte A* terminiert werden, sobald alle Zielknoten gefunden wurden? Nein, expandiere alle Knoten , welche eventuell zu einem kürzeren Pfad gehören (also f(n1)<= f(n2)), wobei n1 noch nicht vollständig expandierte Knoten und n2 die gefundenen Zielknoten sind.
• Pseudocode für die Baumsuche? Blätter = [Startknoten] While Blätter nicht leer:   Nächster = pop(Blätter)   If Nächster = Zielknoten thenreturn Nächster     For all Folgeknoten von Nächster         Füge Folgeknoten der Liste Blätter hinzu Return failure pop gibt erstes Element aus Liste
• Was bedeuten b, d und m? b: maximaler Verzeigungsgrad (branchingfactor) d: Tiefe der besten Lösung (depth) m: Maximale Tiefe des Zustandsraumes (kann unendlich sein)
• Nach welchem First/Last Verfahren arbeitet DFS bzw BFS? DFS: LIFO BFS: FIFO
• Wie kann bei tiefenbeschränkter Suche Vollständigkeit erreicht werden? Indem man t sukzessiv erhöht -> Iteratives Verfahren
• Advertisement
• Wie lässt sich ein Schwellenwert K bestimmen? Zb. durch vorherige Durchführung mit dem Greedy Algorithmus.
• Warum wird der exakte Zeitaufwand der Breitensuche mit d+1 und nich mit d berechnet? m schlimmsten Fall liegt der gesuchte Knoten im letzten ("rechtesten") Ast des Baumes in Tiefe d. Es müssen also alle Nachfolgeknoten in d+1 angesehen (und in die Queue eingereiht) werden, außer die des gesuchten Knotens.
• Wie lassen sich die Suchalgorithmen auf Graphen mit Kreisen erweitern? Man muss sich merken, welche Knoten besucht worden sind , und welche nicht.
• Wie lautet die Zeit und Speicherkomplexität bei Greedy Search wenn die Heuristik perfekt ist? O(d)
• Wann ist A* nicht vollständig? Wenn es unendlich viele Knoten gibt mit f(n) < f(g)

back  |  next 1 / 1