Programowanie dynamiczne - Zliczanie ścieżek w systemie metra

Question

Posiadam sieć stacji w systemie metra. Liczba stacji, liczba biletów, które mogę podróżować pomiędzy stacjami i stacjami, które są ze sobą połączone, są podane w pliku tekstowym jako dane wejściowe do programu. Które stacje są ze sobą połączone są przechowywane w macierzy binarnej 2D. Muszę znaleźć liczbę ścieżek od stacji 0 i z powrotem do 0, która wykorzystuje wszystkie bilety.

Oto jeden z przykładów:

W tym przykładzie, istnieje 7 stacji i 5 biletów. Uruchamianie i powrocie do 0, to jest 6 ścieżki:

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 

mają obecnie rekursywne rozwiązanie do tego, że biegnie w O (N^k) (n oznacza liczbę stacji, a k jest liczbą biletów), ale muszę go przekonwertować na iteracyjne, dynamiczne rozwiązanie programistyczne w O (k * N^2), które działa na dowolnym wejściu.

#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; 
} 

Nie szukam rozwiązania. Obecnie nie mam pomysłów i mam nadzieję, że ktoś wskaże mi właściwy kierunek. Ponieważ muszę wdrożyć do tego podejście oddolne, jak powinienem zacząć od opracowania tabeli programowania dynamicznego z wykorzystaniem najmniejszych pod-problemów?

Answer 1

Proponuję rozważyć sub-problem:

DP [i] [a] = liczba ścieżek od 0 ° C do korzystania dokładnie: i bilety

ten jest inicjowany z DP [ 0] [0] = 1, a DP [0] [a = 0] = 0.

można uzyskać formułę aktualizacji rozważając wszystkie ścieżki do węzła:

DP [i] [k] = suma DP [i-1], [B] wszystkich sąsiadów b o

Istnieje kN sub-problemy, z których każde ma O (N), w celu obliczenia, więc całkowita złożoność to O (kN^2).

Ostateczna odpowiedź jest podana przez DP [k] [0].

Answer 2

Powinieneś zbudować tablicę T, która dla każdego kroku T[i] mówi "ile ścieżek istnieje między 0 a i".

0 kroków, to tablica jest:

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

Następnie dla każdego kroku zrobić:

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

Po k tych krokach T[0] będzie odpowiedź.

Oto prosta implementacja Pythona, aby zilustrować:

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 prace rekurencyjnie przechowywania poprzedni wynik subproblem. W twoim przypadku podproblemy polegają na znalezieniu liczby wszystkich ścieżek, które, biorąc pod uwagę liczbę biletów k, mogą osiągnąć stację.

W przypadku podstawowym masz 0 biletów, a zatem jedyną dostępną stacją jest stacja 0 bez ścieżek. Aby uruchomić algorytm, zakładamy, że ścieżka zerowa jest również prawidłową ścieżką.

W tym miejscu polecam Ci dostać kawałek papieru i najpierw go wypróbować. Rekursji potrzebne jest coś

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 

Algorytm pełna DP, minimalizując liczbę zmian koniecznych do włączenia jej do kodu, następuje

/** 
* 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]; 
} 

Złożoność jest jak zapytałem. Upewnij się, że rozumiesz kod przed jego użyciem.

Jak się dowiesz, powtarzanie podprogramów to common pattern w algorytmach programowania dynamicznego.