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

Question

我在地铁系统中有一个车站网络。车站的数量、我可以在车站之间旅行的车票数量以及哪些车站相互连接，这些都在文本文件中作为程序的输入给出。哪些站相互连接保存在二维 bool 矩阵中。我必须找到从站 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;
}

我不是在寻找解决方案。我目前没有想法，希望有人能指出我正确的方向。由于我需要为此实现自下而上的方法，我将如何开始使用最小的子问题开发动态规划表？

Answer 1

你应该构造一个数组 T每一步 T[i]告诉“0 和 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