Rekursion vermeiden (abhängige Summen) - Laufzeitanalyse

lord_haffi

Moderator
Teammitglied
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
 
Zuletzt bearbeitet:
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?
 
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 :)
 
Ich arbeite derzeit an einem Algorithmus für meine Uni-Aufgabe, der einfache Pfade in einem ungerichteten Graphen finden soll. Könnte mir jemand Tipps geben, welche Suchmethoden sich am besten eignen, um effizient alle möglichen Pfade zwischen zwei Knoten zu ermitteln? Gibt es spezielle Herausforderungen, auf die ich achten sollte, oder Best Practices, die ich berücksichtigen sollte?",
"refusal
 
Bastle einfach eine Funktion, die alle umliegenden Knoten besucht, welche sie noch nicht besucht hat. Lasse sie auf dem Startknoten starten und gib den Pfad aus, falls sie bei dem Endknoten ankommt. Das nennt sich Rekursion.
 
Könnt ihr mir Tipps geben, wie ich effizient einen Algorithmus für ungewichtete und ungerichtete Graphen schreiben kann? Bin etwas unsicher und würde gerne eure Meinungen und Erfahrungen dazu hören.",
"refusal
 
Gibt es eine Vorgabe, wie die Knoten und Kanten eingegeben werden sollen? Die einfachste Methode, die mir einfällt, ist, einzelne Zeichen aus dem Alphabet als Knoten zu nehmen und Zeichenpaare als Kanten. Zeichenpaare kann man als Map/Dictionary effizient speichern und nachschlagen.
Wenn Du die Funktion zB als (Pseudocode) void suche(string bisheriger_pfad, char letzter_besuchter_knoten) definierst, kannst Du alle Pfade ermitteln, die von Punkt A nach Punkt B führen. Einfach jedes Mal im String nachschauen, ob der grade überprüfte Nachbarknoten schon besucht wurde.
Mit weniger Rechenaufwand findest du nur weniger als alle Pfade. Den Kürzesten zB mit Alpha-Beta-Pruning.
 
Im Gegensatz zu Ihnen habe ich versucht, künstliche Intelligenz zu fragen. Dies ist das Ergebnis, das ich erhalten habe:

Ein Algorithmus, um alle einfachen Pfade zwischen zwei Knoten in einem ungerichteten Graphen zu finden, erfordert die Suche nach allen möglichen Verbindungen ohne Wiederholung von Knoten. Hier sind einige Tipps und Methoden, die du verwenden könntest:

  1. Tiefensuche (DFS): Ein häufiger Ansatz zur Suche nach allen Pfaden ist die Tiefensuche (DFS), bei der du von einem Startknoten ausgehst und rekursiv alle benachbarten Knoten erkundest, dabei jedoch darauf achtest, keine Knoten zweimal zu besuchen. Sobald du das Ziel erreichst, kannst du den gefundenen Pfad speichern.
  2. Breitensuche (BFS): Falls du nach den kürzesten Pfaden zwischen zwei Knoten suchst, eignet sich die Breitensuche besser. Sie kann aber auch angepasst werden, um alle einfachen Pfade zu finden, ist jedoch weniger effizient als DFS für diese spezielle Aufgabe.
  3. Backtracking: In Kombination mit DFS kannst du Backtracking verwenden, um Pfade zu verwerfen, sobald sie eine Schleife oder einen bereits besuchten Knoten enthalten. Auf diese Weise stellst du sicher, dass jeder Pfad „einfach“ bleibt.
  4. Speicheroptimierung: Da alle Pfade gespeichert werden müssen, kann der Speicherverbrauch problematisch werden, insbesondere bei großen Graphen. Eine Möglichkeit zur Speicheroptimierung ist es, die Speicherung der Pfade erst dann vorzunehmen, wenn du einen vollständigen Pfad gefunden hast, und ihn nach der Weiterverarbeitung wieder zu löschen.
  5. Komplexität: Beachte, dass die Anzahl der möglichen Pfade exponentiell wachsen kann, insbesondere in großen, dichten Graphen. Es ist wichtig, die Komplexität zu berücksichtigen und ggf. Heuristiken oder Begrenzungen zu verwenden, um unnötige Berechnungen zu vermeiden.
Best Practices:

  • Stelle sicher, dass du alle Kanten des Graphen korrekt berücksichtigst, auch wenn der Graph ungerichtet ist.
  • Verwende effiziente Datenstrukturen, wie z. B. Sets oder HashMaps, um Knoten zu speichern und die Besuche zu prüfen.
  • Teste deinen Algorithmus gründlich mit kleinen Beispielen, um sicherzustellen, dass er alle Pfade korrekt findet.
Diese Methoden sollten dir helfen, einen effizienten Algorithmus zu entwickeln.
 
Im Gegensatz zu Ihnen habe ich versucht, künstliche Intelligenz zu fragen.
Jetzt werden die Bots auch noch frech :ROFLMAO: Als ob ich das nicht versucht hätte. Und dann hat die Antwort nichtmal im Entferntesten etwas mit der Frage zu tun. GPT Version 3? Version 4 hätte das bestimmt besser hinbekommen ^^ Aber Hauptsache, Mupfel gefällt das.

"refusal
 
Das Mitglied RobertASYPE hatte noch eine verwandte Frage und hat keinen neuen Thread aufgemacht. Soweit ich das sehe, liefert die AI ihm da brauchbare Stichworte.

 
Zurück
Oben Unten