Startseite < Informatik < Algorithmen < Sortieren Komprimieren [ DRUCK , 2004 , 2005 , 2006 , 2007 , 2008 , 2009 ] Suchen < Damenproblem Springerproblem Solitaire > / Primzahltest > Datenstrukturen / Software-Engineering / Programmiersprachen / Künstliche Intelligenz > Schach Privates / Inhalt >
Suchen
Wie kann anhand eines Suchkriteriums ein Objekt gefunden werden?
Einführung Definitionen zum Thema Suchen
Suchen
Das Suchen ist die Tätigkeit, in einem vorgegebenen Datenbestand (Suchraum) alle Objekte zu ermitteln, die eine bestimmte Bedingung, das Suchkriterium, erfüllen. [INFODUDEN S. 706]
Suchraum
Ein Suchraum ist
  • eine Datenstrukturinstanz,
  • eine Menge bzw. Ansammlung von vernetzten Daten,
  • ein Datennetz,
  • ein Graph.
Der Suchraum besteht aus Knoten (Datenobjekte), die untereinander in Beziehung stehen. Die Suche arbeit sich über vernetzte Knoten – wenn es sein muss – durch das gesamte Knotennetz wie beispielsweise über Nachbarschaftsbeziehungen zwischen den Knoten oder über Vater-Sohn-Beziehungen. Knoten des Suchraums stellen die Argumente/Objekte für das Suchkriterium dar.
Suchkriterium
Mit dem Suchkriterium wird geprüft, ob ein besuchtes Objekt das Zielobjekt ist. Das Suchkriterium ist im Allgemeinen eine Indikatorfunktion, mit der die Zielobjekte identifiziert werden:
  1. if (Suchkriterium(Objekt))
    then print('Zielobjekt gefunden!');
Agenda
Die Agenda ist eine Liste (listenartige Datenstruktur), die ein wichtiger Bestandteil eines jeden Suchalgorithmus darstellt. In diese Liste werden all jene Objekte (genauer: Referenzen bzw. Pointer auf Objekte) aufgenommen, die während der Suche noch abgearbeitet werden müssen, d. h. dass in die Agenda vom aktuellen Knoten die noch unbesuchten Nachbarknoten aufgenommen werden, die dann im weiteren Verlauf der Suche eventuell wiederum selbst weitere noch unbesuchte Nachbarknoten zur Verfügung stellen. Der Suchalgorithmus
  • beginnt in der Regel, wenn die Agenda als einziges Objekt das Startobjekt enthält.
  • terminiert, wenn die Agenda leer ist oder wenn das Ziel während der Suche entdeckt wird.
Suchalgorithmen unterscheiden sich grundlegend in Ihrer Strategie meist je nach Strukturierung der Agenda. Ist beispielsweise die Agenda eine Warteschlange, handelt es sich um eine Breitensuche.
Suchstrategien Unterschiedliche Suchstrategien
Man unterscheidet zwischen zwei Arten von Suchstrategien:
  • Uninformierte bzw. blinde Suche

    Das Suchverfahren bekommt keine Auskunft darüber, wo sich das Ziel befindent (auch nicht ungefähr).
    • Tiefensuche

      Ein Suchverfahren wird als Tiefensuche (Depth-First-Search, DFS) bezeichnet, wenn die zugrundeliegende Agenda ein Stack ist.
    • Breitensuche

      Ein Suchverfahren wird als Breitensuche (Breadth-First-Search, BFS) bezeichnet, wenn die zugrundeliegende Agenda eine Queue ist.
    • Dijkstra-Suche

      Die Dijkstra-Suche ist ein Suchverfahren, welches die Agenda als eine prioritätsorientierte Warteschlange verwendet. Jeder Knoten erhält jeweils einen Kostenwert (Prioritätswert), der die Länge der Wegstrecke vom Startknoten aus bis zum Knoten speichert. Die Hauptfrage bei der Dijkstra-Suche ist nämlich: wie kann ein Knoten mit den geringsten Kosten erreicht werden?
  • Informierte bzw. heuristische Suche

    Diesem Suchverfahren wird das Ziel mitgegeben wie zum Beispiel die Zielposition bzw. die Zielsituation.
    • Greedy-Suche

      Die Greedy-Suche oder auch die Bestensuche (Best-First-Search) ist ein Suchverfahren, welches die Agenda auch als eine prioritätsorientierte Warteschlange verwendet. Der Prioritätswert eines Knotens wird von einer optimistischen, heuristischen Funktion berechnet.
    • A*-Suche

      Die A*-Suche (sprich: A Stern) ist eine Erweiterung der Greedy-Suche, welches die Agenda auch als eine prioritätsorientierte Warteschlange verwendet. Zur heuristischen Funktion kommt noch eine Kostenfunktion (vergleiche Dijkstra-Suche) hinzu.

      Bei großen Suchräumen muss man strategisch vorgehen, und die einzig wahre Strategie lautet: A*.

      Als probates Suchverfahren im IT-Bereich der Künstlichen Intelligenz ist der A*-Suchalgorithmus bekannt. Auch wenn man unter etwas Zusatzaufwand eine heuristische Funktion angeben muss, so wird man mit der optimalsten Laufzeitkomplexität belohnt. In der Entwicklung von KI-Systemen spielt das Thema „Suchen” eine wesentliche Rolle. KI-Lösungen werden nämlich gesucht, wobei die Wissensbasis den Suchraum darstellt.
Beispiele Unterschiedliche Suchverfahren anhand zweier Beispiele
Unterschiedliche Suchverfahren in einer Grid-Map
Eine Grid-Map ist eine rasterisierte 2D-Landschaft, die nicht selten als Karte für Computerspiele dient. Jedes einzelne Feld enthält zur Pfadsuche relevante Informationen wie beispielsweise, ob das Feld begehbar ist, ob sich ein Gegener auf dem Feld befindet oder wieviele Spielfiguren auf dem Feld bereits verendeten, usw.
Ob nun ein Feld Bestandteil des Ergebnispfades sein kann, entscheidet das Suchkriterium, mit dem gesucht wird. Wenn sich zum Beispiel der Held auf einem Grid-Map von Feld A nach Feld B bewegen muss, dann gibt es auf dem Wege meist ein Hindernis, welches Dank des Suchkriteriums umgangen werden kann.

Ein Suchalgorithmus bezüglich einer Grid-Map sucht einen möglichen Weg von A nach B. Falls die Suche keinen Pfad finden sollte, so existiert auch kein Ergebnispfad (Vollständigkeit).

Mit dem folgenden Applet 1 wird das Suchverhalten verschiedener Suchalgorithmen innerhalb einer Grid-Map simuliert. Das Suchkriterium des folgenden Applet ist recht einfach gelagert, es prüft lediglich, ob ein Feld begehbar ist oder nicht.
1) Nur Mut beim Applet, einfach Klicki-Klacki alles ausprobieren! Leider benötigen Sie hierfür einen leistungsstarken Rechner.
Mehr zu diesem Applet finden Sie unter Pfadsuche-Applet.
A*-Suche anhand eines Schiebepuzzles
Das Schiebepuzzle, welches wohl jedem bekannt sein dürfte, verfügt über einen unendlichen (Zyklen!) Suchraum, weshalb ein blindes Vorgehen (brute force) wie bei der Breitensuche sehr viel Speicherplatz verbraten würde. Deshalb wird für das 8-Puzzles-Schiebepuzzle eine informierte Suche eingesetzt, meist das A*-Suchverfahren. Für dieses Suchbeispiel sind zwei heuristische Funktionen bekannt:
  1. Manhattenabstand 2 aller Puzzle-Teilchen
    mit h(n) = |x - x(n)| + |y - y(n)|
  2. Summe der falsch positionierten Puzzle-Teilchen
    (etwas effizienter zu berechnen)
Es bleibt dem Entwickler überlassen, für welche heuristische Funktion er sich entscheidet. An dieser Stelle möchte ich Sie kurz darauf hinweisen, dass die heuristische Funktion dazu da ist, um einen kürzestmöglichen Lösungsweg zu finden. Die heuristische Funktion h muss lediglich eine Bedingung erfüllen: Optimisums! :-) Das heißt, die heuristische Funktion h gibt immer eine kürzere Weglänge zurück, als es tatsächlich der Fall sein wird. Wird die erforderliche Eigenschaft der Heuristik verletzt, so erhält man dennoch eine Lösung. Ob diese Lösung dann ein kürzester Lösungsweg ist, hängt vom Zustand des Suchraumes ab:
  • Der maximale Fehlerabstand der Lösungswege ist kleiner oder gleich dem maximalen Schätzfehler einer zu pessemistischen Heuristik.
Näheres zur A*-Suche finden Sie in den Unterlagen zu meinem Hauptseminar.

Und nun viel Spaß mit dem Schiebepuzzle. :-)
2) Der Manhattenabstand ist nicht der diagonale bzw. euklid'sche Abstand, sondern die Summe von Horizontal- und Vertikalabstand. Der Manhattenabstand wird manchmal auch "city block distance" genannt - durch einen Häuserblock fährt es sich nicht so leicht hindurch. :-)
Mehr zu diesem Applet finden Sie unter 8-Puzzles-Applet.
Startseite   Sitemap   Downloads   Hilfe   Impressum  
Fußnoten
  1. Nur Mut beim Applet, einfach Klicki-Klacki alles ausprobieren! Leider benötigen Sie hierfür einen leistungsstarken Rechner.
  2. Der Manhattenabstand ist nicht der diagonale bzw. euklid'sche Abstand, sondern die Summe von Horizontal- und Vertikalabstand. Der Manhattenabstand wird manchmal auch "city block distance" genannt - durch einen Häuserblock fährt es sich nicht so leicht hindurch. :-)
Quellenangabe
  • [INFODUDEN] Duden Informatik: 1993 Auflage2, Bibliographisches Institut & F. A. Brockhaus AG ISBN 3-411-05232-5 Ein Sachlexikon für Studium und Praxis
Startseite < Informatik < Algorithmen < Sortieren Komprimieren [ DRUCK , 2004 , 2005 , 2006 , 2007 , 2008 , 2009 ] Suchen < Damenproblem Springerproblem Solitaire > / Primzahltest > Datenstrukturen / Software-Engineering / Programmiersprachen / Künstliche Intelligenz > Schach Privates / Inhalt >