Grundsätzliches über heuristische Verfahren

Zurück zum Inhaltsverzeichnis

Heuristische Verfahren

Viele Suchprobleme sind derart komplex, daß sie sich mit einer blinden Suche nicht in praktikabler Zeit lösen lassen. Grund hierfür ist die exponentiell ansteigende Anzahl der zu untersuchenden Möglichkeiten. Beispielhaft soll dies an der Suche nach der besten Standortverteilung für 100 Mobilfunkmasten auf 1000 mögliche Standorte illustriert werden. In diesem Fall gibt es 1000! / 100! Möglichkeiten – eine Zahl, die sich aufgrund ihrer Größe mit gängiger Software weder berechnen noch darstellen läßt.

Heuristische Suchverfahren versuchen der Problematik dadurch zu entgehen, daß sie auf eine vollständige Untersuchung des Suchraumes verzichten. Dies kann allerdings zur Folge haben, daß entweder gar keine Lösung gefunden wird oder eventuell die gefundene Lösung nicht optimal ist.

Heuristiken können nach folgenden Kriterien unterschieden werden:

• erschöpfend – nicht erschöpfend
• informiert – uninformiert

Eine erschöpfendes Verfahren findet garantiert die optimal Lösung, obwohl es nicht den vollständigen Suchraum untersucht. Als Beispiel soll eine Namensdatenbank dienen, die zu jedem Eintrag Name, Vorname und Geburtsdatum enthält. Sucht ein Anwender in der Datenbank nach dem Geburtsdatum von Peter Müller, so wird er erwarten, alle Einträge angezeigt zu bekommen, die in der Spalte "Name" den Begriff "Müller" und in der Spalte "Vorname" den Begriff "Peter" enthalten. Die Software, die die Datenbank verwaltet, könnte nun alle Datensätze auf diese Kriterien hin durchsuchen. Allerdings wäre es effektiver, nur bei denjenigen Datensätzen die Spalte "Vorname" zu untersuchen, in denen die Überprüfung der Spalte "Name" bereits den Begriff "Müller" ergeben hat. Obwohl nicht alle Datensätze (beziehungsweise Suchpfade) vollständig untersucht wurden, wird das vollständige und korrekte Ergebnis ausgegeben werden. Die Suchzeit ist gegenüber der vollständigen Suche in etwa halbiert. Übertragen auf das Suchen in Suchbäumen bedeutet dies, daß Pfade, die offensichtlich abwegig sind, da sie zum Beispiel eine Bedingung verletzen oder die Suchkosten bereits einen bestimmten Wert überschritten haben, von der weiteren Suche ausgeschlossen werden.

Ein nicht erschöpfendes Verfahren kann ein gutes Ergebnis liefern, ohne daß der Anwender die Gewißheit hat, daß es nicht doch eine bessere Lösung gibt. So wird zum Beispiel ein Geschäft gesucht, welches ein Produkt zum günstigsten Preis verkauft. Der Kaufwillige erkundigt sich daraufhin in fünf Geschäften der Stadt und kauft das Produkt in dem Laden, in dem er es am günstigsten bekommt. In der Regel hat der Käufer nun ein gutes Gefühl, obwohl er nicht sicher sein kann, ob er das Produkt in einem der fünf anderen Läden der Stadt (oder gar im Nachbarort) nicht hätte billiger bekommen können.

Bei informierten Verfahren liegt für jeden untersuchten Knoten innerhalb des Suchbaumes ein heuristischer Schätzwert vor, der auf seine Güte schließen läßt. Die Pfade entlang der vielversprechendsten Knoten werden zuerst untersucht, da sie, im Verhältnis zu den schlechteren Knoten, ein besseres Ergebnis erwarten lassen. Ein Bergsteiger, der den Weg zum Gipfel sucht, wird den nächsten Schritt in der Regel bergauf setzen, da er weiß, daß er zum Erreichen seines Ziels bergauf gehen muß. Sollte er nach einiger Zeit feststellen, daß der von ihm eingeschlagene Weg eine Sackgasse ist, wird er umkehren und einen anderen Weg wählen. Genau so verhält es sich bei den informierten Verfahren. Der vielversprechendste Pfad wird zuerst untersucht. Führt er nicht zum Ziel, kommt der nächstbeste Pfad an die Reihe.

Nicht informierte Verfahren verfügen über keine heuristische Schätzfunktion. Bis zum erreichen der Lösung haben sie keinen Anhaltspunkt dafür, wie gut der eingeschlagene Pfad ist. Beispielhaft hierfür ist die Suche nach der Nadel im Heuhaufen. Der Suchende weiß nicht, ob es besser ist, links oder rechts, oben oder unten zu suchen. Erst wenn er die Nadel gefunden hat, ist er sich über den besten Lösungsweg im Klaren.

Heuristische Suchverfahren ermöglichen also Lösungsverfahren für Probleme, die unter Verwendung der blinden Suche erst mit der nächsten oder übernächsten Rechnergeneration lösbar wären. Die verfügbare Anzahl heuristischer Suchverfahren ist wesentlich größer, als die auf diesen Seiten vorgestellten. Je nach Problemstellung, Anforderung an die Güte der Lösung oder die verfügbare Rechenzeit können unterschiedliche Verfahren eingesetzt werden.