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

Question

我在地铁系统中有一个站点网络.可以在文本文件中给出站的数量,我可以在站之间行进的票的数量以及哪些站彼此连接作为程序的输入.哪些站彼此连接保存在2D布尔矩阵中.我必须找到从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

我建议你考虑一下子问题：

DP[i][a] = 使用 i 张票从 0 到 a 的路径数

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

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

DP[i][a] = a 的所有邻居 b 的 DP[i-1][b] 之和

有 kN 个子问题，每个子问题需要 O(N) 来计算，因此总复杂度为 O(kN^2)。

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