动态规划 - 计算地铁系统中的路径

Question

我在地铁系统中有一个车站网络。车站的数量、我可以在车站之间旅行的车票数量以及哪些车站相互连接，这些都在文本文件中作为程序的输入给出。哪些站相互连接保存在二维布尔矩阵中。我必须找到从 0 站到 0 站的路径数，这些路径使用了所有的票。

这是其中一个例子：

在那个例子中，有 7 个车站和 5 张车票。从0开始和返回，共有6条路径：

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

我目前有一个在 O(N^k) 中运行的递归解决方案（N 代表站数，而 k 是票数），但我必须将其转换为迭代动态规划O(k*N^2) 中适用于任何输入的解决方案。

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

我不是在寻找解决方案。我目前没有想法，希望有人能指出我正确的方向。由于我需要为此实施 bottom-up 方法，我将如何开始使用最小的 sub-problems 开发动态规划 table？

Answer 1

建议你考虑子问题：

DP[i][a] = number of paths from 0 to a using exactly i tickets

这是用 DP[0][0] = 1 和 DP[0][a!=0] = 0 初始化的。

您可以通过考虑到节点的所有路径来获得更新公式：

DP[i][a] = sum DP[i-1][b] for all neighbours b of a

有kN个子问题，每个子问题的计算时间都是O(N)，所以总的复杂度是O(kN^2)。

最终答案由DP[k][0]给出。

Answer 2

您应该构造一个数组 T，每个步骤 T[i] 告诉 "how many paths are there between 0 and i"。

对于 0 步，此数组为：

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

然后，对于每一步，执行：

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

经过 k 个步骤后，T[0] 就是答案。

这里有一个简单的 Python 实现来说明：

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 通过递归存储先前的子问题结果来工作。在你的情况下，子问题包括找到所有路径的数量，给定一些票 k，可以到达车站。

在基本情况下，您有 0 张车票，因此您唯一可以到达的车站是没有路径的车站 0。为了启动算法，我们假设空路径也是有效路径。

在这一点上，我建议您先拿一张纸自己尝试一下。您需要的递归类似于

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

完整的 DP 算法，最大限度地减少将其集成到您的代码中所需的更改数量，如下所示

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

复杂度是所要求的。在使用代码之前，请确保您了解代码。

正如您将了解到的，迭代子问题是动态规划算法中的一个 common pattern。

动态规划 - 计算地铁系统中的路径

Dynamic Programming - Counting paths in a subway system

c++

algorithm

dynamic-programming

c++11