Robert Sedgewick: Algorithmen

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


44. Erschöpfendes Durchsuchen



Erschöpfendes Durchsuchen in Graphen

Wenn der Handelsreisende nur zwischen bestimmten Städtepaaren reisen kann (zum Beispiel wenn er mit dem Flugzeug reist), läßt sich das Problem unmittelbar mit Hilfe eines Graphen modellieren: Für einen gegebenen gewichteten (möglicherweise gerichteten) Graph möchten wir den kürzesten einfachen Zyklus finden, der alle Knoten verbindet.

Dies erinnert sofort an ein anderes Problem, das einfacher zu sein scheint: Falls ein ungerichteter Graph gegeben ist, gibt es dann irgendeinen Weg, um alle Knoten mit Hilfe eines einfachen Zyklus zu verbinden? Das heißt, können wir, wenn wir in einem bestimmten Knoten starten, alle anderen Knoten »besuchen« und zu dem Anfangsknoten zurückkehren, wenn jeder Knoten im Graph genau einmal besucht werden soll? Diese Aufgabe ist als Problem des Hamilton-Zyklus bekannt. Im folgenden Kapitel werden wir sehen, daß es in einem streng technischen Sinne zu dem Problem des Handelsreisenden äquivalent ist.

In den Kapiteln 29 und 31 betrachteten wir eine Reihe von Verfahren für das systematische Besuchen aller Knoten eines Graphen. Für diese Algorithmen war es möglich, die Berechnung so zu organisieren, daß jeder Knoten genau einmal besucht wird, und dies führte zu sehr effizienten Algorithmen. Für das Problem des Hamilton-Zyklus ist eine solche Lösung nicht offensichtlich; es ist allem Anschein nach erforderlich, jeden Knoten viele Male zu besuchen. Für die anderen Probleme konstruierten wir einen Baum; wenn bei der Suche eine »Sackgasse« erreicht wurde, konnten wir sie wieder aufnehmen, indem wir einen anderen Teil des Baumes untersuchten. Für das vorliegende Problem muß der Baum eine spezielle Struktur (Zyklus) aufweisen; wenn wir im Verlaufe der Suche feststellen, daß der erzeugte Baum kein Zyklus sein kann, müssen wir zurückgehen und einen Teil von ihm neu konstruieren.

Abbildung 44.1
Abbildung 44.1 Eine Instanz des Problems des Handlungsreisenden.

Um einige der dabei auftretenden Fragen zu illustrieren, betrachten wir das Problem des Hamilton-Zyklus für den in Abbildung 44.1 dargestellten Graphen. Bei einer Tiefensuche werden die Knoten in diesem Graph in der Reihenfolge A B C E F D G H I K J L M besucht (wobei eine Darstellung mit Hilfe einer Adjazenz-Matrix oder einer sortierten Adjazenz-Liste vorausgesetzt wird). Dies ist kein einfacher Zyklus, und um einen Hamilton-Zyklus zu finden, müssen wir daher einen anderen Weg suchen, wie die Knoten besucht werden können. Es erweist sich, daß wir mit einer einfachen Modifikation der Prozedur visit alle Möglichkeiten systematisch ausprobieren können:

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

Anstatt jeden Knoten, den sie berührt, mit einer von Null verschiedenen Eintragung in val zu markieren, »räumt« diese Prozedur »hinter sich auf« und hinterläßt id und das Feld val genau so, wie sie sie vorgefunden hat. Die einzigen markierten Knoten sind die Knoten, für die visit nicht beendet worden ist, und diese Knoten entsprechen genau einem einfachen Pfad der Länge id im Graph, der vom Anfangsknoten zu dem gerade besuchten Knoten führt. Um einen Knoten mittels visit zu besuchen, besuchen wir einfach alle nicht markierten benachbarten Knoten (markierte würden keinem einfachen Pfad entsprechen). Die rekursive Prozedur prüft alle einfachen Pfade im Graph, die in dem Anfangsknoten beginnen.

Abbildung 44.2 zeigt die Reihenfolge, in der Pfade durch die obige Prozedur geprüft werden. Jeder Knoten im Baum entspricht einem Aufruf von visit; daher sind die Nachfolger jedes Knotens benachbarte Knoten, die zum Zeitpunkt des Aufrufs nicht markiert sind. Jeder Pfad in dem Baum von einem Knoten zur Wurzel entspricht einem einfachen Pfad im Graph. Der erste geprüfte Pfad ist daher A B C E F D. Zu diesem Zeitpunkt sind alle zu D benachbarten Knoten markiert (haben von Null verschiedene Einträge in val), so daß visit für D die Markierung von D löscht und zurückkehrt. Danach löscht visit für F die Markierung von F und kehrt zurück. Danach bewirkt visit für E das Ausprobieren von G, was zum Ausprobieren von H führt usw., wodurch sich schließlich der Pfad A B C E G H I K J L M ergibt. Zu beachten ist, daß bei der Tiefensuche Knoten, nachdem sie besucht wurden, markiert bleiben, während beim erschöpfenden Durchsuchen Knoten viele Male besucht werden. Das »Löschen der Markierung« der Knoten bewirkt, daß sich das erschöpfende Durchsuchen wesentlich von der Tiefensuche unterscheidet (obwohl das Programm recht ähnlich ist); der Leser sollte sich den Unterschied unbedingt klarmachen.

Abbildung 44.2
Abbildung 44.2 Erschöpfendes Durchsuchen.

Wie bereits erwähnt wurde, ist id die aktuelle Länge des gerade ausprobierten Pfades, und val[k] ist die Position des Knotens k auf diesem Pfad. Daher können wir erreichen, daß die obige Prozedur visit die Existenz eines Hamilton-Zyklus prüft, indem wir sie prüfen lassen, ob eine Kante von k nach 1 existiert, wenn val[k] = V gilt. In dem obigen Beispiel existiert nur ein Hamilton-Zyklus, der in dem Baum zweimal erscheint, wobei er in beiden Richtungen durchlaufen wird (es gibt drei weitere Pfade der Länge V). Man kann erreichen, daß das Programm das Problem des Handelsreisenden löst, indem man die Länge des aktuellen Pfades in dem Feld val registriert und dann das Minimum der Längen der gefundenen Hamilton-Zyklen registriert.


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