Die Community zu .NET und Classic VB.
Menü

Mit Oberstufenmathe gegen die wirklich schweren Probleme

 von 

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.