Wenn wir bei der Tiefensuche oder Breitensuche den nächsten Knoten expandieren, dann nehmen wir auf das besondere Problem keinen Bezug.
Darin liegt ja gerade die Möglichkeit begründet, ein allgemeingültiges Programm Tiefensuche mit backtracking schreiben zu können. Der Anwender muss nur gewährleisten, dassFür die Tiefensuche gilt:
Zur Strategie bei der Tiefensuche siehe dort. Kurz:
Strategie bei der Tiefensuche |
Wähle als nächsten zu expandierenden Knoten einen beliebigen unter denen mit maximaler Pfadlänge (Tiefe) aus. |
Für die Breitensuche gilt entsprechend:
Zur Strategie bei der Breitensuche siehe dort. Kurz:
Strategie bei der Breitensuche |
Wähle als nächsten zu expandierenden Knoten einen beliebigen unter denen mit minimaler Pfadlänge (Tiefe) aus. |
In jedem Fall zeigen die Formulierungen, dass allein Informationen des schon expandierten Graphen verwendet werden und keine Informationen über den Restgraphen.
Selbst die optimierenden Varianten, etwa des "hierarchischen Generate and Test" nutzen allein die Informationen, die im schon generierten Suchgraphen stecken. Das bedeutet aber, dass im expandierten Teil des Graphen überhaupt reale, zum Problem gehörende Informationen enthalten sein müssen. Was nützt beispielsweise eine Information über die Pfadlänge zu einem Knoten, wenn sie für die Lösung des Problems belanglos ist?