Rekursion vermeiden (abhängige Summen) - Laufzeitanalyse

[lord_haffi]

Moin Leude,

Kurzer Kontext:

Vor kurzem musste ich für eine Uniaufgabe einen Algorithmus schreiben, der einen einfachen, ungewichteten und ungerichteten Graphen (im Sinne der Graphentheorie) mit \(N\) Knoten und \(M\) zufällig verteilten Verbindungen erzeugt.

Erste Idee: Eine zufällige Verbindung (d.h. zwei zufällige Knoten) ziehen und hinzufügen, falls sie noch nicht vorhanden ist. Ansonsten wird einfach geskippt. Das ganze wird wiederholt, bis alle \(M\) Verbindungen gesetzt wurden.

Da dieser Algorithmus mit einem höheren Verhältnis zwischen \(M\) und \(N\) immer schlechter wird, hatten wir uns eine andere Lösung überlegt, die im Endeffekt eine Laufzeit von \(M\) im best case und eine von \( \frac{N\cdot (N-1)}{2} \) (maximale Anzahl an Verbindungen in einem einfachen, ungerichteten Graphen) im worst case hat. Da hierbei die Laufzeit eine gleichverteilte Wahrscheinlichkeitsfunktion ist, ist der average case einfach \(\frac{N\cdot (N-1) - 2M}{4}\).

Jetzt würde ich gerne (aus Interesse) herausfinden, bei was für einem Verhältnis von \(M\) und \(N\) letzterer Algorithmus im average case besser wird. Dazu würde ich also gerne auch die Wahrscheinlichkeitsverteilung der Iterationen (bis alle Verbindungen gesetzt wurden) bei der ersten Idee berechnen.

Nun zur Frage:

Nach eifrigem Überlegen, bin ich zu folgender Wahrscheinlichkeitsverteilung gekommen:
Bei einem Graphen mit \(N\) Knoten und \(M\) hinzuzufügenden Verbindungen, ist die Wahrscheinlichkeit \(P( n )\) genau \(n\) Iterationen zu benötigen, um alle \(M\) Verbindungen zu setzen:

\[ P( n ) = \frac{(|E|_\text{max}-1)!}{|E|_\text{max}^{n-1}\cdot (|E|_\text{max}-M-1)!} \underbrace{\sum_{i_1=1}^{M-1}i_1 \sum_{i_2=i_1}^{M-1}i_2\:...\sum_{i_{n-M}=i_{n-M-1}}^{M-1}i_{n-M}}_{n-M\text{ nested sums}} \]

Wobei \(|E|_\text{max} = \frac{N\cdot (N-1)}{2}\) die maximale Anzahl an Verbindungen im Graphen ist.
Tja, da hab ich jetzt das Problem, dass nicht nur die Anzahl der Summen variabel ist sondern auch noch voneinander abhängen. Würden sie nicht voneinander abhängen, wäre das ganze "recht einfach", da könnte man sich nämlich das Multinomial Theorem zunutze machen und das Ding in ein Produkt einer Summe verpacken. So aber leider nicht. Ich hab das ganze testweise auch mal mit Rekursion so einprogrammiert, aber das Ding ist scheiße lahm.

Keine Ahnung, wie fit ihr in Mathe seid, aber hat einer von euch zufällig ne gescheite Idee, dass ich mir die Rekursion sparen kann? ^^

Mfg

 

[BAGZZlash]

Ich habe leider keine Antwort für Dich, aber bei solchen Fragen wurde mir selbst schon mehrmals hier kompetent geholfen. Da tummeln sich pfiffige Leute, die auf genau sowas Bock haben. Sieht zwar ein bisschen altbacken aus, aber die Leute da sind wirklich gut.

Angenommen, wir haben \( I = \{1, 2, 3, 4, 5\} \). Dann gilt (der Einfachheit halber) für \[ \sum_{i = I_1}^{I_N}i\sum_{j = i}^{I_N}j = 1 \cdot (1+2+3+4+5)+2 \cdot (2+3+4+5) + 3 \cdot (3+4+5) + 4 \cdot (4+5) + 5 \cdot 5 \] = \[ 1 \cdot 15 + 2 \cdot 14 + 3 \cdot 12 + 4 \cdot 9 + 5 \cdot 5 = 15 + 28 + 36 + 36 + 25 = 140 \].

Schreibt man die Werte so in eine Matrix, wird klar, dass man für die innere Summe zunächst die Randsummen der oberen Dreiecksmatrix braucht: \[ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & \sum = 15\\ & 2 & 3 & 4 & 5 & \sum = 14\\ & & 3 & 4 & 5 & \sum = 12\\ & & & 4 & 5 & \sum = 9\\ & & & & 5 & \sum = 5\\ \end{pmatrix} \]

Hat man nicht zwei geschachtelte Summen, sondern drei, wird aus der Matrix ein dreidimensionaler Würfel (Tensor). Hm, ob das hilft? Oder man schreibt den gesuchten Wert \( X \) mit einer Matrix \[ A_{m\times m}=\begin{pmatrix} 1 & 0 & 0 & 0 & 0\\0 & 2 & 0 & 0 & 0\\0 & 0 & 3 & 0 & 0\\ 0 & 0 & 0 & 4 & 0\\ 0 & 0 & 0 & 0 & 5\\ \end{pmatrix} \] als \[ X = \sum_{i = 1}^{I_N}i \cdot sp(A_{1:m-i+1, 1:m-i+1}) \]. Aber wieder ist die Frage, was bringt uns das konkret?

 

[lord_haffi]

Hat man nicht zwei geschachtelte Summen, sondern drei, wird aus der Matrix ein dreidimensionaler Würfel (Tensor). Hm, ob das hilft?

Hm, programmatisch könnte ich mir damit wohl die explizite Rekursion sparen, aber ich hab da so meine Zweifel, ob das wirklich schneller ist. Schließlich müsste ich das Ding ja auch noch initialisieren.. Aber n Versuch ist es vielleicht Wert ^^

Oder man schreibt den gesuchten Wert \(X\) mit einer Matrix

Naja, da ist ja das selbe Problem dann, wenn man das ganze auf mehr als zwei Summen verallgemeinern möchte.

Das Forum da sieht in der Tat etwas altbacken aus, aber ich versuch's Mal. Vielleicht findet sich ja dort eine Lösung für mein Problem - danke dir

 

[BAGZZlash]

Gearde kam da eine recht gute Antwort rein. Hilft Dir das?

 

[lord_haffi]

Ja, durchaus Danke dir ^^