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

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

此问题是“
最长路径问题”的变体，但是您的限制使此问题更加容易，因为该图实际上是有向无环图（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    otherwisestep: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 = 0numPaths = 0for 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）