Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


44. Erschöpfendes Durchsuchen



Backtracking

Die Zeit, die die oben angegebene Prozedur des erschöpfenden Durchsuchens benötigt, ist zur Anzahl der Aufrufe von visit proportional, welche gleich der Anzahl der Knoten in dem Baum des erschöpfenden Durchsuchens ist. Für umfangreiche Graphen ist diese natürlich sehr groß. Wenn der Graph zum Beispiel vollständig ist (das heißt, wenn jeder Knoten mit jedem anderen Knoten verbunden ist), so existieren V! einfache Zyklen, wobei jeder Anordnung der Knoten einer entspricht. (Dieser Fall wird weiter unten eingehender untersucht.) Bereits für den Graph in Abbildung 44.1 ist es nicht leicht, allein durch Betrachtung einen Hamilton-Zyklus zu finden, so daß wir nach einer effizienteren Methode suchen, um dies mittels Computer zu realisieren.

Als nächstes betrachten wir Methoden, um die Anzahl der ausprobierten Möglichkeiten erheblich zu verringern. Alle diese Verfahren bestehen in der Hinzufügung von Tests zu visit, mit denen festgestellt werden kann, daß rekursive Aufrufe für bestimmte Knoten nicht erfolgen sollten. Dies entspricht einem Ausästen des Baums des erschöpfenden Durchsuchens, dem Abschneiden bestimmter Zweige und dem Löschen von allem, was mit ihnen zusammenhängt.

Eine wichtige Methode des Ausästens besteht in der Beseitigung von Symmetrien. Der Wert dieser Methode kommt in dem obigen Beispiel in der Tatsache zum Ausdruck, daß jeder Zyklus in beiden Richtungen durchlaufen wird und daher zweimal gefunden wird. In diesem Falle können wir gewährleisten, daß wir jeden Zyklus nur einmal finden, indem wir fordern, daß drei bestimmte Knoten in einer bestimmten Reihenfolge erscheinen müssen. Wenn wir zum Beispiel fordern, daß der Knoten C nach dem Knoten A, jedoch vor dem Knoten B erscheint, müssen wir visit für den Knoten B nur dann aufrufen, wenn C sich bereits auf dem Pfad befindet. Dies führt zu dem erheblich kleineren Baum, der in Abbildung 44.3 dargestellt ist.

Abbildung 44.3
Abbildung 44.3 Suche nach einem Zyklus mit A vor C vor B.

Dieses Verfahren ist nicht immer anwendbar. Nehmen wir zum Beispiel an, daß wir versuchen, einen Pfad zu finden (nicht unbedingt einen Zyklus), der alle Knoten verbindet. Dann kann das obige Schema nicht angewandt werden, da wir im voraus nicht wissen können, ob ein Pfad zu einem Zyklus führen wird oder nicht.

Jedesmal, wenn wir die Suche in einem Knoten abbrechen, vermeiden wir das Durchsuchen des gesamten Unterbaumes unter diesem Knoten. Für sehr umfangreiche Bäume ist dies eine sehr wesentliche Einsparung. Tatsächlich ist die Einsparung so beträchtlich, daß es sich lohnt, in visit unser Möglichstes zu tun, um zu vermeiden, daß rekursive Aufrufe erfolgen. Für unser Beispiel sind mehrere Vorgehensweisen möglich. Eine besteht in der Beobachtung, daß manche Pfade den Graph so zerlegen können, daß die nicht markierten Knoten nicht verbunden sind, so daß also kein Zyklus gefunden werden kann. Zum Beispiel kann in Abbildung 44.1 kein einfacher Pfad mit ABFE beginnen, da dieser Pfad B, C und D von dem restlichen Graph trennt. Mit dem Aufwand einer Tiefensuche, die erforderlich ist, um dies festzustellen, können wir 25 rekursive Aufrufe von visit vermeiden (siehe Abbildung 44.3).

Abbildung 44.4 zeigt den Suchbaum, der sich ergibt, wenn diese Regel auf den Baum in Abbildung 44.3 angewandt wird. Der Baum ist erneut erheblich kleiner geworden; er enthält nur noch 19 Knoten, im Vergleich zu 153 in dem vollständigen Baum des erschöpfenden Durchsuchens (Abbildung 44.2). Es muß erwähnt werden, daß die bei diesem sehr kleinen Problem erzielten Einsparungen nur eine ungefähre Vorstellung von der Situation bei umfangreicheren Problemen geben. Ein Abschneiden weit oben im Baum kann wirklich beachtliche Einsparungen ermöglichen; das Versäumen einer offensichtlichen Möglichkeit zum Abschneiden kann zu einer sehr beträchtlichen Vergeudung führen.

Abbildung 44.4
Abbildung 44.4 Suchen nach einem Zyklus mit Abbruch, wen der Graph zerlegt wird.

Die oben beschriebene allgemeine Prozedur zur Lösung eines Problems durch systematische Erzeugung aller möglichen Lösungen wird Backtracking (Zurückverfolgung) genannt. Immer dann, wenn partielle Lösungen eines Problems auf vielerlei Weise sukzessive erweitert werden können, um eine vollständige Lösung zu erzeugen, kann eine rekursive Implementation wie das obige Programm geeignet sein. Wie oben kann der Prozeß mit Hilfe eines Baums des erschöpfenden Durchsuchens beschrieben werden, dessen Knoten den partiellen Lösungen entsprechen. Eine Bewegung im Baum abwärts entspricht der Konstruktion einer vollständigeren Lösung; eine Bewegung im Baum nach oben entspricht einer »Rückkehr« zu einer zuvor erzeugten partiellen Lösung, von der aus es sich lohnen könnte, erneut vorwärts zu gehen.

Als weiteres Beispiel betrachten wir das Rucksack-Problem aus Kapitel 42. Wie dort erwähnt wurde, ist dieses Problem wesentlich komplizierter, wenn die Größen der Gegenstände keine ganzen Zahlen sind. Für dieses Problem bestehen die partiellen Lösungen natürlich in einer Auswahl von Gegenständen für den Rucksack, und Backtracking entspricht dem Entfernen eines Elements, um irgendeine andere Kombination auszuprobieren. Ein Ausästen des Suchbaumes durch Beseitigung von Symmetrien ist für dieses Problem sehr effizient, da die Reihenfolge, in der Gegenstände in den Rucksack gelegt werden, die Kosten nicht beeinflußt.

Wenn der beste Pfad gesucht wird (Problem des Handlungsreisenden), steht eine andere wichtige Methode des Ausästens zur Verfügung, bei der die Suche abgebrochen wird, sobald festgestellt worden ist, daß sie keinen Erfolg haben kann. Nehmen wir an, daß ein Pfad durch den Graph gefunden wurde, der die Kosten x verursacht. Dann ist es nutzlos, irgendeinen Pfad weiter zu verfolgen, für den die bisherigen Kosten größer als x sind. Dies kann einfach implementiert werden, indem keine rekursiven Aufrufe von visit realisiert werden, wenn die Kosten des aktuellen partiellen Pfades größer sind als die Kosten des bis dahin gefundenen besten vollständigen Pfades. Wenn wir eine solche Strategie verfolgen, können wir natürlich den Pfad mit den minimalen Kosten nicht übersehen.

Das Ausästen ist effizienter, wenn während der Suche schon frühzeitig ein Pfad mit niedrigen Kosten gefunden wird; ein Weg, um dies wahrscheinlicher zu machen, besteht darin, die dem aktuellen Knoten benachbarten Knoten entsprechend der Reihenfolge wachsender Kosten mit visit zu besuchen. Tatsächlich können wir noch besser vorgehen: Oft können wir eine Schranke für die Kosten aller vollständigen Pfade berechnen, die mit einem gegebenen partiellen Pfad beginnen. Für unser Beispiel können wir eine weit bessere Schranke für die Kosten eines jeden vollständigen Pfades, der mit dem aus den markierten Knoten gebildeten partiellen Pfad beginnt, berechnen, indem wir die Kosten des minimalen Spannbaumes der nicht markierten Knoten addieren. (Der Rest des Pfades ist ein Spannbaum für die nicht markierten Knoten; seine Kosten sind sicher nicht geringer als die Kosten des minimalen Spannbaumes dieser Knoten.)

Diese allgemeine Methode zur Berechnung von Schranken für partielle Lösungen zwecks Begrenzung der Anzahl der zu untersuchenden vollständigen Lösungen wird manchmal Branch-and-Bound (Verzweigen und Beschränken) genannt. Natürlich wird sie immer dann angewandt, wenn mit Pfaden Kosten verknüpft sind (und wir versuchen, Kosten zu minimieren). Normalerweise besteht unser Ziel bei solchen Problemen darin, bei der Suche nach einer Lösung eine beträchtliche Anzahl von Möglichkeiten auszuschließen. Es ist nicht ungewöhnlich, daß Dutzende von heuristischen Regeln der in den vorangegangenen Abschnitten beschriebenen Art angewandt werden, um zu vermeiden, daß ein falscher Pfad verfolgt wird.

Backtracking und Branch-and-Bound besitzen als allgemeine Methoden der Problemlösung ein sehr weites Anwendungsfeld. Zum Beispiel bilden sie die Grundlage für viele Programme, mit denen Spiele wie Schach oder Dame gespielt werden. In diesem Falle ist eine partielle Lösung irgendeine zulässige Stellung aller Figuren auf dem Spielbrett, und der Nachfolger eines Knotens in dem Baum des erschöpfenden Durchsuchens ist eine Stellung, die das Ergebnis irgendeines zulässigen Zuges sein kann. Im Idealfall wäre es am besten, wenn ein Programm ein erschöpfendes Durchsuchen durch alle Möglichkeiten realisieren und einen Zug wählen könnte, der unabhängig von der Reaktion des Gegners zum Sieg führt. Doch es gibt normalerweise viel zu viele Möglichkeiten, so daß gewöhnlich eine Suche mit Backtracking mit sehr komplizierten Regeln für das Ausästen vorgenommen wird, so daß nur »interessante« Stellungen untersucht werden. Methoden des erschöpfenden Durchsuchens werden auch für andere Anwendungen im Bereich der Künstlichen Intelligenz benutzt.

Im folgenden Kapitel betrachten wir verschiedene andere Probleme, die den bereits untersuchten ähneln und unter Anwendung dieser Methoden in Angriff genommen werden können. Die Lösung eines speziellen Problems erfordert die Entwicklung von komplizierten Kriterien, die benutzt werden können, um die Suche zu begrenzen. Wir haben nur wenige Beispiele der vielen Methoden angegeben, die für das Problem des Handlungsreisenden ausprobiert worden sind, und für andere wichtige Probleme sind ebenso ausgeklügelte Verfahren entwickelt worden.

Doch so kompliziert die Kriterien auch sein mögen, im allgemeinen gilt, daß die Laufzeit von Backtracking-Algorithmen exponentiell bleibt. Grob gesagt, wenn jeder Knoten in dem Suchbaum im Durchschnitt Alpha Nachfolger hat und die Länge des Lösungspfades N ist, so ist zu erwarten, daß die Anzahl der Knoten im Baum proportional zu AlphaN ist. Verschiedene Backtracking-Regeln entsprechen der Verringerung des Wertes von Alpha, der Anzahl der für jeden Knoten auszuprobierenden Möglichkeiten. Es lohnt sich, dafür einigen Aufwand zu treiben, da eine Verkleinerung von Alpha bedeutet, daß ein größeres Problem gelöst werden kann. Zum Beispiel kann ein Algorithmus, der in einer zu 1,1N proportionalen Zeit abläuft, ein etwa achtmal so großes Problem lösen wie ein Algorithmus, der eine zu 2N proportionale Zeit benötigt. Andererseits kann, wie wir bereits erwähnt haben, keiner von ihnen sehr umfangreiche Probleme bewältigen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]