Dynamische Programmierung - Zählen von Pfaden in einem U-Bahn-System
Ich habe ein Netz von Stationen in einem U-Bahn-System. Die Anzahl der Stationen, die Anzahl der Fahrkarten, die ich zwischen Stationen fahren kann und welche Stationen miteinander verbunden sind, werden in einer Textdatei als Eingabe für das Programm angegeben. Welche Stationen miteinander verbunden sind, werden in einer booleschen 2D-Matrix gehalten. Ich muss die Anzahl der Pfade von Station 0 und zurück zu 0 finden, die alle Tickets verwendet.
Hier ist eines der Beispiele:
In diesem Beispiel gibt es 7 Stationen und 5 Tickets.
Start und Rückkehr zu 0, gibt es 6 Wege:
Ich habe derzeit eine rekursive Lösung, die in O (N ^ k) läuft (N stellt die Anzahl der Stationen dar, während k die Anzahl der Tickets ist), aber ich muss es in eine iterative, dynamische Programmierlösung umwandeln O (k * N ^ 2), das bei jeder Eingabe funktioniert.
%Vor%Ich suche keine Lösung. Ich habe derzeit keine Ideen mehr und hoffe, dass mich jemand in die richtige Richtung lenken kann. Da ich dazu einen Bottom-Up-Ansatz implementieren muss, wie würde ich mit der Entwicklung einer dynamischen Programmiertabelle beginnen, die die kleinsten Teilprobleme verwendet?
3 Antworten
Ich schlage vor, Sie betrachten das Teilproblem:
DP [i] [a] = Anzahl der Pfade von 0 bis zur Verwendung von genau i Tickets
Dies wird mit DP [0] [0] = 1 und DP [0] [a! = 0] = 0 initialisiert.
Sie können eine Aktualisierungsformel erhalten, indem Sie alle Pfade zu einem Knoten berücksichtigen:
DP [i] [a] = Summe DP [i-1] [b] für alle Nachbarn b von a
Es gibt kN-Teilprobleme, von denen jeder O (N) zu berechnen hat, also ist die Gesamtkomplexität O (kN ^ 2).
Die endgültige Antwort wird von DP [k] [0] gegeben.
Sie sollten ein Array T erstellen, das für jeden Schritt T[i] angibt, "wie viele Pfade zwischen 0 und i liegen".
Für 0 Schritte ist dieses Array:
[1, 0, 0, ... 0]
Machen Sie dann für jeden Schritt:
T_new[i] = sum{0<=j<n}(T[j] if there is an edge (i, j))
Nach k dieser Schritte wird T[0] die Antwort sein.
Hier ist eine einfache Python-Implementierung zur Veranschaulichung:
%Vor%Die dynamische Programmierung funktioniert durch rekursives Speichern des vorherigen Subproblems. In Ihrem Fall bestehen die Teilprobleme darin, die Anzahl aller Pfade zu finden, die bei einer bestimmten Anzahl von Tickets k eine Station erreichen können.
Im Basisfall haben Sie 0 Tickets und somit ist die einzige Station, die Sie erreichen können, Station 0 ohne Pfade. Um den Algorithmus zu starten, gehen wir davon aus, dass der Null-Pfad auch ein gültiger Pfad ist.
An dieser Stelle würde ich Ihnen empfehlen, ein Stück Papier zu holen und es zuerst selbst auszuprobieren. Die Rekursion, die Sie benötigen, ist etwas wie
%Vor%Der vollständige DP-Algorithmus, der die Anzahl der Änderungen minimiert, die benötigt werden, um ihn in Ihren Code zu integrieren, folgt
%Vor% Die Komplexität ist 
wie gefragt.
Stellen Sie sicher, dass Sie den Code verstanden haben, bevor Sie ihn verwenden.
Wie Sie lernen, über Teilprobleme zu iterieren, ist ein allgemeines Muster in dynamischen Programmieralgorithmen .
Tags und Links algorithm c++ c++11 dynamic-programming