c++ - 在网格中找到最佳路径的最大长度

Question

给定一个N*N的网格，现在我们需要找到一条最大长度的好路径，好路径定义如下:

1. 好的路径总是从标记为 0 的单元格开始
2. 我们只能向左、向右、向上或向下移动
3. 如果第 i 个单元格的值为 A，则路径中下一个单元格的值必须为 A+1。

现在给定这几个条件，我需要找出可以走的最大路径的长度。我还需要计算最大长度的路径。

例子:设 N=3，我们有 3*3 矩阵如下:

0 3 2               
3 0 1               
2 1 0            

那么这里的最大好路径长度是3，这样好路径的数量是4。

0 3 2
3 0 1
2 1 0

0 3 2
3 0 1
2 1 0

0 3 2
3 0 1
2 1 0

0 3 2
3 0 1
2 1 0

Answer 1

此问题是 Longest Path Problem 的变体，但是您的限制使这个问题变得容易得多，因为该图实际上是一个 Directed Acyclic Graph (DAG) , 因此该问题是可以有效解决的。

定义有向图 G=(V,E) 如下:

• V = { 矩阵中的所有单元格}(完整性检查:|V| = N^2)
• E = { (u,v) | u 与 v 相邻且 value(u) + 1 = value(v)

请注意，上面定义的结果图是一个 DAG，因为你不能有任何循环，因为它会导致有一些边 e= (u,v) 这样 值(u) > 值(v)。

现在，你只需要找到longest path in a DAG从任何起点。这是由 topological sort 完成的在图上，然后使用动态规划:

init:
for every source in the DAG:
D(v) = 0            if value(v) = 0
       -infinity    otherwise
step:
for each node v from first to last (according to topological sort)
   D(v) = max{D(u) + 1 | for each edge (u,v) }

完成后，找到具有最大值D(v) 的节点v，这是最长“好路径”的长度。
找到路径本身是通过重新滚动上面的过程来完成的，从最大 D(v) 向后追溯你的步骤，直到你回到值为 0 的初始节点。

这种方法的复杂度是 O(V+E) = O(n^2)

---

由于您正在寻找最长路径的数量，因此您可以稍微修改此解决方案以计算到达每个节点的路径数量，如下所示:

Topological sort the nodes, let the sorted array be arr (1)
For each node v from start to end of arr:
   if value(v) = 0:
        set D(v) = 1 
   else
        sum = 0
        for each u such that (u,v) is an edge: (2)
            sum = sum + D(u) 
        D(v) = sum

以上将为每个节点v 找到到达它的“好路径”D(v) 的数量。您现在要做的就是找到具有总和节点 v 的最大值 x 使得 value(v) = x 和 D(v) > 0，将到达任意节点的路径数与value(v)相加:

max = 0
numPaths = 0
for each node v:
    if value(v) == max:
         numPaths = numPaths + D(v)
    else if value(v) > max AND D(v) > 0:
         numPaths = D(v)
         max = value(v)
return numPaths

注意事项: (1) - “常规”排序在这里起作用，但需要 O(n^2logn) 时间，而拓扑排序需要 O(n^2) 时间
(2) 提醒，(u,v) 是一条边，如果: (1) u 和 v 相邻 (2) value(u) + 1 = 值(v)