Datenstrukturen

Suche von Wegen in Graphen


Algorithmen zur Suche von Pfaden in Graphen lassen sich als Schemata sehr allgemeiner Problemlösestrategien auffassen und sind Hilfsmittel bei vielen grundlegenden Aufgaben der Informatik.

Graphen und speziell Bäume sind gut grafisch und damit anschaulich darstellbar. Startet man bei der Behandlung von Suchproblemen mit einem von sich aus grafisch orientierten Problemstellung, dann nutzt man diese Eigenschaft. Das Problem der Suche von Wegen in Labyrinthen ist allein deswegen für unterrichtliche Zwecke schon gut geeignet. Hinzu kommt, dass mit dem ARIADNE - Problem die historisch erste bekannte Anwendung eines Suchverfahrens vorliegt. Die Betrachtung solcher Labyrinthe und von Strategien, wie man in ihnen zum "Ausgang" findet, werden wir daher als erstes angehen!

Die Labyrinthe des ARIADNE - Projektes (s.u.) sind ungerichtete, endliche und zusammenhängende Graphen. Begeben wir uns gedanklich in ein solches Labyrinth, dann wird sofort eine elementare Technik klar, die man bei der Bearbeitung der Lösung des Problemes anwendet:

Teile das Gesamtproblem in die Abfolge von Teilproblemen auf, die dadurch entsteht, dass du nun an einem Ort stehst und dich entscheiden musst, wie du weitergehen willst.

Besonders bei interessanten Problemen ist die richtige Abfolge dieser Auswahl der nachfolgenden Teilaufgaben nicht vorab eindeutig festgelegt, sondern man kann erst nachträglich entscheiden, ob eine vorgenommene Auswahl sinnvoll war:

Sucht man z.B. in einem Graphen von einer Ecke aus einen Weg zu einer bestimmten Zielecke, dann könnte diese mit jeder Kante beginnen, die von der Startecke ausgeht. Es bleibt also nichts anderes übrig, als alle Möglichkeiten nacheinander solange auszuprobieren, bis eine Lösung gefunden ist oder das Problem endgültig als unlösbar erkannt ist.

Bevor wir zu einer ausführlichen Behandlung verschiedener Verfahren und ihrer Bedeutung für Suchprobleme kommen, wollen wir für eines von ihnen einige Vorüberlegungen anstellen: Die Tiefensuche !

 


 

"Das ARIADNE - Projekt" war der Titel einer früheren Handreichung zu Suchverfahren (von Theo Stenzel), aus der einige Textpassagen der einführenden Abschnitte übernommen wurden, weil einerseits das Problem immer noch hervorragend zur Einführung in Suchprobleme geeignet ist (s.o.) und grundlegende Techniken -nicht nur- von Suchverfahren kennengelernt werden können.

Mit "Labyrinth" wird hier —wie umgangssprachlich üblich— ein Irrgangsystem bezeichnet. Das klassische Labyrinth, auf das sich die Theseussage bezieht, enthielt keine Kreuzungen.