在矩阵中寻找一条具有最大和的前向路径，然后再寻找一条具有最大和的反向路径。

Question

11

如果我有一个矩阵，矩阵的每个元素都是非负数。我想从左下角走到右上角。在每一步中，我只能向上或向右移动，并且每访问一个元素后都将其设置为0；之后，我从右上角向左下角走，每一步中，我只能向下或向左移动。

我的问题是如何高效地找到具有最大和的路径。

- 宇宙人

1

@kajacx 当我尝试寻找反例时，似乎当最优解是交叉路径时，我总能找到另一个没有交叉路径的最优解。 - 宇宙人

@fjardon 你觉得怎么样？你以前遇到过这个问题吗？ - 宇宙人

1

@fjardon 顺便问一下，你能否帮忙搜索另一个问题：我们有一个大小为 N x M 的二维空间矩形，该矩形由 MN 个正方形组成，每个正方形的边长均为1。我们画一条直线穿过这个矩形，那么这条直线最多可以穿过多少个正方形？（我听说原问题是在三维空间中的。） - 宇宙人

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kajacx · Accepted Answer

让我们拥有一个具有N行和M列的矩阵，并假设N≥2和M≥2，否则解决方案是微不足道的。我有一个使用动态规划运行的算法，其时间复杂度为O（max（M，N）* min（N，M）^4）。

首先，让我们证明一种最优解，其中路径不交叉（除了在起点和终点处），始终存在。我们将采取任何解决方案并将其转化为非交叉解决方案，而不降低优化函数。

证明：

首先确保第二条路径（从右上到左下）始终位于或与第一条路径相同行或更高行。通过取其中一个段落并交换它们来实现这一点。说明如下：

然后，一次只删除一个碰撞。您总是可以找到至少有一条路径在那里转弯的碰撞，并更改该路径以避免碰撞。重复此过程，直到所有碰撞都被移除。下面是一步的示例:

我们可以看到，不仅两条路径合并后没有删除任何元素，而且还添加了更多的元素，并且所有元素都是非负的，因此总和只能增加。 算法： 我们将只考虑不交叉的路径，同时假设N<=M（矩阵宽度至少与高度相同）。通常，我们会添加一列中的数字，这可以使用前缀和快速完成。

我们将从第一列开始。对于每个对(i,j)，使得1<=i<j<=N，我们将计算该对的分数，即两条路径从(1,1)开始分别覆盖(1,i)和(1,j)的总和。例如：

Matrix:
1 2 3
4 5 6
7 8 9

score(1,1) = 7
score(1,3) = 12
score(2,3) = -inf (paths cannot cross)

然后我们将计算下一列中每对的得分，该得分来自于当前列中的配对得分。对于下一列中的每对，请查看所有先前列中路径可以延伸以匹配当前列路径的配对。

最后，你的答案是最后一列中对的得分。很抱歉我不擅长在文字媒体上解释算法，希望它不完全不能理解。