Robert Sedgewick: Algorithmen

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


44. Erschöpfendes Durchsuchen



Digression: Erzeugung von Permutationen

Es ist ein interessantes Problem, ein Programm zu erstellen, das alle Möglichkeiten der Anordnung von N verschiedenen Elementen erzeugt. Ein einfaches Programm für dieses Problem der Erzeugung von Permutationen kann unmittelbar aus dem oben angegebenen Programm für das erschöpfende Durchsuchen für Graphen abgeleitet werden. Wie oben erwähnt wurde, muß dieses Programm, wenn es auf einen vollständigen Graph angewandt wird, versuchen, die Knoten dieses Graphen in allen möglichen Reihenfolgen zu besuchen. Wir erhalten alle Permutationen, indem wir die Knoten in der Reihenfolge markiert lassen, in der sie auf dem Suchpfad erscheinen, und jedesmal, wenn wir einen Pfad der Länge V haben, alle Marken der Knoten ausgeben:

    procedure visit(k: integer);
      var t: integer;
      begin
      id:=id+1; val[k]:=id;
      if id=V then writeperm;
      for t:=1 to V do
        if val[t]=0 then visit(t);
      id:=id-1; val[k]:=0
      end;

Dieses Programm läßt sich aus der obigen Prozedur ableiten, indem jede Bezugnahme auf die Adjazenz-Matrix beseitigt wird (da in einem vollständigen Graph alle Kanten vorhanden sind). Die Prozedur writeperm bewirkt einfach die Ausgabe der Elemente des Feldes val. Dies erfolgt jedesmal, wenn id = V gilt, was der Entdeckung eines vollständigen Pfades im Graph entspricht. (Tatsächlich kann das Programm noch etwas verbessert werden, indem man die for-Schleife wegläßt, wenn id = V gilt, da in diesem Falle bekannt ist, daß alle Einträge in val von null verschieden sind.) Um alle Permutationen der ganzen Zahlen von 1 bis N auszugeben, rufen wir diese Prozedur mit visit(0) auf, wobei id mit -1 und das Feld val mit null initialisiert wird. Dies entspricht der Einführung eines Pseudo-Knotens in dem vollständigen Graph und dem Prüfen aller Pfade im Graph, die im Knoten 0 beginnen. Wenn die Prozedur in dieser Weise für N = 4 aufgerufen wird, erzeugt sie die folgende Ausgabe (hier in zwei Spalten dargestellt):

1 2 3 4       2 3 1 4
1 2 4 3       2 4 1 3
1 3 2 4       3 2 1 4
1 4 2 3       4 2 1 3
1 3 4 2       3 4 1 2
1 4 3 2       4 3 1 2
2 1 3 4       2 3 4 1
2 1 4 3       2 4 3 1
3 1 2 4       3 2 4 1
4 1 2 3       4 2 3 1
3 1 4 2       3 4 2 1
4 1 3 2       4 3 2 1

Es muß eingeräumt werden, daß die Interpretation der Prozedur als Erzeugung von Pfaden in einem vollständigen Graph kaum erkennbar ist. Doch eine unmittelbare Untersuchung der Prozedur zeigt, daß sie alle N! Permutationen der ganzen Zahlen von 1 bis N erzeugt, indem sie zuerst alle (N - 1)! Permutationen mit der 1 an erster Stelle erzeugt (wobei sie sich rekursiv aufruft, um 2 bis N anzuordnen), dann alle (N - 1)! Permutationen mit der 1 an zweiter Stelle usw.

Sicher wäre es undenkbar, dieses Programm auch nur für N = 16 zu verwenden, da 16! > 250 ist. Trotzdem ist das Programm für die Untersuchung wichtig, da es die Grundlage für ein Backtracking-Programm für die Lösung eines beliebigen Problems, bei dem das Umordnen einer Menge von Elementen erforderlich ist, bilden kann.

Betrachten wir zum Beispiel das Euklidische Problem des Handlungsreisenden: Zu einer gegebenen Menge von N Punkten in der Ebene ist die kürzeste Tour zu finden, die alle Punkte verbindet. Da jede Reihenfolge der Punkte einer zulässigen Tour entspricht, kann man erreichen, daß das obige Programm ein erschöpfendes Durchsuchen nach der Lösung für dieses Problem realisiert, indem man es einfach dahingehend ändert, daß es genau wie oben die Kosten jeder Tour und das Minimum der Kosten der vollständigen Touren registriert. Dann kann die gleiche Methode vom Typ Branch-and-Bound wie oben angewandt werden, ebenso wie verschiedene heuristische Backtrackingverfahren, die für das Euklidische Problem spezifisch sind. (Zum Beispiel kann man leicht beweisen, daß sich die optimale Tour nicht selbst überkreuzen kann, so daß die Suche bei allen partiellen Pfaden, die sich selbst überkreuzen, abgebrochen werden kann.) Unterschiedliche heuristische Suchmethoden entsprechen unterschiedlichen Reihenfolgen der Anordnung der Permutationen. Solche Verfahren können viel Aufwand einsparen helfen, doch es bleibt immer noch eine enorme Menge an Arbeit übrig. Es ist ganz und gar nicht einfach, eine exakte Lösung für das Euklidische Problem des Handlungsreisenden zu finden, selbst wenn N einen so kleinen Wert wie 16 hat.

Ein anderer Grund, weshalb die Erzeugung von Permutationen von Interesse ist, besteht darin, daß eine Reihe ähnlich gearteter Prozeduren für die Erzeugung anderer kombinatorischer Objekte existiert. In einigen Fällen ist die Anzahl der erzeugten Objekte nicht ganz so groß wie im Falle der Permutationen, und solche Prozeduren können demzufolge in der Praxis für größeres N von Nutzen sein. Ein Beispiel hierfür ist eine Prozedur zur Erzeugung aller Möglichkeiten der Auswahl einer Teilmenge vom Umfang k aus einer Menge, die N Elemente enthält. Für großes N und kleines k ist die Anzahl dieser Möglichkeiten ungefähr proportional zu Nk. Eine derartige Prozedur könnte als Grundlage für ein Backtracking-Programm zur Lösung des Rucksack-Problems benutzt werden.


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