Programmieren ist schwierig

Herbert Ausflüge

Wie schwierig Programmieren sein kann, zeigt dieses synthetische Beispiel:

Auf einer magischen Inselökonomie wirtschaften nur Banken, Produzenten und Spekulanten. Wir betrachten ihre magischen Übernahmeaktivitäten: Spekulanten übernehmen Banken und Produzenten, Banken übernehmen Produzenten. Wenn Spekulanten Banken übernehmen, werden sie Produzenten, wenn sie Produzenten übernehmen, werden sie Banken und wenn Banken Produzenten übernehmen, werden sie Spekulanten. Andere Beziehungen gibt es nicht.

Auf der Insel gibt es 17 Produzenten, 55 Banken und 6 Spekulanten. Nach jeder Investition gibt es einen Teilnehmer weniger und das Investieren hat einmal ein Ende.

Die Aufgabe: wie groß ist dann die maximale Anzahl der Teilnehmer, die auf der Insel ökonomisch überleben?

Betrachten wir 3 mögliche Lösungswege (Algorithmen).

Ausprobieren aller Änderungen der Zusammensetzung

Wir können jeden Investitionsschritt durch Wörter beschreiben, deren Buchstaben aus B (Bank), P (Produzent), und S (Spekulant) bestehen. Das längste Wort hat 78 Buchstaben (17+55+8) und wir könnten alle Wörter aus (B, P,S) bilden, die kürzer als 78 sind und darunter das längste heraus suchen, welches nur mehr einen Buchstaben enthält. Wenn wir so vorgehen, müssen wir im schlimmsten Fall 3^77 Wörter bilden – eine astronomische Zahl. Für eine vernünftige Rechenzeit sind das bei weitem zu viele.

Ausprobieren aller möglichen Zustände

Wir starten mit (17, 55, 6) und ändern im ersten Schritt auf (16, 54, 7), (16, 55, 5) oder (18, 54, 5), das sind 77 Teilnehmer. Wir reduzieren nun Schritt für Schritt auf 76, 75, 74 und checken „erlaubte“ Überführungen der Zustände. Das Überführen kann gestoppt werden, wenn wir bei einem Zustand mit zwei Teilnehmer bei 0 angelangt sind. Dieser Zustand ist (0, 0, 23). Es überleben 23 Spekulanten. Das schaffen Computer…

Ein direkter Lösungsweg nach einer eingehenden Analyse

Nach einigem Grübeln erkennen wir: 1. Der endgültige Zustand muss zwei Typen mit 0 ausweisen. 2. Jede Übernahme reduziert zwei Typen um je 1 und erhöht die Anzahl des dritten Typen um 1. 3. Aus 2. folgt: die kombinierte Anzahl zweier beliebiger Typen bleibt nach einer Investition entweder gleich oder wird um zwei reduziert.  4. Wenn der finale Zustand zwei 0 enthält, muss jeder Zustand (auf dem Pfad) dieser beiden Typen vorher eine gerade Summe haben – damit auch der Ausgangszustand. 5. Die einzige gerade Summe zweier Typen im Ausgangszustand ist jene von Produzenten und Banken (17+55=72). Folglich überleben Spekulanten. 6. Aus 3. wissen wir: die Summe von Produzenten und Spekulanten kann nur weniger werden als jene im Anfangszustand (17+6=23). Also ist 23 eine obere Grenze. 7. Wenn wir eine Strategie finden, die mit (0, 0, 23) endet, sind wir fertig. Wir wissen auch, dass jede Übernahme eine Bank beteiligt haben muss, sonst müsste ein Spekulant einen Produzenten übernehmen und 23 könnte nicht erreicht werden.

Eine optimale Strategie:

Sie ist nicht die einzige…

1. 17 Banken übernehmen 17 Produzenten (17, 55, 6)–>(0, 38, 23)

2. 19 Spekulanten übernehmen 19 Banken (0, 38, 23)–>(19, 19, 4)

3. 19 Banken übernehmen 19 Produzenten (19, 19, 4)–>(0, 0, 23)

Die Lehren: Grübeln erspart Computerleistung. Analytische Ansätze verhelfen häufig zu Lösungen mittels Bleistift und Papier. Computer errechnen sie in Bruchteilen von Sekunden. Ausprobieren aller Möglichkeiten muss wohl überlegt sein.