Graph Traversal von n Schritten
Gegeben ein einfaches ungerichtetes Diagramm wie folgt:
Beginnend in D, A, B oder C ( V_start ) - Ich muss berechnen, wie viele mögliche Pfade vom Startpunkt ( V_start ) bis zum Startpunkt ( V_start ) von n existieren Schritte, bei denen jede Kante und jeder Eckpunkt unbegrenzt oft besucht werden kann.
Ich dachte daran, eine Tiefensuche zu machen und stoppe, wenn steps > n || (steps == n && vertex != V_start) , dies wird jedoch ziemlich teuer, wenn zum Beispiel n = 1000000 . Mein nächster Gedanke führte mich dazu, DFS mit dynamischer Programmierung zu kombinieren, aber hier stecke ich fest.
(Das sind keine Hausaufgaben, nur ich bleibe dabei, mit Graphen und Algorithmen herumzuspielen, um zu lernen.)
Wie würde ich in einer vernünftigen Zeit mit einer großen n ?
2 Antworten
Diese Aufgabe wird durch Matrixmultiplikation gelöst.
Erzeuge Matrix n x n enthält 0s und 1s (1 für eine Zelle mat[i][j] wenn ein Pfad von i bis j existiert). Multiplizieren Sie diese Matrix mit k mal (ziehen Sie eine schnelle Matrix-Exponentiation in Betracht). Dann haben Sie in der Matrixzelle mat[i][j] die Anzahl der Pfade mit der Länge k beginnend mit i und endend mit j .
HINWEIS : Die schnelle Matrix-Exponentiation ist im Grunde die gleiche wie die schnelle Exponentiation, nur dass Sie stattdessen Zahlen multiplizieren, die Sie mit Matrizen multiplizieren.
NOTE2: Nehmen wir an, n ist die Anzahl der Scheitelpunkte im Diagramm. Dann läuft der Algorithmus, den ich hier vorschlage, in der Zeitkomplexität O (log k
BEARBEITEN Wie von Antoine gefordert, gebe ich eine Erklärung, warum dieser Algorithmus tatsächlich funktioniert:
Ich werde den Algorithmus durch Induktion beweisen. Die Basis der Induktion ist offensichtlich: Anfangs habe ich in der Matrix die Anzahl der Pfade der Länge 1.
Nehmen wir an, bis zur Potenz von k , wenn ich die Matrix auf die Potenz von k erhöhe, habe ich in mat[i][j] die Anzahl der Pfade mit der Länge k zwischen i und j .
Betrachten wir nun den nächsten Schritt k + 1 . Es ist offensichtlich, dass jeder Pfad der Länge k + 1 aus dem Präfix der Länge k und einer weiteren Kante besteht. Dies bedeutet im Wesentlichen, dass die Pfade der Länge k + 1 berechnet werden können (hier bezeichne ich mit mat_pow_k die Matrix, die auf die k th Potenz angehoben wurde)
num_paths (x, y, k + 1) = Summe i = 0 i & lt; n mat_pow_k [x] [i] * mat [i] [y]
Wiederum: n ist die Anzahl der Scheitelpunkte im Graphen. Dies kann eine Weile dauern, um zu verstehen, aber im Grunde die erste Matrix hat 1 in seiner mat[i][y] -Zelle nur, wenn es direkte Kante zwischen x und y gibt. Und wir zählen alle möglichen Präfixe einer solchen Kante, um den Pfad der Länge k + 1 zu bilden.
Aber das letzte, was ich geschrieben habe, ist tatsächlich die k + 1 st Macht von mat zu berechnen, was den Schritt der Induktion und meine Aussage beweist.
Es ist wie ein dynamic programming Problem:
- definiere a f [n] [m] als Anzahl der Pfade vom Startpunkt zum Punkt n in m Schritten
- Von jedem Punkt n zu seinem benachbarten k hast du die Formel: f [k] [m + 1] = f [k] [m + 1] + f [n] [m]
- in der Initialisierung, alle f [n] [m] wird 0 sein, aber f [Startpunkt] [0] = 1
- damit Sie das Endergebnis berechnen können
Pseudocode:
%Vor%