algorithm - 动态规划依赖于更大的状态

Question

有N个城市。每个城市都有1到10(含)类型的传送点。给你一个大小为 N 的数组，用整数表示每个城市的传送类型。对于前。 1 3 5 3 8 9。目标是根据以下规则找到从数组中的第一个条目到最后一个条目所需的最少小时数:

1. 从每个城市(数组中的条目)，您可以移动到它的左邻国或右邻国(如果有的话)，该行动需要 1 小时。
2. 你可以从每座城市传送到另一座城市，传送方式与你传送的城市相同。在上面的示例数组中，您可以从索引 1 的城市传送到索引 3 的城市，因为它们都具有相同类型的传送:3。此操作花费给定的 R 小时数。

我已经实现了一个动态编程解决方案，当最快的方法只是向前移动时，它可以完美地工作。但在某些情况下，返回几个城市然后向前传送会更快，从而最大限度地减少花费的时间。

这是我的算法失败的例子:例如。 2 1 3 4 6 8 5 7 4 2 3 5 2 1 3 4 3 5 6 7 和 R = 2正确答案:索引 0(时间 = 0)-> 索引 9(时间 = 2)-> 索引 8(时间 = 3)-> 索引 7(时间 = 4)-> 索引 19(时间 = 6)。我的算法会找到仅向前移动的最快方法，显然，正确的最快方法还涉及向后移动。

到目前为止，这是我的代码:

#include <iostream>
using namespace std;

int main()
{
    int dp[200] = {};
    short ti[200] = {};
    int numCities, R;
    cin >> numCities >> R;

    for (int i = 0; i < numCities; i++)
    {
        short temp;
        cin >> temp;
        ti[i] = temp;
    }

    for (int i = 1; i < numCities; i++)
    {
        dp[i] = dp[i - 1] + 1;

        for (int x = i - 1; x >= 0; x--)
        {
            if (ti[x] == ti[i])
            {
                if (R + dp[x] < dp[i])
                     dp[i] = R + dp[x];
            }
        }
    }

    cout << dp[numCities - 1];

    return 0;
}

我如何让我的算法适用于这种情况，其中较低的状态取决于较大的状态？

编辑:我按以下方式使用动态规划:对于每个城市，我计算在给定起始状态 dp[0] = 0 的情况下到达它们的最快方式。则递归关系为:dp[i] = min(dp[i - 1] + 1, dp[每隔一个具有相同传送类型的点] + R)

Answer 1

动态规划适用于问题具有最优子结构的情况。也就是说，您必须找到一种方法来分割问题，以便分割的最佳解决方案可以用作构建 block 来找到整个问题的最佳解决方案。

上面，我看你说要用动态规划。我看到了代码。我没有看到对您正在考虑的子问题的明确解释。也就是说:对解决方案的概念性理解是正确进行动态编程的关键，而这正是您没有提供的。

我的直觉是，在这种情况下动态规划不是一个好的方法，因为:

• 重新排列数组中的条目会破坏有关局部运动的信息
• 有可能从起点移动到数组中的任何条目 - 一种固有的非局部性。

您可以使用嵌套循环来解决这些问题。这为您提供了 O(n^2) 时间解决方案。

但是，将此问题视为加权图遍历的一个实例，您可以使用 Dijkstra's algorithm 来解决它。在 O(n log n + m) 时间内(O(n) 遍历足以建立每个节点的邻居)，其中 m 是考虑的边缘数量(这里可以通过识别每个传送器类型将仅使用一次来将其限制为 Θ(m) 的值)。为什么不这样做呢？

您可以尝试使用 A* 来改善运行时间，尽管我不相信这会在一个维度上提供很大的改进。

完成此操作的代码可能如下所示:

#include <iostream>
#include <queue>
#include <unordered_set>
#include <unordered_map>

typedef std::unordered_map<int, std::vector<int> > tele_network_t;

int Dijkstra(const std::vector<int> &graph, const tele_network_t &tn, const int R){
  //This whole mess makes the smallest elements pop off the priority queue first
  std::priority_queue<
    std::pair<int, int>,
    std::vector< std::pair<int, int> >,
    std::greater< std::pair<int, int> >
  > pq; //<distance, index>

  //Keeping track of the teleporters used allows us to speed up the algorithm by
  //making use of the theorem that each teleporter type will be used only once.
  std::unordered_set<int> teleporters_used; 

  //Keep track of the path
  std::vector<int> parent(graph.size(),-1); //Parent==-1 indicates an unvisited node

  //At 0 distance, place the 0th node
  pq.emplace(0,0);
  parent[0] = 0; //The only node whose parent is itself should be node 0

  while(!pq.empty()){
    const auto c = pq.top();
    pq.pop();

    //We've reached the goal node
    if(c.second==graph.size()-1){
      std::cout<<"Dist = "<<c.first<<std::endl;
      break;
    }

    //Insert neighbours
    if(c.second!=0 && parent[c.second-1]==-1){ //Left neighbour
      parent[c.second-1] = c.second;
      pq.emplace(c.first+1,c.second-1);
    }
    if(parent[c.second+1]==-1){ //Right neighbour: can't overflow because goal is the rightmost node
      parent[c.second+1] = c.second;
      pq.emplace(c.first+1,c.second+1);
    }

    //Inner loop is executed once per teleporter type
    if(teleporters_used.count(graph[c.second])==0)
      for(const auto i: tn.at(graph[c.second])){
        if(parent[i]==-1){
          pq.emplace(c.first+R,i);
          parent[i] = c.second;
        }
      }

    teleporters_used.insert(graph[c.second]);
  }

  //Trace our steps backwards to recover the path. Path will be reversed, but a
  //stack could be used to fit this.
  int p = graph.size()-1;
  while(parent[p]!=p){
    std::cout<<p<<std::endl;
    p = parent[p];
  }
  std::cout<<0<<std::endl;
}

int main(){
  tele_network_t tele_network;

  const int R = 2;
  std::vector<int> graph = {{2,1,3,4,6,8,5,7,4,2,3,5,2,1,3,4,3,5,6,7}};

  //Determine network of teleporters
  for(int i=0;i<graph.size();i++)
    tele_network[graph[i]].push_back(i);

  Dijkstra(graph, tele_network, 2);
}