如何找到最小和的路径，在二进制矩阵中向右和向下移动
How to find the path of least sum, moving right and down in a binary matrix
我有一个二进制矩阵。每列对应于图中的一个顶点。如果我沿着路径行走（从“col 1”顶点开始，然后移动到“col 2”等），我必须支付一些罚款。但是由于路径上只有这么多警察，所以我可以等一段时间，直到下一个顶点没有剩下的警察，然后再过去。为了澄清，以下矩阵（第一行是“标题”行）：
A B C D
0 0 1 0
1 0 0 1
1 1 0 0
1 1 1 1
0 0 0 0
如果我在那个点之前额外等待 1、2 或 3 小时后在 A 上，我将支付的编码；在 B 上，我会在 2 或 3 小时后付款；在 C 上，我将在 0 或 3 小时后付款；在D，等一三个小时我就付钱
因此，这里的最优路径是“到B，等1小时，到C，等1小时，再到D”，总成本为0。（这条路径上标有“X”以下）
A B C D
X X 1 0
1 X X 1
1 1 X X
1 1 1 1
0 0 0 0
然而，实现 0 并不总是可能的，我只对从左上角条目到右列的最小总和路径之一感兴趣。
如何有效地生成这样的路径？
天真的算法“生成所有路径，找到最小值”在指数时间内工作，这对我来说不是最优的。
我想过使用 DP 方法，但我无法制定在某些情况下不会中断的方法，无论我尝试添加 line-by-line 还是 column-by-column
让我们从一个简单的问题开始。假设您位于矩阵的行 i、列 j（即单元格 (i,j)）。下一步你有什么选择？
由于我们要移动 column-wise，j 变为 j+1。但是对于该行，您可以贪婪地选择支付最低罚款的行。也就是说，您可以在范围 (i+1, row_count) 中选择 i'，以使 fine(i,j) 最小。 （注意：由于该行代表时间点，您不能从行 i 转到 i-1，有效地缩短了我们的搜索 space）。
算法：
(n = number of rows = len(matrix), m = number of columns)
- 对于最右边的列，我们没有任何进一步的路径，因此不需要修改
- 对于列
m-1 to 1，单元格 (i,j) 的最低罚款为
fine(i,j) = (matrix[i][j] == 1) + (min_value in matrix[i][j+1] to matrix[n][j+1])
- 最小路径成本将为
matrix[0][0]，您可以通过检查每一列的最小值来追踪路径。
最后一点我们需要讲的是，如何在步骤 2 中得到 min_value in matrix[i][j+1] to matrix[n][j+1]？如果您从 row n 遍历到 row 1，任务基本上归结为跟踪已访问过的最小元素，这可以使用简单的 variable/counter.
来完成
该方法不需要额外的 space（因为我们修改了给定的矩阵）和 O(M*N) 时间复杂度。
我有一个二进制矩阵。每列对应于图中的一个顶点。如果我沿着路径行走（从“col 1”顶点开始，然后移动到“col 2”等），我必须支付一些罚款。但是由于路径上只有这么多警察，所以我可以等一段时间，直到下一个顶点没有剩下的警察，然后再过去。为了澄清，以下矩阵（第一行是“标题”行）：
A B C D
0 0 1 0
1 0 0 1
1 1 0 0
1 1 1 1
0 0 0 0
如果我在那个点之前额外等待 1、2 或 3 小时后在 A 上，我将支付的编码；在 B 上，我会在 2 或 3 小时后付款；在 C 上，我将在 0 或 3 小时后付款；在D，等一三个小时我就付钱
因此，这里的最优路径是“到B，等1小时，到C，等1小时，再到D”，总成本为0。（这条路径上标有“X”以下）
A B C D
X X 1 0
1 X X 1
1 1 X X
1 1 1 1
0 0 0 0
然而，实现 0 并不总是可能的，我只对从左上角条目到右列的最小总和路径之一感兴趣。
如何有效地生成这样的路径？
天真的算法“生成所有路径，找到最小值”在指数时间内工作，这对我来说不是最优的。
我想过使用 DP 方法，但我无法制定在某些情况下不会中断的方法，无论我尝试添加 line-by-line 还是 column-by-column
让我们从一个简单的问题开始。假设您位于矩阵的行 i、列 j（即单元格 (i,j)）。下一步你有什么选择？
由于我们要移动 column-wise，j 变为 j+1。但是对于该行，您可以贪婪地选择支付最低罚款的行。也就是说，您可以在范围 (i+1, row_count) 中选择 i'，以使 fine(i,j) 最小。 （注意：由于该行代表时间点，您不能从行 i 转到 i-1，有效地缩短了我们的搜索 space）。
算法：
(n = number of rows = len(matrix), m = number of columns)
- 对于最右边的列，我们没有任何进一步的路径，因此不需要修改
- 对于列
m-1 to 1，单元格(i,j)的最低罚款为
fine(i,j) = (matrix[i][j] == 1) + (min_value in matrix[i][j+1] to matrix[n][j+1])
- 最小路径成本将为
matrix[0][0]，您可以通过检查每一列的最小值来追踪路径。
最后一点我们需要讲的是，如何在步骤 2 中得到 min_value in matrix[i][j+1] to matrix[n][j+1]？如果您从 row n 遍历到 row 1，任务基本上归结为跟踪已访问过的最小元素，这可以使用简单的 variable/counter.
该方法不需要额外的 space（因为我们修改了给定的矩阵）和 O(M*N) 时间复杂度。