Lösung von Abzählproblemen durch Rekursion

Einordnung des Artikels

• Ausgewählte Kapitel der Mathematik (für Programmierer, Informatiker, Ingenieure und Naturwissenschaftler)
  • Wahrscheinlichkeitsrechnung
    • Grundbegriffe der Wahrscheinlichkeitsrechnung: einfache Abzählprobleme
    • Grundbegriffe der Wahrscheinlichkeitsrechnung: Begriffsbildungen der Kombinatorik
    • Entwicklung eines brute force Algorithmus für das Damenproblem
    • Lösung von Abzählproblemen durch Rekursion

In Ein Zahlenspiel zur Erläuterung des Monte Carlo Tree Search Algorithmus wurde ein einfaches Zahlenspiel vorgestellt, für das insbesondere diskutiert wurde,:

• Kann man am Anfangswert n ablesen, ob einer der Spieler den Gewinn erzwingen kann?
• Wie lautet die entsprechende Strategie?

Die Regeln des Zahlenspiels werden hier nochmal kurz erläutert; die anderen Diskussionen über das Zahlenspiel sind für das Verständnis diese Artikels zwar hilfreich aber nicht notwendig.

Einführung

Abzählprobleme und Rekursion

Bisher wurden folgende Methoden besprochen, wie man Abzählprobleme lösen kann:

1. Zurückführen des Problems auf einfachere Abzählprobleme, auf die man die Begriffsbildungen der Kombinatorik (wie Variation, Permutation, Kombination) anwenden kann.
2. Entwicklung eines brute-force-Algorithmus.

Beide Methoden haben ihre Nachteile:

1. Das Problem ist zu komplex für die einfachen Begriffsbildungen (oder man erkennt nicht, wie man das Problem auf sie zurückführen kann).
2. Bei brute-force-Algorithmen müssen oft Objekte erst konstruiert werden, bevor man sie abzählen kann; dies kann zu unzumutbaren Rechenzeiten oder Speicherproblemen führen.

In diesem Kapitel wird ein völlig anderer Zugang vorgestellt – das Abzählproblem wird rekursiv gelöst: Dazu wird es in zwei Teilprobleme zerlegt, wobei

• ein Teilproblem sehr einfach zu lösen ist und
• ein Teilproblem wie das ursprüngliche Problem gelöst werden kann, nur dass ein charakteristischer Parameter für das Problem jetzt kleiner ist.

Wenn man nun die beiden Lösungen zusammensetzt und den zweiten Schritt durch einen rekursiven Funktionsaufruf realisiert, hat man das Abzählproblem im Prinzip gelöst.

Ein einfaches Beispiel

Die geeignete Zerlegung in zwei Teilprobleme, um ein Abzählproblem in eine Rekursion zu verwandeln, kann an einem einfachen Beispiel demonstriert werden:

Wie viele 0-1-Folgen der Länge n gibt es?

Das Problem ist so einfach, dass man es direkt abzählen kann: Da man für jede Stelle 2 Möglichkeiten hat und es insgesamt n Stellen zu besetzten sind, gibt es 2ⁿ Möglichkeiten.

Wie zerlegt man das Problem, um zu einer Rekursion zu gelangen? Man spaltet die Folge der Länge n in ihre erste Stelle und eine restliche Folge der Länge n - 1 auf.

Wenn B(n) die Anzahl der 0-1-Folgen der Länge n beschreibt (B soll an binär erinnern), so hat man für die die erste Stelle zwei Möglichkeiten, nämlich 0 oder 1. Wie viele Möglichkeiten es gibt, die restlichen n - 1 Stellen zu besetzen ist unbekannt, aber das Problem ist strukturell identisch zum Ausgangsproblem: Die gesuchte Anzahl ist B(n - 1).

Zusammengesetzt werden die Lösungen, indem man multipliziert, da die Stellen unabhängig voneinander besetzt werden können. Man erhält insgesamt:

B(n) = 2 · B(n - 1).

Weiter ist klar, dass

B(1) = 2,

da dies genau die Anzahl der Möglichkeiten ist, eine Stelle zu besetzen. Setzt man die Rekursionsformel immer wieder in sich selbst ein, erhält wiederum: (siehe auch Abbildung 1)

B(n) = 2ⁿ.

Aus diesen Überlegungen erkennt man. Um das Problem zu lösen, die Anzahl B(n) der n-stelligen 0-1-Folgen zu berechnen, benötigt man:

1. Die Rekursionsformel, sie wird allgemein als der Rekursionsschritt bezeichnet.
2. Die Lösung des Problems für den Basisfall; dieser wird auch als der Rekursionsanfang bezeichnet.

Abbildung 1 versucht dies graphisch darzustellen.

Abbildung 1: Vorgehensweise zur rekursiven Berechnung der Anzahl der 0-1-Folgen der Länge n. Insgesamt benötigt man die Rekursionsformel (hier der Zusammenhang zwischen B(n) und B(n-1) und die Formel für den trivialen Fall, hier B(1) = 2.

Übersicht

Beispiele wie die Anzahl der 0-1-Folgen der Länge der n sind zu einfach, um mit Rekursionen vertraut zu werden. Das Beispiel wurde nur gewählt, um die Vorgehensweise zu demonstrieren.

Das Paradebeispiel für ein Abzählproblem, das sich leicht rekursiv lösen lässt, für das andere Methoden aussichtslos erscheinen, sind die Türme von Hanoi. Dieses Beispiel wird hier nicht besprochen.

Stattdessen wird ein anderes Problem vorgestellt, das methodisch sehr wichtig ist, da sich viele Abzählprobleme dadurch lösen lassen, dass man eine geeignete Baumstruktur aufbaut und dann den Baum abzählt (meist die Anzahl seiner Knoten oder die Anzahl seiner Blätter). Das hier vorgestellte Problem entspringt einem einfachen Zahlenspiel, das in Ein Zahlenspiel zur Erläuterung des Monte Carlo Tree Search Algorithmus ausführlich diskutiert wurde; dort aber unter dem Aspekt, ob es eine Gewinnstrategie gibt und wie diese lautet. Man kann das Zahlenspiel als eine einfache Variation des Nim-Spiels auffassen. Hier wird das Spiel als Abzählproblem betrachtet:

1. Wie viele mögliche Spiele gibt es?
2. Bei wie vielen Spielen gewinnt der Anziehende beziehungsweise der Nachziehende?

Es wird gezeigt, wie man diese Fragestellungen als Rekursion formuliert. In den R-Skripten werden dann die gesuchten Anzahlen berechnet.

Das Zahlenspiel 3-5-11

Die Spielregeln

Für das Zahlenspiel 3-5-11 zwischen zwei Spielern A und B gelten folgende Regeln:

1. Zu Beginn wird eine natürliche Zahl n aufgeschrieben.
2. Die Spieler A und B sind abwechselnd am Zug, wobei A beginnt.
3. Bei jedem Zug muss ein Spieler eine der Zahlen 3, 5, 11 von n abziehen; die Differenz ist das neue n.
4. Erreicht ein Spieler mit seinem Zug das Ergebnis n = 0, so hat er gewonnen. Ist n < 0, so hat der Spieler verloren.

Die folgende Tabelle zeigt einen möglichen Spielverlauf, der mit n = 22 startet; gezeigt ist immer die Zahl, die der Spieler bei seinem Zug erzeugt hat:

Tabelle 1: Ein möglicher Spielverlauf mit dem Anfangswert n = 22.

• Hier hat also A im ersten Zug 5 abgezogen, so dass n = 17 entsteht.
• Anschließend hat B ebenfalls 5 abgezogen, wodurch n = 12 ensteht.
• Und so weiter.
• Im letzten Zug hat A die Zahl n = 1 erzeugt, womit B eine negative Zahl erzeugen muss.

In Ein Zahlenspiel zur Erläuterung des Monte Carlo Tree Search Algorithmus wird gezeigt, dass man aus der Restklasse modulo 8 des Anfangswertes n ablesen kann, ob der Anziehende A den Gewinn erzeugt kann oder nicht.

Mit dem Zahlenspiel verbundene Abzählprobleme

Kennt man die Spielregeln des Zahlenspiels, so ist klar dass das Spiel nach endlich vielen Zügen beendet ist. Und es ist naheliegend folgende Fragen zu stellen:

1. Wie viele unterschiedliche Spiele kann es zu einem Anfangswert n geben?
2. Bei wie vielen Spielen davon gewinnt der Anziehende A?
3. Da das Spiel nicht unentschieden enden kann, beantworten die ersten beiden Fragen zugleich die Frage: Bei wie vielen Spielen zu gegebenem n gewinnt der Nachziehende B?
4. Das kürzeste Spiel entsteht, wenn immer die Zahl 11 abgezogen wird, und das längste Spiel, wenn immmer die Zahl 3 abgezogen wird. Welche Längen L eines Spiels sind möglich bei gegebenem Anfangswert n?
5. Wie viele Spiele der Länge L gibt es dann?

Lösung der Abzählprobleme

Der Spielbaum

In Abbildung 2 ist der vollständige Spielbaum zum Startwert n = 8 gezeigt; mit vollständiger Spielbaum ist gemeint, dass ausgehend von n = 8 alle möglichen Züge dargestellt werden bis das Spiel zu einem Ende kommt (n ist gleich null oder negativ).

Abbildung 2: Der vollständige Spielbaum zum Anfangswert n = 8. Vollständig heißt, dass das Spiel bis zu einer Entscheidung verfolgt wird. Das Wurzel-Element ist blau gekennzeichnet, die anderen Knoten gelb; die Farben der Kanten sind im Text erklärt.

Das Wurzel-Element des Baumes entspricht dem Anfangswert (hier n = 8).

Die Farben der Kanten sollen anzeigen:

• ob sich der Gewinn erzwingen lässt und der richtige Zug ausgewählt wurde (rot)
• ob der Gewinnzug verpasst wurde (blau) oder
• ob kein Gewinn möglich ist und es daher keinen Zug gibt, der den Gewinn des Gegners verhindern könnte (schwarz).

Es gelten daher folgende Regeln, wenn man den Baum entlang absteigender n untersucht:

1. Von einem Knoten können entweder rote und blaue Kanten ausgehen oder nur schwarze Kanten. (Dies gilt, da bei jedem n feststeht, ob sich der Gewinn erzwingen lässt oder nicht.)
2. Auf eine rote Kante können nur schwarze Kanten folgen. (Wenn ein Zug ausgeführt wurde, der den Gewinn erzwingen kann, kann der Gegner nur indiffernte Züge machen.)
3. Auf eine blaue oder eine schwarze Kante folgen nur rote oder blaue Kanten. (In beiden Fällen hat der Spieler, der am Zug ist, die Möglichkeit den Gewinn zu erzwingen.)

In der folgenden Abbildung 3 sind zusätzlich die Blätter des Baumes gefärbt, um anzuzeigen, wer das Spiel gewonnen hat:

• rot: der Anziehende gewinnt,
• grün: der Nachziehende gewinnt.

Abbildung 3: Zusätzlich zu Abbildung 2 sind jetzt die Blätter im Spielbaum farbig gekennzeichnet, um anzuzeigen, wer das Spiel gewinnt.

In den folgenden beiden Abbildungen 4 und 5 wird der Spielbaum für den Anfangswert n = 14 dargestellt.

Abbildung 4: Vollständiger Spielbaum zum Anfangswert n = 14.

Abbildung 5: Nochmals der vollständige Spielbaum, aber mit Kennzeichnung des Gewinners (rot: der Anziehende gewinnt, grün: der Nachziehende gewinnt).

Die rekursive Struktur des Spielbaumes

An den letzten Abbildungen erkennt man zum Beispiel, dass ein Spiel, das bei n = 14 beginnt, aus maximal 5 Zügen besteht. Trotz dieser kleinen Zahl ist es schwer in den Bäumen Regelmäßigkeiten zu erkennen, die das Abzählen erleichtern können. Aber genau in solchen Fällen können Rekursionen sehr einfache Lösungen ermöglichen. Dazu wird in der folgenden Abbildung 6 angedeutet, in welchem Sinne die Spielbäume rekursiv aufgebaut sind.

Abbildung 6 : Links ist der vollständige Spielbaum zum Anfangswert n angedeutet. Führt man den ersten Zug aus, entsteht einer von drei möglichen neuen Anfangswerten. Das restliche Spiel kann wiederum durch einen Spielbaum beschrieben werden (rechts). Man kann diese rekursive Struktur verwenden, um zum Beispiel einen Zusammenhang zwischen der Anzahl B(n) der Blätter des Spielbaumes links und der drei neuen Spielbäume rechts herzustellen (Formel unten).

Dazu ist links der Spielbaum dargestellt, der bei einem Anfangswert n startet. Mit B(n) werde die Anzahl der Blätter des Baumes bezeichnet, also die Anzahl der Spiele, die ausgehend von n möglich sind. Dass der Spielbaum in Dreiecksgestalt dargestellt wird, ist natürlich irreführend: Für große n wächst seine Breite exponentiell mit einem Verzweigungsfaktor 3. Und er bricht nicht abrupt ab wie es die Abbildung suggeriert – denn dann hätten alle Spiele die gleiche Anzahl von Zügen.

Da im ersten Zug eine der drei Zahlen 3, 5 oder 11 von n abgezogen werden muss, entstehen drei neue Spielbäume (rechts) zu den Anfangswerten n - 3, n - 5 und n - 11. Für den Fall, dass das Spiel bereits beendet ist, wird B = 1 gesetzt. Für die Anzahl der Blätter gilt somit folgende Rekursionsformel:

B(n) = B(n-3) + B(n-5) + B(n-11)

Man kann diese Überlegung fortsetzen und auf die Frage anwenden, wie viele Spiele von A beziehungsweise B gewonnen werden. Dazu wird in Abbildung 7 angedeutet, dass für die Anzahlen der gewonnen beziehungsweise verlorenen Spielen ebenfalls Rekursionsformeln gelten.

Zunächst zur Bezeichnung: Im Baum links wird mit G(n) die Anzahl der gewonnenen Spiele bezeichnet, die verlorenen Spiele mit V(n) und zwar aus der Sicht des Spielers, der in der Anfangssituation n am Zug ist; es gilt (es gibt kein unentschieden):

B(n) = G(n) + V(n)

Da bei jedem Zug das Zugrecht wechselt, tauschen die gewonnen und verlorenen Spiele bei jedem Zug ihre Rolle und man erhält die Rekursionsformeln:

G(n) = V(n-3) + V(n-5) + V(n-11)

V(n) = G(n-3) + G(n-5) + G(n-11)

Man spricht hier von einer wechselseitigen Rekursion, da G(n) durch eine Funktion V und V(n) wiederum durch die Funktion G ausgedrückt wird.

Abbildung 7: Links: Die Blätter des Spielbaumes werden in zwei Gruppen zerlegt; diejenigen bei denen der Anziehende gewinnt (rot) und diejenigen bei denen der Nachziehende gewinnt (grün). Rechts: Wird ein Zug ausgeführt, drehen sich Gewinn und Verlust um. Zwischen den Anzahlen der gewonnenen und verlorenen Spiele besteht jetzt eine wechselseitige Rekursion.

Rekursionsformel und Rekursionsanfang

Die Formeln, die oben für B(n), G(n) und V(n) hergeleitet wurden, bezeichnet man als Rekursionsformel oder Rekursionsschritt. Das einführende Beispiel mit der Anzahl der n-stelligen 0-1-Folgen hat schon gezeigt, dass die Rekursionsformel durch einen Startwert ergänzt werden muss; er wird als Rekursionsanfang oder Basisfall bezeichnet.

Wie lautet jeweils der Rekursionsanfang für B(n), G(n) und V(n)?

Für B(n) ist dies besonders einfach: Wenn das Spiel zu Ende ist, besteht der Spielbaum aus genau einem Knoten und n ist gerade der Wert, der im letzten Zug erzeugt wurde – nach den Spielregeln also n = 0 oder n < 0.

Somit lautet der Rekursionsanfang:

B(n) = 1 für n ≤ 0.

Um die Rekursionsanfänge für G und V zu formulieren, muss man beachten, wer am Zug ist. Wird daher in der Formel

G(n) = V(n-3) + V(n-5) + V(n-11)

die Funktion V(n = 0) aufgerufen, bedeutet dies: der anziehende Spieler hat n = 0 erzeugt und gewinnt, daher muss gelten:

V(0) = 1.

Wird dagegen V mit einem negativen Argument aufgerufen, verliert der anziehende Spieler:

V(n) = 0 für n < 0.

Betrachtet man die Formel

V(n) = G(n-3) + G(n-5) + G(n-11),

muss man die Argumentation genau umdrehen und man erhält:

G(0) = 0 und G(n) = 1 für n < 0.

Man sieht, dass man keinen einzigen Baum mit mehr als einem Knoten abzählen muss und aus den Rekursionsformeln dennoch alle gesuchten Anzahlen folgen. Die Ergebnisse zeigt die folgende Tabelle für n = 1, 2, ..., 24. Unten folgen die R-Skripte, die dies mit wenigen Zeilen Quelltext erledigen.

Tabelle 2: Berechnung von B(n), G(n) und V(n) für n = 1, 2, ..., 24.

Aufgaben

1. Berechnung der Anzahl der Spiele mit gegebener Länge L und Anfangswert n

• Welche Anzahl von Zügen kann ein Spiel haben, wenn es mit dem Anfangswert n beginnt, n = 1, 2, ...?
• Berechnen Sie die Anzahl der Spiele S(n, L) zu gegebenem Anfangswert n und Anzahl der Züge L. Verwenden Sie dazu eine ähnliche Rekursion wie sie zur Berechnung von G(n), V(n) und B(n) angewendet wurde.

2. Was bedeutet Gewinn-Wahrscheinlichkeit?

Die Zahlen G(n) und V(n) kann man als die Anzahl der Pfade interpretieren, die ausgehend von n im Spielbaum zu einem gewonnenen beziehungsweise verlorenen Spiel führen. (Denn jedes Blatt gehört eindeutig zu einem Pfad, der im Wurzel-Element startet.)

Diskutieren Sie:

Geben die Quotienten G(n) / S(n) und V(n) / S(n) die Wahrscheinlichkeit dafür an, dass ein Spiel gewonnen beziehungsweise verloren wird, wenn man annimmt, dass jede Entscheidung über den nächsten Zug rein zufällig aus den drei zur Verfügung stehenden Möglichkeiten gefällt wird (auch dann, wenn das Ende des Spiels bereits in Sicht ist)?

Falls ja: Wie begründet man, dass dies die gesuchten Wahrscheinlichkeiten sind?

Falls nein: Wie werden die entsprechenden Wahrscheinlichkeiten stattdessen berechnet?

R-Skripte

Berechnung der Anzahl der Spiele zu gegebenem Anfangswert n

Die oben hergeleitete Rekursionsformel wird jetzt verwendet, um für Anfangswerte n = 1, 2, ..., N die Anzahl der möglichen Spiele B(n) zu berechnen; die Funktion wird mit getB() bezeichnet. Eingabewert ist die obere Grenze N.

Die Berechnung der Werte von B(n) erfolgt in einer Schleife, die bei n = 1 startet und bis zu n = N läuft (Zeilen 8 bis 10). In der Schleife wird die Rekursionsformel zur Berechnung von B(n) verwendet, allerdings wird auf der rechten Seite die Berechnung an eine interne Funktion B.mem() weitergereicht (Zeile 9); dabei soll mem an memory erinnern.

Die interne Funktion B.mem() (Zeile 4 bis 6) geift entweder auf bereits berechnete Werte von B zurück (else-Zweig in Zeile 5) oder verwendet den Rekursionsanfang (if-Zweig in Zeile 5).

Für die bereits berechneten Werte von B wird in Zeile 2 ein Vektor der Länge N vorbereitet.

getB <- function(N = 100){
  B <- vector(mode = "integer", length = N)
  
  B.mem <- function(n){
    if( n <= 0) return(1) else return(B[n])
  }
  
  for(i in (1:N)){
    B[i] <- B.mem(i - 3) +  B.mem(i - 5) +  B.mem(i - 11)
  }
  return(B)
}

getB(N = 24)
# [1]          3          3          3          5          5          7          9          9         13         15
# [11]         17         25         27         33         45         49         65         81         91        123
# [21]        145        173        229        263

Der Aufruf von B() berechnet die in der Tabelle oben gezeigten Werte.

Berechnung der Anzahl der gewonnen beziehungsweise verlorenen Spiele zu gegebenem Anfangswert n

Die Berechnung erfolgt nach dem Vorgehen wie bei B(); es gibt nur kleine Unterschiede:

• Da es sich um eine wechselseitige Rekursion handelt, werden zwei interne Funktionen verwendet (G.mem() und V.mem()). In den internen Funktionen ist wieder der Rekursionsanfang implementiert.
• Da zwei Vektoren berechnet werden, wird das Ergebnis zu einer Liste zusammengefasst.

getGV <- function(N = 100){
  G <- vector(mode = "integer", length = N)
  V <- vector(mode = "integer", length = N)
  
  G.mem <- function(n){
    if( n < 0){
      return(1)
    }  else {
      if(identical(n, 0)){
        return(0)
      } else {
        return(G[n])
      }
    }
  }    # Ende G.mem()
  
  V.mem <- function(n){
    if( n < 0){
      return(0)
    }  else {
      if(identical(n, 0)){
        return(1)
      } else {
        return(V[n])
      }
    }
  }    # Ende V.mem()
  
  for(i in (1:N)){
    G[i] <- V.mem(i - 3) +  V.mem(i - 5) +  V.mem(i - 11)
    V[i] <- G.mem(i - 3) +  G.mem(i - 5) +  G.mem(i - 11)
  }
  return(list(G = G, V = V))
}

getGV(N = 24)
# $G
# [1]   0   0   1   3   4   5   5   3   4   5   9  16  19  19  21  17  25  36  52  73  87  87 104 105
# 
# $V
# [1]   3   3   2   2   1   2   4   6   9  10   8   9   8  14  24  32  40  45  39  50  58  86 125 158