map Inhalt

 
 

Dieser Text von 1988 beschreibt einen wichtigen Algorithmus in einer Form, die zwar nicht immer zu einem optimal schnellen Programm führt, dafür aber so allgemein gehalten ist, daß sehr viele Probleme mit nur leichten Anpassungen bearbeitet werden können. Die Stellen, die im Bedarfsfall anzupassen sind, werden deutlich hervorgehoben. Die Hoffnung dabei ist, daß bei Verständnis der allgemeinen Form des Algorithmus es meist leicht möglich ist, für spezielle Probleme einen optimierten Algorithmus zu erstellen. Viel schwieriger ist es - wie oft in Büchern zu lesen - von einigen speziellen Beispielen auszugehen und womöglich auch noch auf eine Verallgemeinerung zu verzichten.

Der Text war lange Zeit mit nur geringen Modifikationen eine Grundlage für den Informatikunterricht in Jahrgangsstufe 13. Die beigefügten Programmbeispiele sind ehemals für TurboPascal 3 entwickelt worden und jetzt auch noch unter TurboPascal 7 lauffähig. Der Text in der alten Form für DOS ist jetzt in eine zeitgemäßere Form übertragen worden. Dabei ist der Text ergänzt und verbessert worden. Außerdem wurden weitere Beispiele beigefügt.



1. Darstellung eines Knotens aus einem Baum


Ein k-Baum mit n-Stufen (die Wurzel hat Stufe oder Tiefe 0), der nicht notwendigerweise vollständig sein muß, kann normalerweise den Lösungsraum eines dynamischen Problems darstellen. Je nach Art des Problems liegen dabei die Lösungen nur an den Blättern oder auch innen im Baum. In irgendeiner Weise muß man sich die Knoten merken können, um einerseits die gefundenen Lösungen aufzuzeichnen und andererseits den Weg durch den Baum organisieren zu können.


 

backtr1.gif (4 KB)



Hier ein 4-Baum der Tiefe N, also mit N Stufen, von denen aber nur die Stufen 0,1 und 2 dargestellt sind. Dieser Baum könnte zu einem N-stufigen Problem gehören, bei dem man N-mal aus 4 Möglichkeiten auswählen kann. Die Wahlmöglichkeiten sind die Kanten des Baumes (hier entsprechend markiert) und die Lösungen oder Teillösungen sind die Knoten, die hier nicht näher markiert sind.

Ein Knoten ist ein Vektor mit N-Komponenten. Zusätzlich benutzt man gern eine 0-te Komponente, um die Stufe des Knotens zu kennzeichnen. Diese Komponente gibt damit auch die Stelligkeit an, das heißt, den Index k, für den die Komponenten 1..k des Vektors definiert sind. Für ein Blatt ist die Stelligkeit dann N und für die Wurzel ist sie 0. Zum Beispiel für die oben im Baumdiagramm markierten Knoten A,B,C,D :


          Vektor     :  V = ( v0 , v1 , v2 , v3 , .... , vN )

          Knoten A :  V = ( 0, 0, 0, 0, .... , 0 )

          Knoten B :  V = ( 1, 2, 0, 0, .... , 0 )

          Knoten C :  V = ( 2, 2, 3, 0, .... , 0 )

          Knoten D :  V = ( 2, 4, 4, 0, .... , 0 )


Allgemein also:

          v0 = k heißt, daß v1 ... vk Komponenten definiert sind

          vi = q heißt, daß bei der i-ten Auswahl, Wert q gewählt wurde



2. Prädikate auf den Knoten des Baumes


Im Lösungsraum sind normalerweise einige Knoten Endpunkte, mit denen die Suche endet. Regelmäßig sind die Blätter auf Stufe N solche Endpunkte. Es können aber auch innere Knoten Endpunkte sein, wenn nämlich erkennbar wird, daß dieser Knoten und alle seine Nachfolger unmöglich noch zu einer Lösung werden können, weil bestimmte Bedingungen verletzt sind. Ein Algorithmus ist aber umso besser, je früher Endpunkte erreicht werden. Das bedeutet dann, daß ganze Teilbäume nicht mehr nach einer Lösung abgesucht werden müssen. Man muß solche Endpunkte, man nennt sie auch "tote" Knoten, erkennen können.

Je nach Problemstellung wird überhaupt nur irgendeine Lösung gesucht, eine optimale Lösung gesucht oder alle Lösungen gesucht. Jedenfalls braucht man ein Verfahren, um Lösungen zu erkennen.

Knoten, die keine Lösung sind und die nicht "tot" sind, nennt man "lebende" Knoten. Bei diesen geht die Suche nach Lösungen in deren Teilbäumen weiter.

Im Algorithmus werden mehrere Prädikate auf den Vektoren verwendet, die dann die oben geforderten Entscheidungen liefern. Es ist durchaus problemspezifisch wie man die Prädikate realisiert, ob einige Bedingungen zusammenfallen, ob womöglich noch einige Nebenbedingungen zu realisieren sind. Es kann sehr vernünftig sein, bestimmte Berechnungen an einem Vektor vorab durchzuführen, damit dann später bei den Prädikaten diese Rechnungen nicht doppelt geleistet werden müssen, was die Laufzeit ungünstig beinflussen würde.

Wenn man die Teillösung oder Lösung, dargestellt im Vektor V, als Kandidaten bezeichnet, dann werden folgende Prädikate, in Pascal durch Boolesche Funktionen realisiert, vorgeschlagen:

Kandidat_vollständig (V) := ( V ist ein Blatt im Baum aller Vektoren )

          Das ist im Normalfall die Situation, wenn der Vektor keine Nachfolger mehr haben kann und als Lösung
          in Betracht kommt. Meist hat der Vektor dann die Stelligkeit N.

Kandidat_lebend (V) := ( V erfüllt noch alle Bedingungen )

          Für Vektoren, die keine Endpunkte sind, wird hierdurch festgelegt, wann noch die Nachkommen
          zu einer Lösung führen können, also "leben". Die Sorgfalt, mit der dieses Prädikat formuliert
          wird, beeinflußt wesentlich wie schnell der Algorithmus wird.

Kandidat_neues_Optimum (V) := ( V ist Lösung und besser/gleich den zuvor gefundenen Lösungen )

          Wenn ein Problem keine Optimierungsaufgabe ist (z.B. 8-Damen) dann ist dieses Prädikat
          überflüssig. Sonst ist dieses Prädikat problemspezifisch zu definieren. Ob besser oder besser-gleich
          verwendet wird, hängt z.B. davon ab, ob nur eine Lösung oder alle gefunden werden sollen.



3. Der Algorithmus


Wenn man ein dynamische Programmierproblem so auffaßt und darstellt, wie in den Abschnitten 1 und 2 beschrieben und zuvor bereits bei Tiefen- und Breitensuche dargestellt, dann stellt sich Backtracking wie eine Tiefensuche dar, bei der lediglich eine erkannte sinnlose Suche unterlassen wird.

Sinnlos ist die Suche hinter "toten" Knoten. Dementsprechend kommt es also auf die oben angegebenen Prädikate an, die den Unterschied zwischen vollständiger Durchsuche nach dem Verfahren Tiefensuche und Backtracking ausmachen.

Dementsprechend wird fast der gleich rekursive Algorithmus wie bei der Tiefensuche auch für das Backtracking zu verwenden sein. Es müssen lediglich die Prädikate so eingebaut werden, daß bei einem "toten" Knoten abgebrochen werden kann.

In der Literatur findet man recht häufig diesen Algorithmus als Prozedur mit dem Namen "try", der auch jetzt verwendet werden soll. Das Diagramm vom Algorithmus Tiefensuche in der modifizierten Version stellt sich dann folgendermaßen dar:


backtr2.gif (7 KB)


Die problemspezifischen Details sind oben in rot hervorgehoben. Es sind besonders die oben angegebenen Prädikate und zusätzlich eine Prozedur zur Bewertung des Vektors, wo die Rechenarbeit zentralisiert wird. Problemspezifisch ist auch wie eine neue Lösung gespeichert wird. Hier macht es einen Unterschied, wenn alle Lösungen gesucht werden oder nur eine.

Vor dem Anwendung des rekursiven Algorithmus muß dann noch der Vektor mit Stelligkeit 0 initialisiert werden und das aktuelle Optimum auf einen unmöglichen Wert gesetzt werden, der schlechter als jede denkbae Lösung ist, damit der Algorithmus bei den Vergleichen funktioniert.



4. Ein Überdeckungsproblem


Gegeben ist ein Zielwert B und eine Anzahl von N Münzen mit gegebenen Münzwerten p1 bis pN. Gesucht ist eine Möglichkeit, den Zielwert B mit minimal vielen der gegebenen Münzen auszugeben.

gegeben:

          N, B   aus   N,   natürliche Zahlen

          P = ( p1 , .... , pN )   aus   NN,   Werte

Definitionen:

          X := ( x0 , x1 , x2 , .... , xN ) aus {1,..,N} x {0,1}N

          k := x0    aus   {1,..,N},   Stelligkeit

          Wert ( X ) := SUMME xi*pi  (von i=1 bis k)

          Anzahl ( X ) := SUMME xi  (von i=1 bis k)

          aktuelles_Optimum := Anzahl ( X )   wenn   X die zuletzt ermittelte Lösung ist

Prädikate:

          Kandidat_vollständig ( X ) := ( x0 = N )

          Kandidat_lebend ( X ) := ( Wert (X) < B )   und   ( Anzahl (X) < aktuelles_Optimum )

          Kandidat_neues_Optimum (X) := ( Wert (X) = B )   und   ( Anzahl (X) < aktuelles_Optimum )

gesucht:

          X   mit    Wert (X) = B    und    Anzahl (X) minimal

Die Prädikate lassen sich direkt in Pascal realisieren, "auswahlanfang" und "auswahlende" sind hier 0 und 1, das Speichern der Lösung ist ebenfalls leicht und direkt realisierbar und damit kann obiger Algorithmus direkt und ohne Tricks übernommen werden.

Für ein kleines Zahlenbeispiel kann man den Lösungsraum noch vollständig als Baum von Bitvektoren aufzeichnen. Mit 5 Münzen hätte der vollständige Baum 26-1 = 63 Vektoren insgesamt, davon 25 = 32 Blätter als Endpunkte. Wie wirksam Äste des Baumes als "tot" erkannt und abgeschnitten werden, hängt auch von den Daten ab und ist damit oft unvorhersehbar. Bei diesem Beispiel werden nur noch 39 Vektoren erzeugt, davon 16 Blätter.


backtr3.gif (7 KB)


Das entsprechende Programm ist als   BACKTR11.PAS   für TurboPascal gegeben. Das Programm können Sie hier als HTML-Text lesen. Es handelt sich aber nur um eine kleine, prizipielle Lösung der Aufgabe, die nur mit fest als Konstanten vorgegebenen Daten arbeitet. Eine alternative Lösung des gleichen Problems ist mit dem Algorithmus Branch & Bound zum Vergleich verfügbar.

Wenn die Aufgabenstellung so geändert wird, daß alle minimalen Kombinationen aus Münzen gesucht werden sollen, dann gibt es nur zwei Änderungen.

  • Wo in den Prädikaten < (kleiner) steht, dort muß jetzt <= (kleinergleich) stehen.
  • In der Prozedur Lösung_speichern wird jetzt mehr Aufwand zu treiben sein. Naheliegend ist es, jeden Lösungskandidaten in einer Liste zu speichern. Allerdings muß man auch gespeicherte Vektoren, die später durch bessere ungültig werden, herausfinden können.

Auch dieses Programm ist hier gegeben, als   BACKTR12.PAS   für TurboPascal. Sie können es ebenfalls als HTML-Text hier lesen. In diesem Programm wird ein Stack zur Speicherung der Lösungen benutzt. Das Programm ist außerdem so ergänzt, daß hier beliebige Daten (in vernünftigen Grenzen) eingegeben werden können.



5. Ein Färbungsproblem: pisces escheri


M.C.Escher hat auf einer Kugeloberfläche 12 Fische so angeordnet, daß sie eine Parkettierung der Oberfläche bilden. Die Kugel von Escher haben Doris Schattschneider und Wallace Walker zu einem Würfel deformiert, der mit dem gleichen Fischmuster bedeckt ist. Viermal stoßen drei Fische jeweils mit den Schwanzflossen zusammen und viermal stoßen drei Fische jeweils mit der Rückenflosse zusammen. Dies raffinierte Muster muß man sehen !

Das Muster soll jetzt so gefärbt werden, daß jeder Fisch eine Farbe erhält und benachbarte Fische unterschiedliche Farben haben.

Dies Problem erscheint recht verschieden im Vergleich mit dem oben beschriebenen Überdeckungsproblem. Während oben ein Binärbaum aus Bitvektoren als Lösungsraum in Betracht kommt, wird hier ein 4-Baum zweckmäßig sein. Für jeden Fisch kann man unter 4 Farben auswählen.

Beim Überdeckungsproblem waren die Berechnungen leicht und trivial. Hier ist das nur verbal einfach zu beschreiben "kein Farbkonflikt", aber in der Realisierung etwas umständlicher. Erstmal muß die räumliche Anordnung der Fische mit der Nachbarschaftsbeziehung erfaßt werden und dann muß man sich überlegen, wie man die Farben überprüft. Hier wird es sicherlich verschiedene brauchbare Ansätze geben. Der folgende Ansatz zeigt, daß auch für dieses Problem der oben allgemein beschriebene Algorithmus greift.

gegeben:

          Farbanzahl    aus   N

          N = Fischanzahl    aus   N      ( jeder Fisch ist eindeutig bezeichnet )

          F = { 1, 2, ..., N }     ( Menge der Fische )

          C = { 1, ..., Farbanzahl}     ( Menge der Farben )

          für alle j aus F:   Ij := { i aus F | i<>j und Fischi berührt Fischj }      (Nachbarschaftsbeziehung)

Definitionen:

          X := ( x0 , x1 , x2 , .... , xN ) aus F x CN

          k := x0     aus   { 0, 1, ..., N }

          Farbkonflikt (X) := es gibt ein i aus {1..k-1}   mit:   ( xi = xk    und   i aus Ik )

Prädikate:

          Kandidat_vollständig ( X ) := ( k = N )

          Kandidat_lebend ( X ) := NOT Farbkonflikt (X)

           Kandidat_neues_Optimum (X) := NOT Farbkonflikt (X)

gesucht:

          L := { X | X0     und     NOT Farbkonflikt (X) }

Die Bezeichnung muten teilweise etwas gezwungen an, aber das ist hier nur der Fall, damit der oben vorgestellte Algorithmus TRY ohne Weiteres verwendet werden kann.

Der Raum der Lösungen ist hier als 4-Baum mit 12 Ebenen gegeben. Die allermeisten Vektoren in diesem großen Baum haben einen Farbkonflikt und dort wird dann die Lösungssuche abgebrochen. Ein Teil des linken Randes des Baumes wird hier dargestellt, um eine Vorstellung zu geben, wie die Lösungen gefunden werden.


backtr4.gif (6 KB)


Das resultierende TurboPascal-Programm   BACKTR2.PAS   kann hier als HTML-Text gelesen werden. Ebenso wie die anderen Programmbeispiele kann es auch als Pascal-Quelltext und als EXE-Datei geladen werden.



6. Das klassische Rucksackproblem


Das Rucksackproblem ist nur ganz wenig aufwendiger als das Überdeckungsproblem aus Kapitel 4. Es kann ganz ähnlich implementiert werden. Wenn man das Überdeckungsproblem als Vorbild nimmt, hat man nur einen geringen Änderungsaufwand.

Gegeben ist ein Rucksack mit der Tragfähigkeit B. Weiter sind N Gegenstände mit Werten und Gewichten gegeben. Nun sollen Gegenstände ausgewählt werden, die in der Summe einen maximalen Wert ergeben, aber deren Gesamtgewicht die Tragfähigkeit des Rucksacks nicht überschreitet.

gegeben:

          N, B   aus   N,   natürliche Zahlen

          P = ( p0 , p1 , .... , pN )   aus   NN,   Werte

          W = ( w0 , w1 , .... , wN )   aus   NN,   Gewichte

Definitionen:

          Wert ( X ) := SUMME xi*pi  (von i=1 bis k)

          Gewicht ( X ) := SUMME xi*wi  (von i=1 bis k)

          aktuelles_Optimum := Wert ( X )   wenn   X die zuletzt ermittelte Lösung ist

Prädikate:

          Kandidat_vollständig ( X ) := ( x0 = N )

          Kandidat_lebend ( X ) := ( Gewicht (X) <= B )

          Kandidat_neues_Optimum (X) := ( Gewicht (X) <= B )   und   ( Wert (X) > aktuelles_Optimum )

gesucht:

          X   mit   Gewicht (X) <= B    und    Wert (X) maximal

Das resultierende TurboPascal-Programm   BACKTR3.PAS   kann hier als HTML-Text gelesen werden oder auch als Pascal-Quelltext und als EXE-Datei geladen werden.



7. Ein Färbungsproblem: bunte Reihe


Auch zu diesem Kapitel gibt es das Beispielprogramm   BACKTR4.PAS,   das hier als HTML-Text gelesen werden kann. Das ist umso wichtiger, weil das Problem hier nicht mehr so ausführlich diskutiert wird.

Das Problem war einmal als Aufgabe in der ersten Runde des Bundeswettbewerbs Informatik gegeben worden.

Gegeben sind bunte Wimpel in verschiedenen Farben, die so in einer Reihe angeordnet werden sollen, daß nie benachbarte Wimpel die gleiche Farbe haben. Vorgegeben wird die Anzahl der Farben und wieviel Wimpel in jeder Farben vorhanden sind.

In der Aufgabenstellung sind noch Zusätze gegeben, die es erzwingen, daß alle möglichen Lösungen ermittelt werden müssen. Das sind jedoch nur sekundäre Probleme, die hier nicht weiter diskutiert werden sollen.

Die Dimension N des Problems ergibt sich aus Addition der Anzahlen der Wimpel in jeder Farbe, das ist dann sie Anzahl der Wimpel insgesamt.

An manchen Stellen ähnelt das Problem dem Färbungsproblem pisces escheri. Hier wird jedoch für jeden Knoten ein Vorrat von noch vorhandenen Farben mitgeführt.

Ein Problem ist bisher noch nicht diskutiert worden. Die Vektoren wurden sukzessive aufgebaut und für jede neue Stelle ein neuer rekursiver Aufruf getätigt. Beim Abbau der Rekursion stand dann immer wieder der alte Vektor zur Verfügung, weil er nur bis zur alten Stelligkeit betrachtet wurde. Die Stellen dahinter waren eventuell verändert, das fiel aber nicht in Betracht. Das war einfach und bequem. Allgemein muß man aber eine Struktur, die man beim rekursiven Aufruf aufgebaut hat, auch wieder restaurieren. Das ist hier mit dem Vorrat an Farben der Fall.

Als praktikable Lösung bietet sich an eine lokale Variable zu definieren, die immer nur in der entsprechenden Inkarnation der rekursiven Prozedur lebt und deshalb bei Tiefersteigen nicht verändert wird. Das Schema dafür sieht folgendermaßen aus:

   PROZEDUR  try (stufe: Integer; vektor:...; datum: ...);
   VAR  neudatum: ...;
   BEGIN
     ...
     neudatum:=datum;                 {die vorigen Werte werden übernommen}
     neudatum:=....;                  {die Werte werden geändert}
     ...
     try (stufe+1, vektor, neudatum); {mit den neuen Daten gehts weiter,}
     ...                              {die alten bleiben.}
   END;

Damit ist dann der Algorithmus try ohne weitere Tricks anwendbar. Das resultieren Programm PAS  BACKTR4.PAS   enthält nur noch einige Ein-/und Ausgabeprozeduren, damit es zu einer vollständigen Lösung der gestellten Aufgabe wird.



8. Das Problem des Handlungsreisenden


Auch hier gibt es ein Beispielprogramm   BACKTR5.PAS,   das hier als HTML-Text gelesen werden kann.

Das Problem des Handlungsreisenden - travelling salesman - ist sehr bekannt. Es kann in verschiedenen Variationen formuliert werden. Hier sind N Orte gegeben und die Entfernungen zwischen ihnen. Nicht notwendig ist jeder Ort mit jedem verbunden. Hier sind allerdings alle Verbindungen symmetrisch. Wäre das nicht der Fall, gäbe es z.B. Einbahnstraßen. Gesucht ist nun eine Rundreise, die alle Orte besucht und zum Ausgangspunkt zurückkehrt und die eine minimale Gesamtlänge hat.

Vordergründig ähnelt das Problem keinem der oben als Beispiel gegebenen. Tatsächlich läßt es sich aber auch problemlos mit dem Algorithmus try bearbeiten. Es ist aber - besonders, wenn viele Orte verbunden sind - ziemlich aufwendig.

Um die Berechnung der Streckenlänge einfacher zu gestalten, wir hier jedem Vektor schon seine Gesamtlänge mitgegeben, der Vektor wird also um eine weitere Komponente erweitert. Das hat zur Folge, daß bei Rückkehr aus der Rekursion die veränderte Länge wieder auf den vorigen Wert gesetzt werden muß. Deshalb ist hier für den Vektor ebenfalls das Verfahren anzuwenden, das in Kapitel 7 dargestellt wurde.




HTML-Texte: Münzen 1 Münzen 2 ADT Stack Escher knapsac bunte Reihe salesman HAUPTTEXT
Paket mit Pascal-Dateien laden: BackPac.Zip   (47 K)

zur Informatik-Leitseite


© HMO, Neubearbeitung Januar 1998