8Entwurf von Algorithmen

Der Entwurf von Algorithmen und damit von Programmen ist eine konstruktive und kreative Tätigkeit, die den Entwerfer immer wieder vor neue Herausforderungen stellt – neben der reinen Funktionalität sind ja auch Fragen der Laufzeitkomplexität und andere, nichtfunktionale Anforderungen zu berücksichtigen. Wir hatten ja bereits gesehen, dass die automatische Ableitung eines optimalen Algorithmus aus einer Beschreibung der Anforderungen prinzipiell nicht automatisierbar ist.

Inhalt dieses Abschnitts kann es daher nur sein, anhand von Beispielen Prinzipien des Entwurfs und einige typische Muster für Algorithmen vorzustellen. Derartige »best practice«-Beispiele helfen dem Entwerfer, brauchbare Erfahrungen für das Angehen neuer Probleme zu sammeln. Nach einer allgemeinen Diskussion von Entwurfsprinzipien werden wir vier typische Algorithmenmuster vorstellen: Greedy-Algorithmen, Divide-and-Conquer, Backtracking und dynamische Programmierung.

8.1Entwurfsprinzipien

In den vorherigen Kapiteln haben wir quasi nebenbei schon einige Techniken angewendet, die beim praktischen Entwurf von Programmen hilfreich sind. Drei der wichtigsten dieser Techniken werden wir noch einmal kurz rekapitulieren: die schrittweise Verfeinerung, den Einsatz von Algorithmenmustern und die Problemreduzierung durch Rekursion.

8.1.1Schrittweise Verfeinerung

Schrittweise Verfeinerung

Die Vorgehensweise der schrittweisen Verfeinerung hatten wir bereits bei der ersten Diskussion des intuitiven Algorithmenbegriffs anhand von Pseudocode-Algorithmen kennen gelernt. Diese Verfeinerung basiert auf folgendem Ablauf:

1. Beginne mit einer kurzen Folge abstrakter Lösungsschritte (d.h. etwa Anweisungen in Pseudocode)
2. Verfeinere die Anweisungen Schritt für Schritt in detailliertere Anweisungen, zunächst in verfeinerten Pseudocode und letztendlich in konkrete Algorithmenschritte
3. Fertig, wenn alle Anweisungen in der Zielsprache (z.B. Java) formuliert sind

In der Terminologie der Programmierung entspricht der Verfeinerungsschritt der Formulierung von Algorithmen auf einer abstrakten Stufe, bei der statt ausführbarer Einzelschritte Prozeduraufrufe eingesetzt werden, deren Bedeutung dann durch die Ausprogrammierung der Prozedur konkretisiert wird. Betrachten wir hierzu ein einfaches Beispiel.

Beispiel 8.1 Durch schrittweise Verfeinerung zur Berechnung des Medians

Es soll der Median – der mittlere Wert einer geordneten Folge von Elementen (x₁, x₂, …, x_n) – ermittelt werden. Der Median ist definiert als:

Für die Folge

1 2 6 8 9

ist offensichtlich 6 der Median. Zur Umsetzung in ein Programm durch Verfeinerung gehen wir schrittweise vor:

1. Schritt: Wir bleiben zunächst bei einer Pseudocode-Notation:

2. Schritt: Nun verfeinern wir diese recht abstrakte Anweisung zu vier Anweisungen:

3. Schritt: Jede dieser Anweisungen muss jetzt weiter verfeinert werden und könnte beispielsweise zunächst durch einen Prozeduraufruf ersetzt werden. Wir konzentrieren uns im Moment jedoch vor allem auf die dritte Anweisung:

4. Schritt: Nun können wir beginnen, den Pseudocode durch Java-Code zu ersetzen. Für erste Tests verzichten wir auf die Eingabe der Folge und geben stattdessen ein festes Feld vor. Für die Sortierung des Feldes können wir auf unsere QuickSort-Implementierung aus Abschnitt 5.2.6 zurückgreifen.

5. Schritt: Schließlich kann noch eine Eingabe implementiert werden:

Dieses einfache Beispiel illustriert bereits einige Aspekte der schrittweisen Verfeinerung: die Frage der Notation (wie lange Pseudocode verwenden), aber auch die Notwendigkeit von Entwurfsentscheidungen (Verwendung von Prozeduren, welche Algorithmen). Zwar lassen sich hierfür keine festen Regeln angeben, aber einige Tipps sind eventuell hilfreich:

• Es sollte so lange wie möglich während der Verfeinerung eine geeignete Notation (Pseudocode, natürliche Sprache) genutzt werden (so abstrakt wie möglich, so detailliert wie nötig).
• Jeder Verfeinerungsschritt ist mit einer Entwurfsentscheidung verbunden, die spätere Eigenschaften des Programms wie Geschwindigkeit oder Speicherplatzbedarf beeinflusst. Das bedeutet, dass unter Umständen derartige Entscheidungen später revidiert werden müssen. Im obigen Beispiel ist dies etwa die Wahl des Sortierverfahrens oder auch die Entscheidung, dass die Eingabe für das Programm eine bereits sortierte Folge sein muss.
• Neben dem Ablauf müssen auch die zu verarbeitenden Daten schrittweise verfeinert werden, etwa Kaffee zu Kaffeepulver + Wasser oder der abstrakte Begriff der Folge zu einem Feld von int-Werten.

Betrachten wir abschließend noch ein komplexeres Fallbeispiel: das in Abschnitt 2.5.2 eingeführte Tic-Tac-Toe-Spiel. Ausgangspunkt unseres Entwurfs ist das Struktogramm aus Abbildung 8–1 mit einem ersten groben Spielablauf: Solange das Spiel nicht beendet ist (was in der Variablen fertig erfasst wird, die initial den Wert false hat), wird in der Hauptschleife zunächst geprüft, ob noch ein Feld frei ist. Ist dies der Fall, wird ein Zug ausgeführt, andernfalls wird die Schleife verlassen.

Abb. 8–1 Spielablauf für Tic Tac Toe

Im nächsten Schritt können wir die Ausführung eines Spielzugs verfeinern (Abbildung 8–2). Hierbei wird zunächst ein Zug eingegeben (vom Spieler oder dem Computer). Danach wird geprüft, ob dieser Zug gültig ist, und anschließend, ob ein Spieler gewonnen hat. In diesem Fall wird der Variablen fertig der Wert true zugewiesen und die Hauptschleife beendet.

Programm 8.1 Java-Umsetzung des Spielablaufs

Abb. 8–2 Ausführung eines Spielzugs

Dieser Ablauf kann nun weiter verfeinert werden – wir wechseln dazu die Notation und übertragen das Programm nach Java (Programm 8.1). Dabei bietet es sich wieder an, zunächst Methoden für die weiter zu verfeinernden Schritte einzusetzen. Weiterhin müssen wir uns auch Gedanken über die Datenstrukturen machen: Hierzu wählen wir ein Feld von char-Werten für das Spielfeld.

Unser nächster Schritt ist die Verfeinerung der Methode freiesFeld (prüfen, ob ein Element in spielfeld noch den Wert ’ ’ hat), der Eingabe eines Zuges sowie des Tests auf Sieg. Letzteres kann direkt aus unserem Struktogramm 8–2 übernommen werden, wobei wir auch hier zunächst wieder Methoden für komplexere Aufgaben (Test, Spielerwechsel) einsetzen:

Wie in Abschnitt 3.6.1 beschrieben, bietet es sich an, die Tests für Zeilen, Spalten und Diagonalen jeweils in eigenen Code-Abschnitten (z.B. Methoden) zu realisieren, so dass die Methode gewonnen wie folgt verfeinert werden kann:

Diese Methoden können nun einfach wie in Abschnitt 3.6.1 beschrieben implementiert werden. Auch die Verfeinerung der weiteren Schritte sei an dieser Stelle dem Leser überlassen.

8.1.2Einsatz von Algorithmenmustern

Musterlösungen für Problemklassen

Die Idee des Einsatzes von Algorithmenmustern besteht darin, generische algorithmische Muster für bestimmte Problemklassen zu entwickeln und diese dann jeweils an eine konkrete Aufgabe anzupassen. Man versucht also für eine allgemeine Problemklasse, zum Beispiel das Finden einer kostenoptimalen Lösung in einem großen Lösungsraum (etwa das Finden kürzester Wege), eine Muster-Implementierung zu finden und diese dann an das konkrete Problem anzupassen. Diese Grundidee kann man auf verschiedene Weise konkretisieren:

• Das Lösungsverfahren wird an einem möglichst einfachen Vertreter der Problemklasse vorgeführt und dokumentiert. Der Entwerfer versteht die Problemlösungsstrategie und überträgt diese auf sein Programm.
• Eine Bibliothek von Mustern (»Design Pattern«, »best practice«-Strategien) wird genutzt, um einen abstrakten Programmrahmen zu generieren. Die freien Stellen dieses Programmrahmens werden dann problemspezifisch ausgefüllt.
• Moderne Programmiersprachen benutzen parametrisierte Algorithmen und Vererbung mit Überschreiben, um Algorithmenmuster als lauffähige Programme zur Verfügung zu stellen und diese dann an ein konkretes Problem anzupassen.

Im Verlauf dieses Kapitels werden wir einige derartige Muster kennen lernen und ebenfalls deren Übertragbarkeit auf verwandte Probleme behandeln.

8.1.3Problemreduzierung durch Rekursion

Rekursive Algorithmen sind ein für die Informatik spezifischer Lösungsansatz, der in den klassischen Ingenieurwissenschaften nicht entwickelt werden konnte – ein mechanisches Bauteil kann physikalisch nicht sich selbst als Bauteil enthalten, während ein Programm sich durchaus selbst aufrufen kann. Rekursive Programmierung ist daher in der Regel nicht aus dem Alltagswissen ableitbar, sondern muss als Technik erlernt und geübt werden.

Prinzipiell haben wir in den Kapiteln über theoretische Grundlagen gesehen, dass auch formale Algorithmenmodelle ohne rekursive Aufrufe bereits berechnungsuniversell sind. Man könnte daher meinen, Rekursion als solche ist eigentlich nicht notwendig. Tatsächlich formen Compiler rekursive Programme in nichtrekursiven Maschinencode um.

Rekursives Anwenden einer Problemlösungsstrategie

Allerdings ist das rekursive Anwenden einer Problemlösungsstrategie auf Teilprobleme ein Algorithmenmuster, mit dem man bestimmte Problemklassen einfach realisieren kann.

Dieses Prinzip der rekursiven Vereinfachung des Problems hatten wir bereits in Abschnitt 2.1 anhand der Türme von Hanoi kennen gelernt. Dies heißt nicht, dass rekursive Algorithmen immer die besten Lösungen sind. Tatsächlich löst folgender nichtrekursiver Algorithmus das »Türme von Hanoi«-Problem offensichtlich viel einfacher:

Allerdings versuche man besser nicht formal zu beweisen, dass diese Variante tatsächlich korrekt ist.

Als Fazit werden wir anhand einiger Algorithmenmuster sehen, wie Rekursion beim Entwurf von Algorithmen sinnvoll eingesetzt werden kann. Allerdings sollte uns dies nicht den Blick auf einfache, nichtrekursive Verfahren verbauen.

8.2Algorithmenmuster: Greedy

Das erste von uns betrachtete Algorithmenmuster sind die Greedy-Algorithmen. Greedy steht hier für gierig. Das Prinzip gieriger Algorithmen ist es, in jedem Teilschritt so viel wie möglich zu erreichen. Wir werden das Prinzip an einem kleinen Beispiel verdeutlichen und danach ein realistisches Problem und dessen »gierige« Lösung behandeln.

8.2.1Greedy-Algorithmen am Beispiel

Als Beispiel für einen Greedy-Algorithmus betrachten wir die Herausgabe von Wechselgeld mit möglichst wenig Münzen. Es soll auf Geldbeträge (unter 1 Euro) Wechselgeld herausgegeben werden. Zur Verfügung stehen ausreichend Münzen mit den Werten 50, 10, 5, 2 und 1 Cent. Das Wechselgeld soll aus so wenig Münzen wie möglich bestehen. Als Beispiel sollen bei einem Wechselgeld von 78 Cent insgesamt 6 Münzen herausgegeben werden, da 78 = 50+2·10+5+2+1.

Wie kann ein Greedy-Algorithmus dieses Problem lösen? Er nimmt jeweils die größte mögliche Münze, um schnell (gierig) zum Ziel zu kommen:

Greedy-Algorithmus zur optimalen Geldrückgabe

Wie man sich leicht an mehreren Beispielen klar machen kann, berechnet Greedy tatsächlich jeweils die optimale Geldrückgabe.

Greedy-Algorithmen berechnen lokales Optimum

Im allgemeinen Fall muss das allerdings nicht gelten: Greedy-Algorithmen berechnen jeweils ein lokales Optimum in jedem Schritt und können daher eventuell ein globales Optimum verpassen!

Zur Verdeutlichung modifizieren wir unser Geldrückgabebeispiel, indem wir nun Münzen mit den Werten 11, 5, und 1 annehmen. Unser Zielwert sei 15. Greedy würde als Ergebnis fünf Münzen herausgeben (für 15 = 11 + 1 + 1 + 1 + 1), die tatsächliche optimale Münzenanzahl wäre aber drei für 15 = 5 + 5 + 5.

Allerdings entsprechen in vielen Fällen derartige lokale Optima den globalen bzw. reicht ein lokales Optimum aus. Vor dem Einsatz von Greedy-Algorithmen ist also jeweils zu prüfen, ob die gierige Vorgehensweise tatsächlich das Optimum berechnet bzw. ob das Problem auch mit suboptimalen Lösungen adäquat bearbeitet werden kann. Für suboptimale Lösungen spricht oft die gute Laufzeitkomplexität von Greedy-Verfahren im Vergleich zu anderen Optimierungsverfahren, die in der Regel exponentiellen Aufwand aufweisen.

Durch Greedy-Verfahren lösbare Probleme

Bevor wir Greedy-Algorithmen an einem weiteren Beispiel vorführen, skizzieren wir kurz die Problemklasse, für die sie angewendet werden können:

1. Gegeben ist eine feste Menge von Eingabewerten.
2. Es gibt eine Menge von Lösungen, die aus Eingabewerten aufgebaut sind.
3. Alle Lösungen lassen sich schrittweise aus partiellen Lösungen, beginnend bei der leeren Lösung, durch Hinzunahme von Eingabewerten aufbauen.
4. Es existiert eine Bewertungsfunktion für partielle und vollständige Lösungen.
5. Gesucht wird die bzw. eine optimale Lösung bezüglich der Bewertungsfunktion.

Es sei noch einmal daran erinnert, dass Greedy-Algorithmen nicht für alle derartigen Probleme tatsächlich die optimale Lösung berechnen.

8.2.2Greedy: Optimales Kommunikationsnetz

Als Problemstellung ist die Aufgabe gegeben, eine möglichst billige Vernetzung von vorgegebenen Stationen mit einem Kommunikationsnetz zu erreichen. Prinzipiell kann jede Station mit jeder anderen direkt verbunden werden, aber zu unterschiedlichen Kosten. Genauer können wir das Problem wie folgt konkretisieren: Zwischen n Knotenpunkten P₁, … , P_n soll ein möglichst billiges Kommunikationsnetz geschaltet werden, so dass jeder Knotenpunkt mit jedem anderen verbunden ist, ggf. auf einem Umweg über andere Knotenpunkte.

Vorgabe für Kommunikationsnetz

Bekannt sind alle Kosten d_i,j für die direkte Verbindung zwischen P_i und P_j, 1 ≤ i, j ≤ n und i ≠ j. Alle Kosten d_i,j seien verschieden und größer als null. Diese Verschiedenheit der Kosten sorgt für eine eindeutige Lösung, kann aber auch aufgegeben werden, wenn ein nichtdeterministisches Ergebnis akzeptiert wird. Die Forderung nach der Vollständigkeit des Verbindungsnetzes kann man dadurch aufweichen, dass man eventuelle nichtexistierende Verbindungen als »virtuelle« Verbindungen mit sehr hohen Kosten hinzufügt. Es gilt natürlich d_i,j = d_j,i. Als Beispiel für eine Eingabe für ein zu konstruierendes Kommunikationsnetz betrachten wir die Verbindungen in Abbildung 8–3.

Man kann sich leicht überlegen, dass ein minimales Kommunikationsnetz einen aufspannenden Baum darstellen muss, also eine Menge von Verbindungen, die alle Knoten verbindet und keinen Zyklus enthält – gäbe es nämlich einen derartigen geschlossenen Kreis, könnte man ein billigeres Kommunikationsnetz durch Entfernen einer Kante aus diesem Zyklus berechnen. Gesucht ist somit der billigste aufspannende Baum, wobei die Gesamtkosten als die Summe der Kantenkosten definiert sind.

Abb. 8–3 Eingabe für Kommunikationsnetz

Greedy-Algorithmus zur Berechnung des minimalen Kommunikationsnetzes

Basierend auf diesen Vorüberlegungen kann man eine erste Greedy-Variante zur Berechnung eines minimalen Kommunikationsnetzes wie folgt angeben:

Mit K_n wird hierbei der vollständige Graph mit n Knoten bezeichnet – die while-Bedingung ist also ein Test, ob alle Knoten erfasst sind. Da wir die Anzahl Kanten im aufspannenden Baum als n − 1 bestimmen können (jeder größere Teilgraph muss einen Zyklus enthalten, jeder kleinere kann nicht n Knoten verbinden), kann die while-Schleife auch durch ein for-Konstrukt ersetzt werden.

Man beachte, dass natürlich noch eine Verfeinerung der Suche nach der billigsten Kante notwendig ist. Darauf werden wir im nächsten Teilabschnitt zurückkommen. Das Ergebnis dieses Algorithmus ist das Kommunikationsnetz, das in Abbildung 8–4 dargestellt ist.

8.2.3Verfeinerung der Suche nach billigster Kante

Das vorgestellte Greedy-Muster reicht aus, um das Greedy-Prinzip bei der Berechnung eines minimalen Kommunikationsnetzes zu erläutern. Wir nutzen nun die Verfeinerung des Teilschrittes

Abb. 8–4 Errechnetes Kommunikationsnetz

um erstens nochmals auf das Entwurfsprinzip der schrittweisen Verfeinerung einzugehen. Zweitens wollen wir gleichzeitig verdeutlichen, wie wichtig Komplexitätsüberlegungen beim Entwurf von Algorithmen sein können. Nehmen wir an, unser Algorithmus hat als Zwischenstand einen Graphen R mit k Knoten berechnet. Die intuitive Vorgehensweise bei der Suche nach der billigsten Kante erfordert jeweils k (n − k) Vergleiche, da jeder Knoten aus R mit jedem noch nicht verbundenen Knoten verglichen werden muss. Insgesamt ergibt sich damit also eine Gesamtlaufzeit mit kubischem Aufwand O(n³) (man setze , um sich dies zu verdeutlichen).

Zur Optimierung der Laufzeitkomplexität wäre es hilfreich, eine Beschränkung der Suche auf eine Teilmenge V der Kanten derart zu erreichen, dass Folgendes gilt:

1. V enthält immer die billigste aus R ausgehende Kante.
2. V enthält wesentlich weniger Kanten als k (n − k).
3. V ist einfach anpassbar im Verlaufe des Algorithmus.

Hierfür kommen mehrere Möglichkeiten der Wahl von V in Frage:

1. V enthält für jeden Knoten P in R die billigste von P aus R herausführende Kante.
2. V enthält für jeden Knoten P außerhalb R die billigste von P in R hineinführende Kante.

Bei Betrachtung der Alternative A stellt man fest, dass mehrere Kanten zum gleichen Knoten herausführen können – dies ist sicher änderungsaufwendig, da im Extremfall alle Kanten in V in einem Schritt durch neue ersetzt werden müssen. Daher entscheiden wir uns für die Wahl von Alternative B.

Als erste Verfeinerung erhalten wir nun den folgenden Algorithmus:

Der Teilschritt »Ändere V« muss nun geeignet verfeinert werden. Zuerst muss die Kante b aus V entfernt werden. Die korrekte Anzahl der Verbindungen in V ist damit bereits erreicht, da jetzt genau ein Knoten weniger außerhalb von R liegt.

Für den neu verbundenen Knoten P können wir Folgendes feststellen:

Daher können wir nun direkt eine zweite Verfeinerung unseres Verfahrens angeben:

Graph

Wir beschließen diesen Abschnitt mit einigen Bemerkungen zum Beispiel. Für die Realisierung benötigen wir einen »abstrakten« Datentyp Graph mit Knoten, Kanten, Operationen etc. Derartige Datentypen bilden den Inhalt des dritten Teils dieses Buches, Graphen und ihre effiziente Darstellung werden speziell in Kapitel 16 ausführlich behandelt.

Bei einer geeigneten Realisierung der Datenstruktur für die zugrunde liegenden Graphen ist das verfeinerte Verfahren quadratisch im Aufwand (O(n²)), also besser als die intuitive Variante. Der vorgestellte Algorithmus stammt ursprünglich von R. C. Prim (1957) und ist daher auch als Algorithmus von Prim bekannt.

8.3Rekursion: Divide-and-conquer

Teile und herrsche

Das bereits mehrfach behandelte Prinzip der Rekursion wendet bei der Lösung eines Problems die Gesamtlösungsstrategie innerhalb der algorithmischen Lösung rekursiv auf ein geändertes Problem an. Typischerweise erfolgt diese erneute Anwendung des Gesamtverfahrens auf ein vereinfachtes Problem, um eine Terminierung zu garantieren. Das Prinzip »Divide-and-conquer«, deutsch »Teile und herrsche«, basiert nun darauf, in einem Schritt eine große Aufgabe in mehrere kleinere Aufgaben zu teilen und diese rekursiv zu bearbeiten – also ein klassischer Einsatz des Rekursionsprinzips.

8.3.1Das Prinzip »Teile und herrsche«

Wir haben bereits mit den Sortierverfahren QuickSort und MergeSort in Kapitel 5 typische Vertreter von Divide-and-conquer-Algorithmen kennen gelernt. Beide Verfahren teilen eine zu sortierende Eingabemenge in zwei ungefähr gleich große Teile, die dann wiederum sortiert und zum Gesamtergebnis verknüpft werden. Unser Ziel ist es nun, ein Muster für derartige Verfahren zu entwickeln, das leicht an andere Aufgabenstellungen angepasst werden kann (neben dem deutschen »Teile und herrsche« wird übrigens auch das lateinische »divide et impera« als Bezeichnung dieser Algorithmenklasse benutzt).

Prinzip: »Teile und herrsche«

Das Prinzip »Teile und herrsche« kann knapp wie folgt skizziert werden:

Dieses Prinzip kann nun in ein Muster für konkrete Divide-and-conquer-Algorithmen überführt werden. Die Grundprinzipien sind dabei die Folgenden:

1. Zerlege das gegebene Problem in mehrere getrennte Teilprobleme,
   1. löse diese einzeln
   2. und setze die Lösungen des ursprünglichen Problems aus den Teillösungen zusammen.
2. Wende dieselbe Technik auf jedes der Teilprobleme an, dann auf deren Teilprobleme usw., bis die Teilprobleme klein genug sind, dass man eine Lösung explizit angeben kann.
3. Strebe an, dass jedes Teilproblem von derselben Art ist wie das ursprüngliche Problem, so dass es mit demselben Algorithmus gelöst werden kann.

Divide-and-conquer-Muster

Das Divide-and-conquer-Muster kann in Pseudocode-Notation nun wie folgt beschrieben werden:

Dieses Muster muss natürlich noch um die Repräsentation und Übergabe der Teillösungen verfeinert werden.

Zur Verdeutlichung dieses Musters sei auf das MergeSort-Verfahren (Algorithmus 5.7 auf Seite 139) verwiesen.

8.3.2Beispiel: Spielpläne für Turniere

Als weiteres Beispiel für die Divide-and-conquer-Technik betrachten wir eine Fragestellung, die auf den ersten Blick ganz anders geartet ist als die bisherigen Divide-and-conquer-Verfahren, die wir etwa als Sortierverfahren kennen gelernt haben. Aufgabe ist es, Turnierspielpläne für eine gegebene Anzahl von Spielern zu konstruieren – es gibt also keine Eingabemenge, die in der Mitte geteilt werden könnte.

Wir gehen von einer Zweierpotenz n = 2^k als Anzahl der Spieler aus. Wir benötigen mindestens n − 1 Turniertage, da ja jeder Spieler gegen jeden anderen spielt und jeder einzelne Spieler nur einmal am Tag spielen soll.

Unser Verfahren basiert wieder auf einer Zerlegung des Problems. Nehmen wir an, dass ein Turnierplan T_k bekannt ist (T_k ist ein Spielplan für 2^k Spieler). Gelingt es uns nun, einen Turnierplan T_k+1 für m = 2n = 2^k+1 Spieler zu konstruieren, können wir das Rekursionsprinzip anwenden.

Wir notieren dafür einen Spielplan als Matrix s, wobei der Eintrag s_i,j den Gegner des Spielers i am Tage j bestimmt. Einen derartigen Spielplan für k = 2 zeigt Abbildung 8–5. Da kein Spieler in einer Spalte oder einer Zeile zweimal vorkommt, handelt es sich um einen korrekten Spielplan.

Abb. 8–5 Spielplan T₂

Der Algorithmus basiert nun darauf, dass es möglich ist, T_k+1 aus T_k nach dem in Abbildung 8–6 skizzierten Muster zu konstruieren.

Abb. 8–6 Konstruktion des Spielplans T_k+1

Dieses Schema kann leicht in einen Divide-and-conquer-Algorithmus überführt werden, der rekursiv T_k+1 auf T_k zurückführt. Die einzelnen Einträge in Abbildung 8–6 bedeuten hierbei das Folgende:

• ist die ursprüngliche Matrix T_k mit jeweils um den Wert n erhöhten Elementen.
• Z_k ist eine (n × n)-Matrix, die durch zyklisches Verschieben der Zeile (1, 2, …, n) erzeugt wird.
• S_k ist eine (n × n)-Matrix, konstruiert durch zyklisches Verschieben der Spalte (n + 1, …, m) für n = 2^k und m = 2^k+1.

Für den Fall k = 2 erhalten wir also beispielsweise:

Abb. 8–7 Spielplan T₃

Divide-and-conquer basiert darauf, dass man für kleine Problemgrößen die Lösung direkt angeben kann. Für den Spielplan T₁ kann man dies wie folgt:

In Abbildung 8–7 ist der Spielplan T₃ angegeben, wie er bei Anwendung des vorgestellten Prinzips errechnet wird.

8.4Rekursion: Backtracking

Backtracking

Das Backtracking ist ein weiteres wichtiges Algorithmenmuster für Such- und Optimierungsprobleme. Das Backtracking realisiert eine allgemeine systematische Suchtechnik, die einen vorgegebenen Lösungsraum komplett bearbeitet.

Am einfachsten kann man sich das Prinzip des Backtracking an einer Labyrinth-Suche verdeutlichen, wie sie in Abbildung 8–8 skizziert ist. Die Problemstellung lautet »Wie kommt die Maus zum Käse?« In Abbildung 8–8 ist links ein Labyrinth mit dem Startpunkt M der Maus und dem Käse K abgebildet; rechts sind alle möglichen (nichtzyklischen) Wege vom Startpunkt aus in Form eines Baumes mit der Wurzel (1, 1) für den Startpunkt notiert.

Der Begriff Backtracking kommt daher, dass man bei der Suche in Sackgassen gerät und dann wieder zur nächsten noch nicht bearbeiteten Abzweigung zurück geht, bis man alle Verzweigungen abgearbeitet hat. So führt ein gewählter Weg (1, 1), (1, 2), (1, 3), (2, 3) in eine Sackgasse, so dass man zur Position (1, 2) zurückgehen muss, um die Verzweigung nach (2, 2) als Alternative zu wählen.

Abb. 8–8 Labyrinth-Suche und Backtracking

Die Abbildung 8–8 zeigt die durchlaufenen Konfigurationen (entsprechend den Positionen im Labyrinth) bei vollständigem Durchlauf durch das Labyrinth. Eine Konfiguration entspricht dabei einem bereits beschrittenen Weg. Dieser Ansatz zum vollständigen Durchlauf wird nun für das Backtracking verallgemeinert.

8.4.1Prinzip des Backtracking

Konfigurationen und Erweiterungen

Backtracking basiert auf dem vollständigen Durchlauf eines Lösungsraums, so dass die gesuchte Lösung tatsächlich erreicht wird. Wie am Labyrinth-Beispiel bereits verdeutlicht, müssen wir dabei Konfigurationen betrachten, die jeweils in einem Schritt zu einer neuen Konfiguration erweitert werden können. Auch muss entscheidbar sein, ob wir eine Lösung (quasi den Käse) auch tatsächlich gefunden haben.

Formal bedeutet es, dass für unsere Problemstellung die folgenden Voraussetzungen gelten müssen:

• KF ist die Menge von Konfigurationen K.
• K₀ ist die Anfangskonfiguration.
• Für jede Konfiguration K_i kann die Menge der direkten Erweiterungen K_i,1, K_i,ni bestimmt werden.
• Für jede Konfiguration ist entscheidbar, ob sie eine Lösung ist.

Backtracking-Muster

Backtracking ist ein rekursives Verfahren, das mit dem Aufruf BACKTRACK(K₀), also mit der Anfangskonfiguration, gestartet wird. Das Backtracking-Muster kann nun in Pseudocode-Notation wie folgt angegeben werden:

Terminierung des Backtracking

Bevor wir das Backtracking anhand einer konkreten Aufgabenstellung verdeutlichen, soll noch auf einige zu beachtende Eigenschaften des Backtracking hingewiesen werden. Eine garantierte Terminierung ist nur gegeben, wenn der zu durchsuchende Lösungsraum endlich ist und wenn wiederholtes Betreten einer bereits getesteten Konfiguration auf einem Weg ausgeschlossen werden kann. Letzteres kann man oft durch geeignete Kodierung des bisher zurückgelegten Weges in der Konfigurationsdarstellung erreichen.

Aufwand des Backtracking

Kritisch kann der Aufwand des Backtracking sein. Da der Aufwand von der Größe des komplett zu durchlaufenden Lösungsraums abhängt, entsteht oft ein exponentieller Aufwand, wenn etwa alle Permutationen einer Eingabeliste als Lösungskonfigurationen in Frage kommen.

Varianten des Backtracking

Aufgrund dieses Problems werden oft abgewandelte Varianten des Backtracking realisiert:

• Der Algorithmus kann bewertete Lösungen berechnen, aus denen nach Lauf des Algorithmus die beste ausgewählt wird. Dies ist eine typische Variante für Optimierungsfragen (»Finde den größten Käse«).
• Das vorgegebene Muster findet alle Lösungen. In einigen Anwendungen ist ein Abbruch nach der ersten gefundenen Lösung sinnvoll.
• Die Variante »Branch-and-Bound« besteht darin, nur Zweige zu verfolgen, die eine Lösung prinzipiell zulassen. Es wird also versucht, Wege in Sackgassen ohne Lösung bereits im Voraus zu erkennen und gar nicht erst zu betreten.
• Oft ist es aus Komplexitätsgründen sinnvoll, eine maximale Rekursionstiefe vorzugeben, um unter Zeitbeschränkungen zumindest einen Teil des Lösungsraums abzuarbeiten. Man denke hierbei etwa an Schachprogramme.

Typische Einsatzfelder des Backtracking

Die beschriebenen Eigenschaften machen das Backtracking-Prinzip für einige Anwendungsgebiete besonders geeignet.

• In Spielprogrammen (Schach, Dame, …) entsprechen Konfigurationen den Stellungen der Spielfiguren, die Erweiterungen den Spielzügen.
• Die Erfüllbarkeitstests von logischen Aussagen und die Auswertung von Programmen in logischen Programmiersprachen (vergleiche Abschnitt 3.4) können ebenfalls Backtracking-Strategien einsetzen.
• Planungsprobleme, Konfigurierungen und Optimierungsprobleme sind ebenfalls klassische Anwendungsgebiete.

8.4.2Beispiel: Das Acht-Damen-Problem

Als Beispiel für einen konkreten Algorithmus, der Backtracking einsetzt, betrachten wir das Acht-Damen-Problem. In Abschnitt 3.5.1 hatten wir dieses Problem bereits mittels genetischer Algorithmen gelöst, also mit einem sukzessiven Näherungsverfahren, bei dem die Annäherung an eine Lösung in zufälligen Schritten mit anschließender Auslese erfolgt. Hier sollen nun konstruktiv alle Lösungen berechnet werden.

Gesucht sind alle Konfigurationen von 8 Damen auf einem 8x8-Schachbrett, so dass keine Dame eine andere bedroht. Eine Dame bedroht dabei bekanntlich alle Felder derjenigen Spalte und Zeile, auf der sie steht, sowie zusätzlich alle Felder der durch sie gehenden Diagonalen. Abbildung 8–9 zeigt zwei (nicht isomorphe!) Lösungen dieses Problems.

Abb. 8–9 Acht-Damen-Problem

Um für das Acht-Damen-Problem Backtracking einsetzen zu können, müssen wir uns für eine Menge der Konfigurationen KF entscheiden. Ein geeignetes KF muss folgende Bedingungen besitzen:

1. Eine eindeutige Anfangskonfiguration K₀, etwa das leere Schachbrett, muss in ihr enthalten sein.
2. L ⊆ KF muss für die Lösungskonfigurationen L gelten.
3. Für jedes k ∊ KF ist leicht entscheidbar, ob k ∊ L gilt.
4. Die Konfigurationen lassen sich schrittweise erweitern und bilden dabei eine hierarchische Struktur.
5. Die Menge KF sollte nicht zu groß sein, um effizient durchsucht werden zu können.

Für die Menge der Lösungskonfigurationen L gelten dabei die folgenden beiden Bedingungen:

L1: Es sind 8 Damen auf dem Brett.

L2: Keine zwei Damen bedrohen sich.

Nach einigem Nachdenken kommt man zu folgender Wahl von KF :

Man kann sich leicht vergewissern, dass dieses KF die oben genannten Bedingungen erfüllt (die Bedingung des effizienten Tests k ∊ L? kann dabei durch eine geschickte Speicherung der Konfigurationen erreicht werden, auf die wir hier nicht eingehen werden).

Nicht alle Konfigurationen lassen sich allerdings tatsächlich zu einer Lösung erweitern. Die Abbildung 8–10 zeigt eine derartige nicht erweiterbare Konfiguration, da jedes Feld in Zeile 7 bereits bedroht ist.

Abb. 8–10 Nicht alle Konfigurationen lassen sich zu einer Lösung erweitern

Algorithmus für Acht-Damen-Problem

Nach diesen Vorbemerkungen können wir nun einen Backtracking-Algorithmus zur Lösung des Acht-Damen-Problems angeben. Aufgerufen wird er mit der Platzierung der ersten Dame.

Dieser Algorithmus kann natürlich leicht auf ein n-Damen-Problem verallgemeinert werden. Da der Suchraum für acht Damen bereits sehr groß ist, zeigen wir den bearbeiteten Konfigurationsraum für vier Damen – vier Damen sind die kleinste Anzahl, für die eine nichttriviale Lösung (für n = 1 gibt es natürlich genau eine triviale Lösung) existiert.

Abb. 8–11 Konfigurationsraum beim Vier-Damen-Problem

Der Ablauf des Algorithmus beim Vier-Damen-Problem wird in Abbildung 8–11 skizziert. Die zweite und die vierte Konfiguration der ersten Stufe werden hier nicht weiter verfeinert, da sie sich symmetrisch zu den beiden vollständig gezeigten Teilbäumen entwickeln.

8.4.3Beispiel: Tic Tac Toe mit Backtracking

Abschließend wollen wir noch eine Anwendung von Backtracking in Computerspielen skizzieren: die Wahl des Spielzugs des Computers. In Abschnitt 2.5.2 haben wir den Gesamtablauf des Tic-Tac-Toe-Spiels skizziert, ohne jedoch auf die Eingabe der Spielzüge einzugehen. Für den menschlichen Spieler ist dies einfach: Hier wird nur das Feld abgefragt, auf welches der Spielstein abgelegt werden soll. Für die Computerseite muss jedoch ein geeigneter Spielzug »berechnet« werden. Grundsätzlich können wir dafür alle möglichen Spielzüge bestimmen (alle freien Felder), darauf aufbauend alle möglichen Spielzüge des Gegners (also des menschlichen Spielers), dann wieder die noch möglichen Computerzüge usw. Insgesamt ergibt sich somit ein Lösungsbaum von Spielzügen (Abbildung 8–12), der dem Konfigurationsraum aus Abschnitt 8.4.2 ähnelt.

Abb. 8–12 Lösungsbaum für Tic Tac Toe

Heuristik

Die Aufgabe ist es nun, jeweils ausgehend vom Knoten, der dem aktuellen Spielstand entspricht, den besten Pfad – und damit den vielversprechendsten eigenen Zug – zu wählen. Hierzu müssen die Lösungen, d.h. die Züge, bewertet werden. Dies erfolgt am besten rekursiv, indem wir von den Endzuständen (den Blättern im Spielbaum) ausgehen: Ein Sieg wird mit 100 Punkten bewertet, eine Niederlage mit − 100, ein Unentschieden mit 0. Für die Bewertung der Zwischenzüge, die nicht direkt zu Sieg oder Niederlage führen, wählen wir die einfache Heuristik »Lieber gleich gewinnen als später«. Hierzu betrachten wir einfach die Anzahl der Züge bis zu einer Entscheidung. Abbildung 8–13 illustriert diese Idee für den Spieler ’o’.

Abb. 8–13 Bewertung von Spielzügen in Tic Tac Toe

• Mit dem Zug auf das Feld 4 würden wir gewinnen – dieser Zug hat also den Wert 100.
• Für den Zug auf eines der Felder 1, 2, 7, 8 hat unser Gegner noch 4 Züge als Alternative. Für alle seine Züge außer auf Position 4 könnten wir im nächsten Zug noch auf Feld 4 setzen. Demzufolge sollte unser Zug auf 1, 2, 7 oder 8 einen kleineren Wert als 100 erhalten: Da es noch ein Zug bis zur Siegstellung wäre, reduzieren wir den Wert einfach um 10.

Dieses Bewertungsprinzip wird nun rekursiv für alle möglichen Züge angewendet und in das Backtracking-Muster aus Abschnitt 8.4.1 eingesetzt. Wie dort beschrieben können wir eine Konfiguration (einen Spielstand) direkt erweitern (einen möglichen Zug ausführen), die Lösungen bewerten und für Konfigurationen entscheiden, ob sie Lösungen darstellen. Eine mögliche Java-Implementierung dafür ist in Programm 8.2 angegeben.

Programm 8.2 Zugberechnung für Tic Tac Toe

Dargestellt ist hierbei nur die Methode waehleZug, die für den gegebenen Spieler spieler rekursiv den besten Zug ermittelt und dafür den Wert zurückgibt. Im Parameter tiefe wird die Rekursionstiefe mitgegeben – da es beim Tic Tac Toe maximal 9 Spielzüge gibt, können wir so die Anzahl der Züge bis zum Ende für die Zugbewertung ermitteln. Eine Besonderheit ist der Parameter pos, über den wir den Zug (Zeile, Spalte) an den Aufrufer zurückgeben. Da bei Java Parameter von primitiven Datentypen bekanntlich über call by value übergeben werden, müssen wir hier ein Feld als Referenzdatentyp verwenden, um einen call by reference-Aufruf zu erreichen, so dass Änderungen (hier also der Zug) innerhalb der Methode für den Aufrufer sichtbar werden (vgl. auch Abschnitt 3.6.2). Weiterhin ist zu beachten, dass beim rekursiven Aufruf jeweils der Spieler gewechselt wird (Methode wechsel).

8.5Dynamische Programmierung

Dynamische Programmierung vereint Aspekte der drei bisher vorgestellten Algorithmenmuster. Vom Ansatz der Greedy-Algorithmen wird die Wahl optimaler Teillösungen übernommen, von Divide-and-conquer und Backtracking die rekursive Herangehensweise basierend auf einem Konfigurationsbaum. Während Divide-and-conquer-Verfahren unabhängige Teilprobleme durch rekursive Aufrufe lösen, werden bei der dynamischen Programmierung abhängige Teilprobleme optimiert gelöst, indem mehrfach auftretende Teilprobleme nur einmal gelöst werden.

Der Anwendungsbereich der dynamischen Programmierung sind Optimierungsprobleme analog zu Greedy-Algorithmen – mit dynamischer Programmierung werden aber insbesondere Probleme bearbeitet, bei denen die Greedy-Vorgehensweise nicht zu optimalen Lösungen führt.

8.5.1Das Rucksackproblem

Rucksackproblem

Das Rucksackproblem (engl. knapsack problem) ähnelt auf den ersten Blick dem Geldwechselproblem. Gegeben sei ein Rucksack mit gegebener Kapazität C. Des Weiteren liegen n Gegenstände vor, die jeweils ein Gewicht g_i und einen Wert w_i haben. Sowohl Werte als auch Gewichte sind positive Zahlen. Aufgabe ist es nun, den Rucksack derart zu füllen, dass das Gesamtgewicht der eingefüllten Gegenstände die Füllkapazität nicht überschreitet und der Wert der eingefüllten Gegenstände maximal ist. Mathematisch entspricht dies der Bestimmung einer Indexmenge I ⊆ {1, …, n}, so dass

und

gelten. Als Datenstruktur bietet es sich an, derartige Indexmengen als boolesche Felder der Grenzen [1… n] zu kodieren. Es gibt nun 2ⁿ verschiedene Indexmengen, die zum Beispiel mittels Backtracking durchsucht werden könnten. Eine Backtracking-Lösung ist daher natürlich für große Eingabemengen vom Aufwand her nicht akzeptabel.

Betrachten wir ein konkretes Beispiel. Gegeben seien vier Gegenstände mit den Gewichten g₁ = 2, g₂ = 2, g₃ = 6, g₄ = 5 und den Werten w₁ = 6, w₂ = 3, w₃ = 5, w₄ = 4. Unser Rucksack hat eine Kapazität von C = 10.

Abbildung 8–14 zeigt den Lösungsraum in Form eines Konfigurationsbaumes. Die Knoten sind mit der verbleibenden Kapazität beschriftet, die Wurzel somit mit C = 10. Jede Ebene basiert auf einer Entscheidung, ob ein Gegenstand in den Rucksack aufgenommen wird oder nicht: Die Ebene i verzweigt sich in zwei Varianten, eine, in der der Gegenstand i im Rucksack aufgenommen wurde, und eine, in der dies nicht geschieht. Der am weitesten links stehende Pfad entspricht dabei einer Folge von ausschließlich »nein«-Entscheidungen: der leere Rucksack. Entscheidungen, die die Kapazität des Rucksacks überschreiten würden, werden nicht weiter verfolgt.

Abb. 8–14 Lösungsraum beim Rucksackproblem

Greedy-Verfahren für das Rucksackproblem

Eine weitere Lösungsmöglichkeit ist die Anwendung eines Greedy-Verfahrens, bei dem schrittweise jeweils der Gegenstand mit dem höchsten Wert ausgewählt wird, bis die Kapazität des Rucksacks erschöpft ist.

Für das obige Beispiel würde dieser Algorithmus zunächst den Gegenstand 1 (da w₁ = 6) wählen, dann 3 und schließlich 2, womit die Gesamtkapazität erreicht und ein Gesamtwert von 14 erzielt wird. In diesem Fall entspricht das der optimalen Lösung {1, 2, 3}. Bei jedem Durchlauf der Schleife müssen somit nur alle (noch nicht ausgewählten) Gegenstände untersucht werden. Wie aber in Abschnitt 8.2 schon erläutert, kann beim Einsatz eines Greedy-Verfahrens nicht garantiert werden, dass immer die optimale Lösung gefunden wird. Wenn wir das obige Beispiel so modifizieren, dass g₁ = 3 ist, würde das Greedy-Verfahren die Lösung {1, 3} liefern, die optimale Lösung ist hier jedoch {1, 2, 4}.

Bei Betrachtung des Baumes in Abbildung 8–14 stellt man fest, dass einige Teilbäume mehrfach berechnet werden, beispielsweise die beiden Teilbäume mit der Restkapazität 8 in der dritten Ebene. Hier setzt die dynamische Programmierung mit einer Optimierung an.

Dynamische Programmierung versucht die Abarbeitung mit folgender Idee zu optimieren: Jede Lösung wird durch einen Lösungsweg bestimmt. Eine optimale Lösung enthält dabei nur optimale Teillösungen: Wäre dies nicht der Fall, könnte man die Teillösung ja durch den besseren Teilweg ersetzen und würde eine noch bessere Gesamtlösung erhalten.

8.5.2Rekursive Lösung des Rucksackproblems

Rekursive Lösung des Rucksackproblems

Wir können das Rucksackproblem rekursiv mit einer Variante des Backtracking lösen, indem wir den Konfigurationsbaum beginnend mit der Entscheidung, ob der erste Gegenstand gewählt wird, schrittweise durchlaufen. Hierzu wird eine rekursive Prozedur rucksack genutzt, die als ersten Parameter den Index des aktuell bearbeiteten Gegenstandes und als zweiten Parameter die Restkapazität des Rucksacks besitzt.

Die Berechnung wird mit dem Aufruf rucksack(1, C) gestartet. Zweige, die die Kapazität frühzeitig ausschöpfen, werden nicht verfolgt. Als Optimierungspotenzial bleibt aber die mehrfache Auswertung gleicher Funktionsaufrufe (in unserem Beispiel würde wie in Abbildung 8–14 dargestellt der Aufruf rucksack(3,8) zweimal erfolgen).

8.5.3Prinzip der dynamischen Programmierung

Die Idee der dynamischen Programmierung ist es nun, in einer Iteration rückwärts die Resultate der Aufrufe rucksack(i,C) zu berechnen. Dazu wird ein zweidimensionales Feld f angelegt, das die Werte speichert.

Wir betrachten in Erweiterung des bisherigen Beispiels fünf Gegenstände mit den Gewichten g₁ = 2, g₂ = 2, g₃ = 6, g₄ = 5, g₅ = 4 und den Werten w₁ = 6, w₂ = 3, w₃ = 5, w₄ = 4, w₅ = 6. Der Konfigurationsbaum würde somit um eine weitere Ebene vergrößert werden. Unser Rucksack hat eine Kapazität von C = 10. Das Feld f ist in Abbildung 8–15 dargestellt.

Abb. 8–15 Feld der Funktionswerte des Rucksackproblems

Zum Beispiel bedeutet der Eintrag an der Stelle i = 4 und rc = 9, dass ein Aufruf rucksack(4,9) das Ergebnis 10 ergeben würde – bei einer Restkapazität von 9 können beide verbleibenden Gegenstände (Nummer 4 und 5) mit dem gemeinsamen Gewicht von 4 + 5 = 9 in den Rucksack gepackt werden, so dass sich ein Wert von 4 + 6 = 10 ergibt. Das Ergebnis der Berechnung f (1, 10) wäre an der Position i = 1 und rc = 10 zu finden – da die anderen Einträge der Zeile i = 1 nicht relevant sind, wird hier nur dieser eine Wert berechnet. Er errechnet sich wie in der rekursiven Variante als

max(f(2, 10), f(2, 8) + 6) = max(11, 9 + 6) = max(11, 15) = 15.

Iterative Lösung des Rucksackproblems

Es ist nun einfach möglich, den rekursiven Algorithmus derart umzuschreiben, dass ein globales Feld genutzt wird, um Berechnungen nach erfolgtem Aufruf abzuspeichern und damit Mehrfachberechnungen zu vermeiden. Dies hat den Vorteil, dass nur Feldeinträge berechnet werden, die tatsächlich benötigt werden. Wir betrachten stattdessen eine iterative Variante, die das gesamte Feld f berechnet. Der iterative Algorithmus kann nun wie folgt skizziert werden:

Natürlich funktioniert eine derartige Lösung nur für Integerwerte der Gewichte (oder bei festen Schritten der Gewichtswerte, die auf eine Integerskala abgebildet werden können). Auch kann das Feld f bei großem Kapazitätswert sehr umfangreich werden. Eine mögliche Lösung für beide Probleme besteht darin, in einer geeigneten Datenstruktur nicht die gesamten Zeilen abzuspeichern, sondern nur die Stellen, an denen der Wert innerhalb einer Zeile wechselt.

Eine ausführliche Behandlung der dynamischen Programmierung mit einer Reihe weiterer Beispiele kann im Buch von Sahni gefunden werden [Sah04, Kapitel 20].