Wählen wir unabhängig von einer Definition einen anderen Zugang, dann lässt sich feststellen:
Die eigentliche Frage ist: Was unterscheidet ein Suchproblem von einem direkt lösbaren Problem, was unterscheidet einen Suchalgorithmus daher von einem Lösungsalgorithmus zu einem Problem, dessen Lösung wir vor seinem Start genau so wenig kennen ?
Ein gutes Beispiel zur Klärung dieser Frage erhält man, wenn das Intervallhalbierungsverfahrens zur Nullstellenbestimmung einer reellen Funktion mit einer binären Tiefensuche ( ggf. mit backtracking ) vergleicht. In beiden Fällen gibt es auf jeder ( Iterations- oder Rekursions- ) Stufe genau zwei Entscheidungen. Was aber die Nullstellenbestimmung mit dem Intervallhalbierungsverfahrens gravierend von der Tiefensuche unterscheidet, ist die Tragweite einer einmal gefällten Entscheidung:
Im ersten Fall ( Nullstellen - Bestimmung ) gibt es bei jeder Entscheidung ein eindeutiges Kriterium der Art dies ist das richtige Teilintervall von den beiden möglichen, hier muss ich weitermachen.
Im anderen Fall der Tiefensuche dagegen ist allein bekannt, dass eine von beiden möglichen Entscheidungen die richtige sein kann ! Es ist nicht einmal gewährleistet, dass eine von beiden überhaupt richtig ist, da in den meisten Fällen schon bei einer der vorigen Entscheidungen auf einer vorausgehenden Rekursionsstufe die falsche gewählt wurde und damit der ( oder ein möglicher ) Lösungspfad verlassen wurde.
Dieses Risiko nimmt die Tiefensuche bewusst in Kauf. Stellt sich im weiteren Verlauf des Verfolgens eines Weges in die Tiefe nämlich heraus, dass die Entscheidung nicht zu einer Lösung geführt hat, dann kann danach auch noch die andere Alternative verfolgt werden.
Das entscheidende Kriterium zur Abtrennung der
Suchverfahren von direkten Lösungsverfahren ist also:
Werden einmal gefällte Entscheidungen ggf. wieder rückgängig gemacht und auch noch Alternativen versucht oder wählt man auf jeder Stufe genau eine richtige ( von möglicherweise mehreren richtigen ) und verfolgt in jedem Fall dann auch nur diese weiter ? |
Bortfeldt schreibt im Abschnitt " 3.2 Die Repräsentation von Problemen
Nachdem im vorangegangenen Abschnitt die heuristische Suche informell eingeführt wurde, sollen nun die in der Künstlichen Intelligenz entwickelten Konzepte der formalen Repräsentation von Suchproblemen vorgestellt werden.
Suchprobleme werden in der Kunstlichen Intelligenz weitgehend einheitlich, nämlich als Transformationsprobleme repräsentiert. SCHEFE (1991) spricht in diesem Zusammenhang von einem Sucheparadigma der Künstlichen Intelligenz. Der Suchprozeß erscheint als eine Folge von Transformationen, die Situationen in andere Situationen überführen und auf diese Weise eine Verbindung von Ausgangs- und Zielsituationen herstellen. Dieser Sichtweise von Suche entspricht die folgende von KAINDL (1989) angegebene allgemeine Definition von Suchproblemen.
'Ein Problem ist durch eine Menge von Ausgangs-(Start-)Situationen und eine Menge von angestrebten Ziel-Situationen gegeben. Im Sinne der Lösbarkeit durch Maschinen werden bei der Problembeschreibung zumeist auch Angaben darüber vorausgesetzt, mittels welcher Operatoren (Regeln) Situationen in andere Situationen übergeführt werden können bzw. welche Situationen überhaupt zulässig sind. Eine Lösung soll Ausgangs- und Ziel-Situationen in gewünschter Weise verbinden' "
Eine Anmerkung zu den greedy - Algorithmen :
Greedy scheint in so fern ein direktes Verfahren und nicht mehr ein Suchverfahren zu sein. Das ist aber nicht richtig. Es wäre nur dann ein direktes Verfahren, wenn jede Entscheidung die richtige wäre. Das ist aber in der Regel nicht der Fall. Nur dann, wenn ein Greedy Verfahren nachweislich zur optimalen Lösung führt, stellt es ein direktes Lösungsverfahren dar. In diesem Sinne sind die Grenzen fließend!