Mit Oberstufenmathe gegen die wirklich schweren Probleme

von Dario Stein

Mit Oberstufenmathe gegen die wirklich schweren Probleme

Stellen wir uns vor, wir hätten eine Anzahl von Maschinen, die irgendwelche Aufgaben ausführen sollen, aber nicht alle Maschinen können gleichzeitig arbeiten. Einige müssen auf eine gemeinsame Ressource zugreifen und blockieren sich damit gegenseitig. Das können wir übersichtlich darstellen, indem wir für die Maschinen Punkte aufmalen und sie durch eine Linie verbinden, falls sie einander blockieren.

Abbildung 1: Kleines Optimierungsproblem

Die vier dunkelrot markierten Maschinen können konfliktfrei arbeiten, da sie nicht durch direkte Linien verbunden sind. Unser Ziel ist es, möglichst viele Maschinen gleichzeitig zum Laufen zu bekommen.

Nun wird dieses Problem mit mehr und mehr Maschinen schwer, richtig schwer. Und zwar nicht nur, weil wir dafür bis heute kein schnelles Rechenverfahren kennen, sondern weil sich die schwierigsten bekannten Probleme aus Logistik, Netzwerkanalyse, Verschlüsselungstechnik usw. allesamt auf Maschinen und Konflikte reduzieren lassen. Könnte man dieses eine Problem gut angehen, könnte man sie alle lösen.

Wir werfen mal einen Blick auf eine Situation mit mehr Maschinen, um zu sehen, wie verwirrend das Ganze wird.

Abbildung 2: Grösseres Optimierungsproblem

Eine exakte Lösung lässt sich also nur mit großen Rechenaufwand finden. Es gibt dagegen eine wunderbar einfache Möglichkeit, die Maschinen ohne zentrale Steuerung eine konfliktfreie Arbeitsteilung finden zu lassen. Wir brauchen dazu nicht mehr als das Werfen einer Münze. Angesichts der Einfachheit dieser Lösung wird sie wohl kaum optimal sein. Erstaunlicherweise ist sie aber, wenn man sich klug anstellt, auch gar nicht so schlecht. Wie genau man sich klug anstellt? Ein wenig Oberstufenmathematik sind dafür völlig ausreichend und die Lösung gibt uns eine spannende Tour durch die Gebiete Stochastik, Analysis und Geometrie.

Maschinen arrangieren mit Münzwurf

Unser Ansatz ist wirklich einfach, er ist in ein paar Sätzen erklärt.

Jede Maschine wirft für sich eine Münze und das Ergebnis Kopf/Zahl interpretieren wir als die Aussagen "will" und "will nicht". Wirft eine Maschine "will nicht", arbeitet sie auch nicht. Eine Maschine arbeitet nur, wenn sie selbst "will" wirft, aber alle anderen Maschinen, die mit ihr in Konflikt stehen, "will nicht" haben.

Alle Maschinen, die nach dieser Prozedur arbeiten, tun das garantiert konfliktfrei (alle Konflikte müssen ja "nicht gewollt" haben). Man könnte allerdings meinen, dass so überhaupt nur recht wenige Maschinen zum Arbeiten kommen, da ja alle Konflikte gleichzeitig richtig werfen müssen. Wir wollen also abschätzen, wie viele arbeitende Maschinen wir statistisch zu erwarten haben .

Der Erwartungswert

Schauen wir uns einmal konkret die $Latex: i$ -te Maschine an. Damit sie arbeitet, muss sie zunächst "will" werfen, das hat die Wahrscheinlichkeit $Latex: \frac 1 2$ . Auch muss jede Maschine, mit der sie in Konflikt steht, "will nicht" geworfen haben. Nennen wir diese Anzahl der Konflikte einmal $Latex: d_i$ , so ist die Wahrscheinlichkeit dafür $Latex: \left(\frac 1 2\right)^{d_i}$ , dass alle Maschinen entsprechend geworfen haben. Insgesamt haben wir also eine Wahrscheinlichkeit von

$Latex: p_i = \frac 1 2 \left(\frac 1 2\right)^{d_i},$ dass Maschine $Latex: i$ arbeitet. Diese Wahrscheinlichkeit ist für jede Maschine $Latex: i$ anders, je nachdem, wie viele Konflikte sie hat.

Wie viele Maschinen arbeiten nun insgesamt? Denken wir uns einmal die Kennzahl $Latex: X_i$ , die den Beitrag der $Latex: i$ -ten Maschine zur Anzahl der arbeitenden Maschinen misst. Also 1, falls die Maschine arbeitet, und 0 sonst. Der erwartete Beitrag $Latex: \mathbb E[X_i]$ ist gerade wieder $Latex: p_i$ . Zum Beispiel hat eine Maschine mit zwei Konflikten einen erwarteten Beitrag von $Latex: \frac 1 8$ zur Gesamtzahl, da sie mit Wahrscheinlichkeit $Latex: 1/8$ arbeitet.

Die Summe

$Latex: X = X_1 + X_2 + \ldots + X_n$ ist jetzt schon die gesuchte Anzahl arbeitender Maschinen. Die erwartete Anzahl arbeitender Maschinen ist also einfach die Summe der Wahrscheinlichkeiten

$Latex: \mathbb E[X] = \mathbb E[X_1] + \ldots + \mathbb E[X_n] = \frac 1 2 \left(\frac 1 2\right)^{d_1} + \ldots + \frac 1 2 \left(\frac 1 2\right)^{d_n}$

Rechnen wir diese Zahl für das erste Beispiel einmal aus: Es gibt fünf Maschinen mit nur einem Konflikt, eine mit zweien, eine mit dreien. Bedeutet

$Latex: \mathbb E[X] = 5 \cdot \frac 1 2 \cdot\frac 1 2 + \frac 1 2 \cdot\frac 1 4 + \frac 1 2 \cdot\frac 1 8 = \frac{23}{16} > 1$

Durch einfachen Münzwurf, völlig ohne Planung, bekommen wir im Schnitt also schon mehr als eine Maschine zum Laufen. Wir wissen rein aus der Rechnung deshalb auch schon, dass mindestens zwei Maschinen konfliktfrei arbeiten können, ohne überhaupt die genaue Konfiguration angeschaut oder mit dem Probieren angefangen zu haben. Aber natürlich wird es noch besser gehen.

Wieso faire Münzen?

Unsere Maschinen werfen "will"/"will nicht" mit derselben Wahrscheinlichkeit $Latex: \frac 1 2$ . Das war ein erster Versuch, aber es gibt keinen Grund, wieso das besonders gut sein sollte. Wenn es sehr viele Konflikte gibt, sollten die Maschinen eher zurücktreten anstatt sich zu blockieren, bei wenigen Konflikten müssen sich überhaupt ausreichend Maschinen freiwillig melden. Anstatt mit Wahrscheinlichkeit $Latex: \frac 1 2$ soll "will" nun mit einer zu bestimmenden Wahrscheinlichkeit $Latex: p$ vorkommen. Die Überlegung von oben liefert nun die neue Wahrscheinlichkeit, dass Maschine $Latex: i$ arbeitet

$Latex: p_i = p(1-p)^{d_i}$ und wir haben $Latex: \mathbb E[X] = \mathbb E[X_1] + \ldots + \mathbb E[X_n] = p(1-p)^{d_1} + \ldots + p(1-p)^{d_n}.$

Wir möchten jetzt $Latex: p$ klug so bestimmen, dass wir eine möglichst große Anzahl arbeitender Maschinen zu erwarten haben. Um beim Einstiegsbeispiel zu bleiben erhalten wir für den Erwartungswert den Ausdruck

$Latex: \mathbb E[X] = 5p(1-p)+p(1-p)^2+p(1-p)^3 = -p^4 + 4p^3-10p^2+7p.$

Das ist ein Polynom in $Latex: p$ , dessen Grad grob die Maximalzahl an Konflikten eines Knotens plus 1 ist. Wenn wir direkt versuchen würden, das Maximum für Werte von $Latex: p$ zwischen 0 und 1 zu finden, hätten wir eine eklige Kurvendiskussion vor uns. Eine Vereinfachung muss her.

Arithmetisches und geometrisches Mittel

Schauen wir uns zunächst einen speziellen Fall an: Wie sieht es aus, wenn alle Maschinen gleichviele Konflikte haben, nämlich genau $Latex: d$ Stück? Für den Erwartungswert kommen wir dann auf die einfache Formel

$Latex: \mathbb E[X] = np(1-p)^d$

und tatsächlich können wir diesen Term mit der Produktregel leicht ableiten und dann maximieren. Was machen wir aber mit echten Systemen und deren unterschiedlichen Konfliktzahlen? Wir könnten hier mit der durchschnittlichen Konfliktzahl

$Latex: \bar d = \frac 1 n (d_1 + \ldots + d_n)$

starten. Im ersten Beispiel hat jede Maschine im Mittel $Latex: \frac {10}{7} \approx 1,4$ Konflikte. Trotzdem bringt uns die vereinfachte Formel mit dem krummen Wert von $Latex: \bar d$ weiter. Tatsächlich ist der echte Erwartungswert nämlich immer mindestens so hoch wie der vereinfachte Wert. Wenn wir die vereinfachte Formel optimieren, schneiden wir also auf jeden Fall gut ab.

Dieses zunächst erstaunliche Ergebnis können wir selbst beweisen (wer die Aussage ohne Beweis akzeptieren möchte, kann sofort den nächsten Abschnitt weiterlesen). Den Schlüssel zum Beweis bilden zwei verschiedene Arten der Mittelwertbildung. Für zwei Zahlen $Latex: a,b\geq 0$ ist ihr arithmetisches Mittel einfach $Latex: AM = \frac{a+b} 2,$ ihr geometrisches Mittel hingegen ist $Latex: GM = \sqrt{a\cdot b}.$ Es gilt nun immer $Latex: GM \leq AM$ . Die beste Art, sich das vorzustellen, ist geometrisch: Nehmen wir ein Rechteck mit Seitenlängen $Latex: a$ und $Latex: b$ , dann ist $Latex: GM$ die Kantenlänge eines Quadrats mit demselben Flächeninhalt. Jetzt müssen wir nur wissen, dass das Quadrat unter den Rechtecken gleichen Inhalts den kleinsten Umfang hat, und fertig sind wir!

Abbildung 3: Arithmetisches und geometrisches Mittel

Arithmetisches und geometrisches Mittel verallgemeinern sich auf mehrere Zahlen ganz genau so mit $Latex: \frac 1 n$ und der $Latex: n$ -ten Wurzel. Die Ungleichung bleibt dabei in jedem Fall bestehen.

Zurück zum Erwartungswert also. Auf der einen Seite interessiert uns der vereinfachte Ausdruck mit der durchschnittlichen Konfliktzahl $Latex: \begin{align} (1-p)^{\bar d} &= (1-p)^{\frac 1 n(d_1 + \ldots d_n)} \\ &= \left((1-p)^{d_1 + \ldots + d_n}\right)^{\frac 1 n} \\ &= \left((1-p)^{d_1} \cdot \ldots \cdot (1-p)^{d_n}\right)^{\frac 1 n} \end{align}$

Das ist nichts anderes als das geometrische Mittel der $Latex: (1-p)^{d_i}$ -Ausdrücke, also nach unserer Ungleichung stets kleiner als das arithmetische Mittel $Latex: \frac 1 n \left((1-p)^{d_1} +\ldots +(1-p)^{d_n}\right).$

Dieser Ausdruck trat aber in unserem eigentlichen Erwartungswert auf. Multiplizieren wir beide Seiten mit $Latex: np$ , erhalten wir wie gewünscht

$Latex: \mathbb E[X] = p\left((1-p)^{d_1} +\ldots +(1-p)^{d_n}\right) \geq np(1-p)^{\bar d}.$

Treten wir kurz etwas von den Formeln zurück, ist das auch nicht überraschend. Die Vereinfachung können wir uns so denken: Wir starten mit einem Problem, in dem Maschinen sehr unterschiedliche Konfliktzahlen haben, mal sehr viele, mal sehr wenige und vergleichen das mit einem (hypothetischen) System, in dem alle Maschinen dieselbe gemittelte Konfliktzahl $Latex: \bar d$ haben. Wenn beide Systeme Münzen werfen, wer bekommt im Schnitt mehr Maschinen ans Laufen?

Die Antwort ist das erste. Die Maschinen mit sehr wenigen Konflikten stechen sozusagen heraus, man kann sie leicht ans Laufen bringen, exponentiell stark werden sie bevorteilt. Das zweite System hat nur mittlere Konfliktzahlen, ist viel regelmäßiger und damit im Schnitt schwieriger zum Laufen zu bringen (aber leichter zu analysieren). Auch das ist eine Interpretation der GM-AM-Ungleichung von oben.

Die optimierte Wahrscheinlichkeit

Wir haben also lediglich die einfache Aufgabe vor uns, zu sehen, welches $Latex: p$ zwischen 0 und 1 den Ausdruck $Latex: np(1-p)^{\bar d}$ maximiert. Also los, Kurvendiskussion! Das $Latex: n$ ist egal und wir leiten mit der Produktregel ab

$Latex: \begin{align} \frac{\mathrm d}{\mathrm dp}(p(1-p)^{\bar d}) &= (1-p)^{\bar d}-dp(1-p)^{\bar d - 1} \\ &= (1-p)^{\bar d-1}(1-p(\bar d+1)) \end{align}$

Die erste Klammer wird zwischen 0 und 1 nicht Null, durch Nullsetzen der hinteren Klammer erhalten wir endlich die optimierte Wahrscheinlichkeit $Latex: 1-p(\bar d+1) = 0, \text{ also } p = \frac 1 {\bar d+1}.$

Unser Verfahren ist also sehr einfach geblieben, alles was wir tun müssen, ist $Latex: \bar d$ auszurechnen, dann kann das Münzwerfen losgehen.

Demo-Programm

Natürlich gibt's ein Demo-Programm, für die einfache Grafik in Lua/löve2d. Der vorgestellte Algorithmus ist so einfach, dass man kaum Pseudocode bräuchte, aber der Vollständigkeit halber kommt hier eine Implementierung. Die Funktion neighbours(k) liefert zu Maschine k eine Liste der Nachbarn, d.h. Konflikte, p0 ist die wie oben bestimmte Wahrscheinlichkeit. That's all.

    -- Toss some coins to see who wants to work
local wants = {}

for k = 1,n do
    wants[k] = love.math.random() < p0
end

-- Find out who should work in the end
for k = 1,n do 
    -- Are all neighbours idle?
    local neighboursIdle = true
    for _, l in ipairs(neighbours(k)) do
        if wants[l] then
            neighboursIdle = false
            break
        end
    end
    
    -- We only work if we want and all neighbours don't
    working[k] = wants[k] and neighboursIdle
end

Das komplette Programm gibt's hier zum Download:

main.lua

Ihre Meinung

Falls Sie Fragen zu diesem Artikel haben oder Ihre Erfahrung mit anderen Nutzern austauschen möchten, dann teilen Sie uns diese bitte in einem der unten vorhandenen Themen oder über einen neuen Beitrag mit. Hierzu können sie einfach einen Beitrag in einem zum Thema passenden Forum anlegen, welcher automatisch mit dieser Seite verknüpft wird.