查找网格中最佳路径的最大长度

  • Z时代
  • 2024-01-10
  • 分类：问答

给定一个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 1 0

0 3 2

1

0

0

3 0

2 1

0 3 2

0 1

回答：

此问题是“

最长路径问题”的变体，但是您的限制使此问题更加容易，因为该图实际上是有向无环图（DAG），因此该问题可以有效解决。

定义有向图G=(V,E)，如下所示：

  • V = { all cells in the matrix} （健全性检查：| V | = N ^ 2）

  • E = { (u,v) | u is adjacent to v AND value(u) + 1 = value(v) }

请注意，根据上述定义，生成的图形是DAG，因为您不能有任何循环，因为它会导致具有e= (u,v)诸如的边value(u) > value(v)。

现在，您只需从任何起点在DAG中找到最长的路径。这是通过对图进行拓扑排序，然后使用动态编程来完成的：

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) }

完成后，找到v具有最大值的节点D(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)。所有你现在要做的，就是找到的最大价值x在于拥有和节点v，使得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）值（u）+ 1 =值（v）

以上是 查找网格中最佳路径的最大长度 的全部内容， 来源链接： utcz.com/qa/402156.html

回到顶部