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

大佬教程收集整理的这篇文章主要介绍了查找网格中最佳路径的最大长度，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

如何解决查找网格中最佳路径的最大长度？@H_673_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)：

@H_573_5@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）

解决方法@H_673_1@

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

大佬总结

以上是大佬教程为你收集整理的查找网格中最佳路径的最大长度全部内容，希望文章能够帮你解决查找网格中最佳路径的最大长度所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。