找到最大一笔向前然后向后路径的交叉矩阵 [英] find path cross matrix with max sum forward then backward

问题描述

如果我有一个矩阵，该矩阵的每个元素是一个非负的数。我想走过矩阵从左下角到右上角。在每一个步骤我只能移动向上或向右，和访问的每一个元件将被设置为0;在那之后，我走从右上角到左下角回来了，我的每一步只能向下移动或向左。

If I have a matrix, every element of the matrix is a non-negative number. I want to walk through the matrix from left-bottom corner to the right-top corner. In every step I can only move upward or rightward, and every visited element will be set to 0; after that, I walk back from the right-top corner to the left-bottom corner, every step I can only move downward or leftward.

我的问题是如何有效地找到最大金额的路径。

My question is how to efficiently find a path with max sum.

推荐答案

让我们用 N A矩阵行 M 列，并假设 N'GT; = 2 和 M＆GT; = 2 ，否则解决方案是微不足道的。我有一个算法运行在 O（MAX（M，N）*分（N，M）^ 4）使用动态规划。

Let's have a matrix with N rows and M columns and assume that N>=2 and M>=2, otherwise the solution is trivial. I have an algorithm running in O(max(M,N) * min(N,M)^4) using dynamic programming.

首先，让我们证明了一个最佳的解决方案，其中的路径不交叉（除了在开头和结尾）总是存在的。我们将采取任何溶液和变换成非交叉1而不降低功能优化

First, let's prove that an optimal solution where the paths don't cross (except at start and end) always exists. We will take any solution and transform in into a non-crossing one without lowering the optimization function.

证明：

通过确保第二路径（从右上角到左下角的）总是高于或在相同行作为第一路径开始。做到这一点的同时服用的路径在哪里，这是不正确的单个部分，并交换它们。图：

Start by ensuring that the second path (from top-right to bottom-left) is always above or at the same row as the first path. Do that by taking a single section of both path where this isn't true, and swap them. Illustration:

然后，取出一次一个碰撞。你总是可以找到一个碰撞，使得至少一个路由转向那里，你可以改变这条道路，以避免碰撞。重复，直到所有冲突都被删除。插图一步的：

Then, remove one collision at a time. You can always find a collision such that at least one route is turning there, and you can change that path to avoid the collision. Repeat this until all collisions are removed. Illustration of one step:

我们看到，不仅没有元素，我们从两个路径组合中删除，但更多的元素被添加，所有的元素都是非负，因此，总和只会上涨。

We see that not only no elements we removed from both paths combined, but more elements have been added, and all elements are non-negative, so the sum could only go up.

的算法：

我们将只考虑不交叉路径，也是我假设 N'LT; = M （矩阵宽至少为高度）。通常，我们将添加数从一栏，可以快速使用 $ P完成$ PFIX总和。

We will only consider paths that don't cross, also I'll assume that N<=M (the matrix wide at least as height). Often we will add number from one column, that can be done quickly using Prefix sum.

我们将开始的第一列。对于每一对（I，J），使得 1＆LT; = I＆LT; J＆LT; = N ，我们将计算出的分数的那一对，即的多少可以两个路径盖起始于（1,1）和分别在（1，i）和（1，j）的结束的总和。例如：

We will start at the first column. For each pair (i,j) such that 1<=i<j<=N we will compute the score of that pair, that is the sum of how much can both paths cover starting at (1,1) and ending at (1,i) and (1,j) respectively. Example:

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)

然后，我们将计算得分的每对中，从对在当前列中的得分的下一列。对于每一对在​​下一栏，只需看一下其路径可以扩展以满足当前列的路径previous列中的所有对。

Then we will compute score of each pair in the next column from the score of pairs in current column. For each pair in the next column, simply look at all the pairs in the previous column whose path can be extended to match the path of current column.

最后，你的答案是对（N-1，N）在最后一栏的分数。我道歉，我是可怕的，在解释算法过书面的媒体，我希望这不是完全取消understable。

Finally, your answer is the score of pair (N-1, N) in the last column. I apologise for I am terrible at explaining algorithms over written media, I hope it's not completely un-understable.

这篇关于找到最大一笔向前然后向后路径的交叉矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！