在网格中找到最佳路径的最大长度
Find maximum length of good path in a grid
给定一个 N*N grid.Now 我们需要找到一条最大长度的好路径，其中好路径定义如下：
- 好的路径总是从标记为 0 的单元格开始
- 我们只能向左、向右、向上或向下移动
- 如果第 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
这个问题是 Longest Path Problem, however your restrictions make this problem much easier, since the graph is actually a Directed Acyclic Graph (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).
现在，你只需要在图上找到longest path in a DAG from any starting point. This is done by 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，这是最长"good path"的长度。
找到路径本身是通过重新滚动上面的过程来完成的，从最大 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找到到达它的"good paths"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) - "regular" 排序在这里有效，但需要 O(n^2logn) 时间，而拓扑排序需要 O(n^2) 时间
(2) 提示，(u,v) 是一条边，如果： (1) u 和 v 相邻 (2) value(u) + 1 = value(v)
您可以使用简单的广度优先搜索来做到这一点。
首先找到所有标记为 0 的单元格。（这是 O(N2)。）在每个这样的单元格上放一个助行器。每个walker携带一个初始化为1的数字'p'。
现在迭代：
所有步行者都站在相同编号 k 的单元格上。每个 walker 寻找标记为 k+1 的相邻单元格（左、右、上或下）。
如果没有步行者看到这样的单元格，搜索结束。最长路径的长度是k，这样的路径的数量是所有步行者p的总和。
如果一些步行者看到这样的数字，杀死任何没有看到的步行者。
每个助行器都移动到一个好的相邻单元格中。如果一个 walker 看到不止一个好细胞，它就会分成与好细胞数量一样多的 walker，每个 walker 进入一个。 （每个 "child" 具有与 "parent" 相同的 p 值。）如果两个或多个步行者在同一个单元格中相遇（即，如果不止一条路径通向该单元格），那么它们会合并变成一个步行者，其 'p' 值是它们 'p' 值的总和。
这个算法是O(N2)，因为每个cell都不能被访问超过一次，walker的数量不能超过cell的数量
我是用 ActionScript 做的，希望它是可读的。我认为它工作正常，但我可能遗漏了一些东西。
const N:int = 9; // field size
const MIN_VALUE:int = 0; // start value
var field:Array = [];
// create field - not relevant to the task
var probabilities:Array = [0,1,2,3,4,5];
for (var i:int = 0; i < N * N; i++) field.push(probabilities[int(Math.random() * probabilities.length)]);//RANGE));
print_field();
// initial chain fill. We will find any chains of adjacent 0-1 elements.
var chain_list:Array = [];
for (var offset:int = 0; offset < N * N - 1; offset++) {
if (offset < N * N - N) { // y coordinate is not the lowest
var chain:Array = find_chain(offset, offset + N, MIN_VALUE);
if (chain) chain_list.push(chain);
}
if ((offset % N) < N - 1) { // x coordinate is not the rightmost
chain = find_chain(offset, offset + 1, MIN_VALUE);
if (chain) chain_list.push(chain);
}
}
var merged_chain_list:Array = chain_list;
var current_value:int = MIN_VALUE + 1;
// for each found chain, scan its higher end for more attached chains
// and merge them into new chain if found
while(chain_list.length) {
chain_list = [];
for (i = 0; i < merged_chain_list.length; i++) {
chain = merged_chain_list[i];
offset = chain[chain.length - 1];
if (offset < N * N - N) {
var tmp:Array = find_chain(offset, offset + N, current_value);
if (tmp) chain_list.push(merge_chains(chain, tmp));
}
if (offset > N) {
tmp = find_chain(offset, offset - N, current_value);
if (tmp) chain_list.push(merge_chains(chain, tmp));
}
if ((offset % N) < N - 1) {
tmp = find_chain(offset, offset + 1, current_value);
if (tmp) chain_list.push(merge_chains(chain, tmp));
}
if (offset % N) {
tmp = find_chain(offset, offset - 1, current_value);
if (tmp) chain_list.push(merge_chains(chain, tmp));
}
}
//save the last merged result if any and try the next value
if (chain_list.length) {
merged_chain_list = chain_list;
current_value++;
}
}
// final merged list is a list of chains of a same maximum length
print_chains(merged_chain_list);
function find_chain(offset1, offset2, current_value):Array {
// returns always sorted sorted from min to max
var v1:int = field[offset1];
var v2:int = field[offset2];
if (v1 == current_value && v2 == current_value + 1) return [offset1, offset2];
if (v2 == current_value && v1 == current_value + 1) return [offset2, offset1];
return null;
}
function merge_chains(chain1:Array, chain2:Array):Array {
var tmp:Array = [];
for (var i:int = 0; i < chain1.length; i++) tmp.push(chain1[i]);
tmp.push(chain2[1]);
return tmp;
}
function print_field():void {
for (var pos_y:int = 0; pos_y < N; pos_y++) {
var offset:int = pos_y * N;
var s:String = "";
for (var pos_x:int = 0; pos_x < N; pos_x++) {
var v:int = field[offset++];
if (v == 0) s += "[0]"; else s += " " + v + " ";
}
trace(s);
}
}
function print_chains(chain_list):void {
var cl:int = chain_list.length;
trace("\nchains found: " + cl);
if (cl) trace("chain length: " + chain_list[0].length);
for (var i:int = 0; i < cl; i++) {
var chain:Array = chain_list[i];
var s:String = "";
for (var j:int = 0; j < chain.length; j++) s += chain[j] + ":" + field[chain[j]] + " ";
trace(s);
}
}
示例输出：
1 2 1 3 2 2 3 2 4
4 3 1 2 2 2 [0][0] 1
[0][0] 1 2 4 [0] 3 3 1
[0][0] 5 4 1 1 [0][0] 1
2 2 3 4 3 2 [0] 1 5
4 [0] 3 [0] 3 1 4 3 1
1 2 2 3 5 3 3 3 2
3 4 2 1 2 4 4 4 5
4 2 1 2 2 3 4 5 [0]
chains found: 2
chain length: 5
23:0 32:1 41:2 40:3 39:4
33:0 32:1 41:2 40:3 39:4
我用我自己的 Lisp 方言实现了它，所以源代码不会对你有太大帮助:-) ...
编辑：也添加了 Python 版本。
无论如何，想法是：
- 写一个函数
paths(i, j) --> (maxlen, number)，returns 从(i, j) 开始的路径的最大长度以及存在的路径数量..
- 此函数是递归的，查看
(i, j) 的邻居值为 M[i][j]+1 将调用 paths(ni, nj) 以获得有效邻居的结果
- 如果邻居的最大长度大于当前最大长度，则设置新的当前最大长度并重置计数器
- 如果最大长度与当前相同，则将计数器添加到总数中
- 如果最大长度更小，则忽略该邻居结果
- 缓存单元格的计算结果（这很重要！）。在我的版本中，代码分为两个相互递归的函数：
paths 首先检查缓存，否则调用 compute-paths； compute-paths 在处理邻居时调用 paths。递归调用的缓存大致相当于显式动态规划方法，但有时更容易实现。
要计算最终结果，您基本上执行相同的计算，但将所有 0 个单元格的结果相加，而不是考虑邻居。
请注意，不同路径的数量可能会变得巨大，这就是为什么枚举所有路径不是一个可行的选择，而 caching/DP 是必须的：例如，对于具有值的 N=20 矩阵M[i][j] = i+j 长度为 38 的最大路径有 35,345,263,800 条。
此算法的时间复杂度为 O(N^2)（每个单元格最多访问一次），缓存和递归需要 O(N^2) space。当然，鉴于输入由 N^2 个数字本身组成，并且您至少需要阅读它们才能计算出答案，因此您不能指望得到比这更好的结果。
(defun good-paths (matrix)
(let** ((N (length matrix))
(cache (make-array (list N N)))
(#'compute-paths (i j)
(let ((res (list 0 1))
(count (1+ (aref matrix i j))))
(dolist ((ii jj) (list (list (1+ i) j) (list (1- i) j)
(list i (1+ j)) (list i (1- j))))
(when (and (< -1 ii N) (< -1 jj N)
(= (aref matrix ii jj) count))
(let (((maxlen num) (paths ii jj)))
(incf maxlen)
(cond
((< (first res) maxlen)
(setf res (list maxlen num)))
((= (first res) maxlen)
(incf (second res) num))))))
res))
(#'paths (i j)
(first (or (aref cache i j)
(setf (aref cache i j)
(list (compute-paths i j))))))
(res (list 0 0)))
(dotimes (i N)
(dotimes (j N)
(when (= (aref matrix i j) 0)
(let (((maxlen num) (paths i j)))
(cond
((< (first res) maxlen)
(setf res (list maxlen num)))
((= (first res) maxlen)
(incf (second res) num)))))))
res))
编辑
下面是Python上面的音译，如果你以前没有接触过Lisp，应该更容易理解...
def good_paths(matrix):
N = len(matrix)
cache = [[None]*N for i in xrange(N)] # an NxN matrix of None
def compute_paths(i, j):
maxlen, num = 0, 1
count = 1 + matrix[i][j]
for (ii, jj) in ((i+1, j), (i-1, j), (i, j-1), (i, j+1)):
if 0 <= ii < N and 0 <= jj < N and matrix[ii][jj] == count:
nh_maxlen, nh_num = paths(ii, jj)
nh_maxlen += 1
if maxlen < nh_maxlen:
maxlen = nh_maxlen
num = nh_num
elif maxlen == nh_maxlen:
num += nh_num
return maxlen, num
def paths(i, j):
res = cache[i][j]
if res is None:
res = cache[i][j] = compute_paths(i, j)
return res
maxlen, num = 0, 0
for i in xrange(N):
for j in xrange(N):
if matrix[i][j] == 0:
c_maxlen, c_num = paths(i, j)
if maxlen < c_maxlen:
maxlen = c_maxlen
num = c_num
elif maxlen == c_maxlen:
num += c_num
return maxlen, num
给定一个 N*N grid.Now 我们需要找到一条最大长度的好路径，其中好路径定义如下：
- 好的路径总是从标记为 0 的单元格开始
- 我们只能向左、向右、向上或向下移动
- 如果第 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
这个问题是 Longest Path Problem, however your restrictions make this problem much easier, since the graph is actually a Directed Acyclic Graph (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).
现在，你只需要在图上找到longest path in a DAG from any starting point. This is done by 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，这是最长"good path"的长度。
找到路径本身是通过重新滚动上面的过程来完成的，从最大 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找到到达它的"good paths"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) - "regular" 排序在这里有效，但需要 O(n^2logn) 时间，而拓扑排序需要 O(n^2) 时间
(2) 提示，(u,v) 是一条边，如果： (1) u 和 v 相邻 (2) value(u) + 1 = value(v)
您可以使用简单的广度优先搜索来做到这一点。
首先找到所有标记为 0 的单元格。（这是 O(N2)。）在每个这样的单元格上放一个助行器。每个walker携带一个初始化为1的数字'p'。
现在迭代：
所有步行者都站在相同编号 k 的单元格上。每个 walker 寻找标记为 k+1 的相邻单元格（左、右、上或下）。
如果没有步行者看到这样的单元格，搜索结束。最长路径的长度是k，这样的路径的数量是所有步行者p的总和。
如果一些步行者看到这样的数字，杀死任何没有看到的步行者。
每个助行器都移动到一个好的相邻单元格中。如果一个 walker 看到不止一个好细胞，它就会分成与好细胞数量一样多的 walker，每个 walker 进入一个。 （每个 "child" 具有与 "parent" 相同的 p 值。）如果两个或多个步行者在同一个单元格中相遇（即，如果不止一条路径通向该单元格），那么它们会合并变成一个步行者，其 'p' 值是它们 'p' 值的总和。
这个算法是O(N2)，因为每个cell都不能被访问超过一次，walker的数量不能超过cell的数量
我是用 ActionScript 做的，希望它是可读的。我认为它工作正常，但我可能遗漏了一些东西。
const N:int = 9; // field size
const MIN_VALUE:int = 0; // start value
var field:Array = [];
// create field - not relevant to the task
var probabilities:Array = [0,1,2,3,4,5];
for (var i:int = 0; i < N * N; i++) field.push(probabilities[int(Math.random() * probabilities.length)]);//RANGE));
print_field();
// initial chain fill. We will find any chains of adjacent 0-1 elements.
var chain_list:Array = [];
for (var offset:int = 0; offset < N * N - 1; offset++) {
if (offset < N * N - N) { // y coordinate is not the lowest
var chain:Array = find_chain(offset, offset + N, MIN_VALUE);
if (chain) chain_list.push(chain);
}
if ((offset % N) < N - 1) { // x coordinate is not the rightmost
chain = find_chain(offset, offset + 1, MIN_VALUE);
if (chain) chain_list.push(chain);
}
}
var merged_chain_list:Array = chain_list;
var current_value:int = MIN_VALUE + 1;
// for each found chain, scan its higher end for more attached chains
// and merge them into new chain if found
while(chain_list.length) {
chain_list = [];
for (i = 0; i < merged_chain_list.length; i++) {
chain = merged_chain_list[i];
offset = chain[chain.length - 1];
if (offset < N * N - N) {
var tmp:Array = find_chain(offset, offset + N, current_value);
if (tmp) chain_list.push(merge_chains(chain, tmp));
}
if (offset > N) {
tmp = find_chain(offset, offset - N, current_value);
if (tmp) chain_list.push(merge_chains(chain, tmp));
}
if ((offset % N) < N - 1) {
tmp = find_chain(offset, offset + 1, current_value);
if (tmp) chain_list.push(merge_chains(chain, tmp));
}
if (offset % N) {
tmp = find_chain(offset, offset - 1, current_value);
if (tmp) chain_list.push(merge_chains(chain, tmp));
}
}
//save the last merged result if any and try the next value
if (chain_list.length) {
merged_chain_list = chain_list;
current_value++;
}
}
// final merged list is a list of chains of a same maximum length
print_chains(merged_chain_list);
function find_chain(offset1, offset2, current_value):Array {
// returns always sorted sorted from min to max
var v1:int = field[offset1];
var v2:int = field[offset2];
if (v1 == current_value && v2 == current_value + 1) return [offset1, offset2];
if (v2 == current_value && v1 == current_value + 1) return [offset2, offset1];
return null;
}
function merge_chains(chain1:Array, chain2:Array):Array {
var tmp:Array = [];
for (var i:int = 0; i < chain1.length; i++) tmp.push(chain1[i]);
tmp.push(chain2[1]);
return tmp;
}
function print_field():void {
for (var pos_y:int = 0; pos_y < N; pos_y++) {
var offset:int = pos_y * N;
var s:String = "";
for (var pos_x:int = 0; pos_x < N; pos_x++) {
var v:int = field[offset++];
if (v == 0) s += "[0]"; else s += " " + v + " ";
}
trace(s);
}
}
function print_chains(chain_list):void {
var cl:int = chain_list.length;
trace("\nchains found: " + cl);
if (cl) trace("chain length: " + chain_list[0].length);
for (var i:int = 0; i < cl; i++) {
var chain:Array = chain_list[i];
var s:String = "";
for (var j:int = 0; j < chain.length; j++) s += chain[j] + ":" + field[chain[j]] + " ";
trace(s);
}
}
示例输出：
1 2 1 3 2 2 3 2 4
4 3 1 2 2 2 [0][0] 1
[0][0] 1 2 4 [0] 3 3 1
[0][0] 5 4 1 1 [0][0] 1
2 2 3 4 3 2 [0] 1 5
4 [0] 3 [0] 3 1 4 3 1
1 2 2 3 5 3 3 3 2
3 4 2 1 2 4 4 4 5
4 2 1 2 2 3 4 5 [0]
chains found: 2
chain length: 5
23:0 32:1 41:2 40:3 39:4
33:0 32:1 41:2 40:3 39:4
我用我自己的 Lisp 方言实现了它，所以源代码不会对你有太大帮助:-) ...
编辑：也添加了 Python 版本。
无论如何，想法是：
- 写一个函数
paths(i, j) --> (maxlen, number)，returns 从(i, j)开始的路径的最大长度以及存在的路径数量.. - 此函数是递归的，查看
(i, j)的邻居值为M[i][j]+1将调用paths(ni, nj)以获得有效邻居的结果 - 如果邻居的最大长度大于当前最大长度，则设置新的当前最大长度并重置计数器
- 如果最大长度与当前相同，则将计数器添加到总数中
- 如果最大长度更小，则忽略该邻居结果
- 缓存单元格的计算结果（这很重要！）。在我的版本中，代码分为两个相互递归的函数：
paths首先检查缓存，否则调用compute-paths；compute-paths在处理邻居时调用paths。递归调用的缓存大致相当于显式动态规划方法，但有时更容易实现。
要计算最终结果，您基本上执行相同的计算，但将所有 0 个单元格的结果相加，而不是考虑邻居。
请注意，不同路径的数量可能会变得巨大，这就是为什么枚举所有路径不是一个可行的选择，而 caching/DP 是必须的：例如，对于具有值的 N=20 矩阵M[i][j] = i+j 长度为 38 的最大路径有 35,345,263,800 条。
此算法的时间复杂度为 O(N^2)（每个单元格最多访问一次），缓存和递归需要 O(N^2) space。当然，鉴于输入由 N^2 个数字本身组成，并且您至少需要阅读它们才能计算出答案，因此您不能指望得到比这更好的结果。
(defun good-paths (matrix)
(let** ((N (length matrix))
(cache (make-array (list N N)))
(#'compute-paths (i j)
(let ((res (list 0 1))
(count (1+ (aref matrix i j))))
(dolist ((ii jj) (list (list (1+ i) j) (list (1- i) j)
(list i (1+ j)) (list i (1- j))))
(when (and (< -1 ii N) (< -1 jj N)
(= (aref matrix ii jj) count))
(let (((maxlen num) (paths ii jj)))
(incf maxlen)
(cond
((< (first res) maxlen)
(setf res (list maxlen num)))
((= (first res) maxlen)
(incf (second res) num))))))
res))
(#'paths (i j)
(first (or (aref cache i j)
(setf (aref cache i j)
(list (compute-paths i j))))))
(res (list 0 0)))
(dotimes (i N)
(dotimes (j N)
(when (= (aref matrix i j) 0)
(let (((maxlen num) (paths i j)))
(cond
((< (first res) maxlen)
(setf res (list maxlen num)))
((= (first res) maxlen)
(incf (second res) num)))))))
res))
编辑
下面是Python上面的音译，如果你以前没有接触过Lisp，应该更容易理解...
def good_paths(matrix):
N = len(matrix)
cache = [[None]*N for i in xrange(N)] # an NxN matrix of None
def compute_paths(i, j):
maxlen, num = 0, 1
count = 1 + matrix[i][j]
for (ii, jj) in ((i+1, j), (i-1, j), (i, j-1), (i, j+1)):
if 0 <= ii < N and 0 <= jj < N and matrix[ii][jj] == count:
nh_maxlen, nh_num = paths(ii, jj)
nh_maxlen += 1
if maxlen < nh_maxlen:
maxlen = nh_maxlen
num = nh_num
elif maxlen == nh_maxlen:
num += nh_num
return maxlen, num
def paths(i, j):
res = cache[i][j]
if res is None:
res = cache[i][j] = compute_paths(i, j)
return res
maxlen, num = 0, 0
for i in xrange(N):
for j in xrange(N):
if matrix[i][j] == 0:
c_maxlen, c_num = paths(i, j)
if maxlen < c_maxlen:
maxlen = c_maxlen
num = c_num
elif maxlen == c_maxlen:
num += c_num
return maxlen, num