Dynamische Programmierung - Zählen von Pfaden in einem U-Bahn-System

Question

Ich habe ein Netzwerk 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.

Dies ist eines der Beispiele:

In diesem Beispiel gibt es 7 Stationen und 5 Tickets. mit 0 starten und Rückkehr gibt es 6 Pfade:

0-1-2-3-4-0 
0-1-5-3-4-0 
0-1-6-3-4-0 
0-4-3-6-1-0 
0-4-3-5-1-0 
0-4-3-2-1-0 

I derzeit eine rekursive Lösung dafür, die in O läuft (n^k) (N die Anzahl der Stationen darstellt, während k die Nummer ist von Tickets), aber ich muss es in eine iterative, dynamische Programmierlösung in O (k * N^2) umwandeln, die an jeder Eingabe funktioniert.

#include <algorithm> 
#include <fstream> 
#include <iostream> 
#include <map> 
#include <vector> 

using namespace std; 


// We will represent our subway as a graph using 
// an adjacency matrix to indicate which stations are 
// adjacent to which other stations. 
struct Subway { 
    bool** connected; 
    int nStations; 

    Subway (int N); 

private: 
    // No copying allowed 
    Subway (const Subway&) {} 
    void operator= (const Subway&) {} 
}; 


Subway::Subway(int N) 
{ 
    nStations = N; 
    connected = new bool*[N]; 
    for (int i = 0; i < N; ++i) 
    { 
     connected[i] = new bool[N]; 
     fill_n (connected[i], N, false); 
    } 
} 

unsigned long long int callCounter = 0; 
void report (int dest, int k) 
{ 
    ++callCounter; 
    // Uncomment the following statement if you want to get a feel 
    // for how many times the same subproblems get revisited 
    // during the recursive solution. 
    cerr << callCounter << ": (" << dest << "," << k << ")" << endl; 
} 


/** 
* Count the number of ways we can go from station 0 to station destination 
* traversing exactly nSteps edges. 
*/ 
unsigned long long int tripCounter (const Subway& subway, int destination, int nSteps) 
{ 
    report (destination, nSteps); 
    if (nSteps == 1) 
    { 
     // Base case: We can do this in 1 step if destination is 
     // directly connected to 0. 
     if (subway.connected[0][destination]){ 
      return 1; 
     } 
     else{ 
      return 0; 
     } 
    } 
    else 
    { 
     // General case: We can get to destinaiton in nSteps steps if 
     // we can get to station S in (nSteps-1) steps and if S connects 
     // to destination. 
     unsigned long long int totalTrips = 0; 
     for (int S = 0; S < subway.nStations; ++S) 
     { 
      if (subway.connected[S][destination]) 
      { 
       // Recursive call 
       totalTrips += tripCounter (subway, S, nSteps-1); 
      } 
     } 
     return totalTrips; 
    } 
} 

// Read the subway description and 
// print the number of possible trips. 
void solve (istream& input) 
{ 
    int N, k; 
    input >> N >> k; 
    Subway subway(N); 
    int station1, station2; 
    while (input >> station1) 
    { 
     input >> station2; 
     subway.connected[station1][station2] = true; 
     subway.connected[station2][station1] = true; 
    } 
    cout << tripCounter(subway, 0, k) << endl; 
    // For illustrative/debugging purposes 
    cerr << "Recursive calls: " << callCounter << endl; 
} 




int main (int argc, char** argv) 
{ 
    if (argc > 1) 
    { 
     ifstream in (argv[1]); 
     solve (in); 
    } 
    else 
    { 
     solve (cin); 
    } 
    return 0; 
} 

Ich bin nicht auf der Suche nach einer 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 anfangen, eine dynamische Programmiertabelle mit den kleinsten Teilproblemen zu entwickeln?

Answer 1

Ich schlage vor, Sie betrachten das Teilproblem:

DP [i] [a] = Anzahl der Pfade von 0 bis ein mit genau i Tickets

Der mit DP initialisiert wird [ 0] [0] = 1 und DP [0] [a = 0] = 0.

Sie eine Update Formel, indem alle Pfade zu einem Knoten bekommen:

DP [i] [a] = sum DP [i-1] [b] für alle Nachbarn B ein

Es gibt kN Teilprobleme, die jeweils unter O (N) zu berechnen, so dass der Gesamt Komplexität ist O (kN^2).

Die endgültige Antwort wird von DP [k] [0] gegeben.

Answer 2

Sie sollten ein Array T konstruieren, dass für jeden Schritt T[i] sagt "wie viele Pfade gibt es zwischen 0 und i".

Für 0 Schritte Dieses Array ist:

[1, 0, 0, ... 0]

Dann wird für jeden Schritt tun:

T_new[i] = sum{0<=j<n}(T[j] if there is an edge (i, j))

Nach k dieser Schritte, T[0] wird die Antwort sein.

Hier ist eine einfache Python-Implementierung zu illustrieren:

def solve(G, k): 
    n = len(G) 

    T = [0]*n 
    T[0] = 1 

    for i in xrange(k): 
     T_new = [ 
      sum(T[j] for j in xrange(n) if G[i][j]) 
      for i in xrange(n) 
     ] 
     T = T_new 

    return T[0] 

G = [ 
    [0, 1, 0, 0, 1, 0, 0], 
    [1, 0, 1, 0, 0, 1, 1], 
    [0, 1, 0, 1, 0, 0, 0], 
    [0, 0, 1, 0, 1, 1, 1], 
    [1, 0, 0, 1, 0, 0, 0], 
    [0, 1, 0, 1, 0, 0, 0], 
    [0, 1, 0, 1, 0, 0, 0] 
] 

print solve(G, 5) #6 

Answer 3

Dynamic programming Werke von rekursiv die vorherigen Subproblem Ergebnis zu speichern. In Ihrem Fall bestehen die Teilprobleme darin, die Anzahl aller Pfade zu finden, die bei einer 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 Sie brauchen, ist so etwas wie

set base case (i.e. station 0 == 1 null path)  

for each ticket in [1;k] 
    stations = get the stations which were reached at the previous step 
    for each station in stations 
    spread the number of paths they were reached with to the neighbors 

return the number of paths for station 0 with k tickets 

Der komplette DP-Algorithmus benötigt, um die Anzahl von Änderungen zu minimieren es in den Code zu integrieren, folgt

/** 
* Count the number of ways we can go from station 0 to station destination 
* traversing exactly nSteps edges with dynamic programming. The algorithm 
* runs in O(k*N^2) where k is the number of tickets and N the number of 
* stations. 
*/ 
unsigned int tripCounter(const Subway& subway, int destination, int nSteps) 
{ 
    map<int, vector<int>> m; 
    for (int i = 0; i < nSteps + 1; ++i) 
    m[i].resize(subway.nStations, 0); 

    m[0][0] = 1; // Base case 

    for (int t = 1; t < m.size(); ++t) { // For each ticket 

    vector<int> reachedStations; 
    for (int s = 0; s < subway.nStations; ++s) { // For each station 
     if (m[t-1][s] > 0) 
     reachedStations.push_back(s); // Store if it was reached in the previous state 
    } 

    for (auto s : reachedStations) { 
     // Find adjacent stations 
     for (int adj = 0; adj < subway.nStations; ++adj) { 
     if (s == adj) 
      continue; 
     if (subway.connected[s][adj]) 
      m[t][adj] += m[t-1][s]; 
     } 
    } 
    } 
    return m[nSteps][0]; 
} 

Komplexität ist als gefragt. Stellen Sie sicher, dass Sie den Code verstanden haben, bevor Sie ihn verwenden.

Wie Sie Iterieren über Teilprobleme lernen wird, ist ein common pattern in dynamischen Programmieralgorithmen.