Einführung in Suchverfahren

Zurück zum Inhaltsverzeichnis

Suchverfahren

Viele geographische Probleme können als Suchproblem formuliert werden. Ob es um die Suche nach dem besten Standort, der besten Route oder ganz allgemein um die Suche einer Lösung zu einem Problem geht, ist vorerst zweitrangig. Erst das Verständnis von Suchalgorithmen ermöglicht die Aussage, ob ein Problem aus der Praxis mit ihrer Hilfe lösbar ist. Bevor ein Suchverfahren angewendet werden kann, muß das Problem in eine Form gebracht werden, die eine Verarbeitung durch ein Suchverfahren ermöglicht.

Ein Computerprogramm muß auf vorgegebenen Wegen suchen und sich durch komplizierte Netze mit Zuständen oder Bedingungen bewegen, um eine bestimmte Zielposition zu erreichen (Tanimoto 1990, S. 171). Solche Netze können als Graphen beschrieben werden. Die Knoten des Graphs repräsentieren die unterschiedlichen Zustände, die innerhalb des Suchraums auftreten können. Die Kanten des Graphs repräsentieren die Bewegungen oder Übergänge von einem Zustand zum anderen. Untenstehende Abbildung  soll dies anhand einer Pfadsuche illustrieren.

Quelle: Winston 1992, S. 64

Gesucht wird ein Pfad vom Startknoten S zum Zielknoten G. Die Kanten stellen den Übergang (in diesem Fall die Straße) von einem Ort zum nächsten dar. Sie bilden zugleich die Regeln, die einem Übergang von einem Knoten zum nächsten zu Grunde liegen. Nur dort, wo eine Straße vorhanden ist, ist ein Übergang überhaupt möglich. In diesem Fall bilden die Entfernungsangaben die Kosten, die beim Begehen dieses Pfades entstehen. Das Finden eines Pfades fällt dem Menschen in dieser einfachen und übersichtlichen Situation sehr leicht. Sogar der beste Pfad (unter der Bedingung, daß die Güte eines Pfades durch seine Länge ermittelt wird) erschließt sich dem Betrachter schnell. Für ein Computerprogramm ist diese Darstellung des Problems jedoch nicht optimal. Auch dem menschlichen Betrachter ist nicht sofort ersichtlich, wie viele Möglichkeiten es gibt, um von S nach G zu gelangen und wie sehr die unterschiedlichen Lösungen in ihrer Güte voneinander abweichen. Deshalb wird das Suchproblem in Form eines Suchbaums dargestellt. Die nächste Abbildung  zeigt den kompletten Zustandsraum des Problems aus der oberen Abbildung . Der Zustandsraum (state space) bezeichnet die Menge aller möglichen Zustände zu einem Problem und ihre Beziehungen untereinander. Vom Starknoten (root node) S ausgehend verzweigt sich der Baum entsprechend der Anzahl der Knoten, die von ihm ausgehen. Für jeden weiteren Knoten wird gleich verfahren, wobei Schleifen, das heißt eine Umkehr zum Ursprungknoten, vermieden werden.

Quelle (Winston 1992, S. 65)

Im obigen Beispiel ist der Zielknoten G. Ein Zielknoten wäre ausreichend um das Problem als lösbar zu bezeichnen. Da es vier Zielknoten gibt, existieren folglich vier verschiedene Lösungen für das Problem. Die Kosten einer Lösung ergeben sich aus der Summe der beteiligten Kanten entlang des Lösungspfades – in diesem Fall die akkumulierten Entfernungen.

Entscheidend für den Erfolg einer Suche ist die Wahl eines geeigneten Suchverfahrens. Geht man davon aus, daß das Problems an sich lösbar ist, läßt es sich – zumindest theoretisch – algorithmisch lösen, indem alle Pfade untersucht werden. Eine solche Suche wird als erschöpfend bezeichnet, da sie garantiert die beste Lösung, so es denn eine gibt, findet. Warum dies in Wirklichkeit nicht immer möglich ist, und warum man sich unter Umständen auch mit Lösungen zufrieden geben muß, die vielleicht nicht die besten sind, wird noch zu zeigen sein.