Wie kann man Erfolg versprechender vorgehen ? lautete die Frage am Ende des Abschnittes über den Weg in die Sackgasse.
Selbstverständlich möchte man nur möglichst wenig Ecken des Graphen besuchen, aber : Welche wählt man als nächstes aus?
Kriterium ist eine -zumindest bei der Expansion neuer Knoten zu berechnende- Bewertungsfunktion. Die Schreibweisen unterscheiden sich in den Büchern, ich richte mich hier nach der Schreibweise von Bortfeld: f = g + h. Mit dieser Funktion f soll gemessen werden, welchen Vorteil man von der Expansion der nachfolgenden Knoten man sich versprechen kann. Die Formulierung macht klar: Es geht hier um Informationen auch über den noch nicht expandierten Teil des Graphen, es handelt sich also um Informierte Graphensuchverfahren.
Strategie beim A - Stern - Algorithmus |
Wähle als nächste in den Suchbaum aufzunehmende Ecke die mit minimalem Wert der Schätzfunktion aus. |
Dabei berechnet man den Wert der Schätzfunktion aus der Länge des Weges zur aktuellen Ecke zuzüglich dem Schätzwert für den unbekannten Restweg. |
Als nächster weiter zu verfolgender Knoten wird der ausgesucht, dessen Bewertung nach dieser Funktion f den besten Wert hat, man nennt ein solches Vorgehen daher Bestensuche [best first search]. Da alle die Knoten, die während der geasamten Bearbeitung des Verfahrens -also bis zum Finden irgendeines Weges zum Ziel- keine bessere Bewertungbekommen haben, gar nicht erst expandiert werden, werden sie quasi vorzeitig aussortiert und die Suche bekommt eine Zielrichtung.
Das Problem dabei ist die Frage der Zuverlässigkeit! Liefert uns das Verfahren tatsächlich eine gute Auswahl von weiter verfolgten Wegen der macht es dabei viele Fehler ?
Beim minmal spanning tree haben wir gesehen, dass es Probleme gibt, bei denen sogar die rein lokalen Informationen ausreichen, um exakt zielgerichtet zu arbeiten. Exakt zielgerichtet heißt eben auch: Kein Suchverfahren mehr, sondern ein direktes Verfahren. Leider -wie wir gesehen haben- gilt das nur für ganz wenige Probleme! Selbst mit globalen Informationen müssen wir damit rechnen, auch Knoten expandieren zu müssen, die im Endeffekt nicht zum Ziel führen. Bei einem passenden Problem uund einer guten Bewertungsfunktion f sollten aber möglichst wenige "Umwege" notwendig sein.
Anmerkung:
Eine solche Bewertungsfunktion hat natürlich einen Berechnungsaufwand zur Folge. Dabei muss man aufpassen, dass der Aufwand nicht höher wird als der Vorteil, der sich aus der gezielten Auswahl ergibt. Hier nun verschiedene Alternativen durchzuspielen, wird in der Regel daher nicht sinnvoll sein. Hierin liegt aber die besondere Anforderung insbesondere an die Berechnung für den noch nicht expandierten Teil des Graphen.