1

我有一个n*n矩阵，其中每个元素代表一个整数。从[0,0]我必须找到精确m到最后一行的元素的路径，返回最大成本。路径可以在最后一行的任何列结束，并且n ≤ m ≤ n^2

我想找到所有长度m从[0,0]到的路径[n-1, 0], [n-1, 1] ... [n-1, n-1]。但是感觉不是很理想...

哪种算法是最有效的方法？BFS 还是 DFS？

编辑

可能的方向是向下/向右/向左，但每个元素最多只能访问一次。

编辑 2

例如，如果给定这个矩阵（n=4）：

[   1   4   1  20 ]
[   5   0   2   8 ]
[   6   8   3   8 ]
[   3   2   9   5 ]

m=7，路径可以是

[   →   →   →   ↓ ]
[   5   0   2   ↓ ]
[   6   8   3   ↓ ]
[   3   2   9   x ] = Path cost = 47

或者

[   ↓   4   1  20 ]
[   ↓   0   2   8 ]
[   →   →   ↓   8 ]
[   3   2   →   x ] = Path cost = 32

或者如果m = n^2

[   →   →   →   ↓ ]
[   ↓   ←   ←   ← ]
[   →   →   →   ↓ ]
[   x   ←   ←   ← ]

编辑 3 / 解决方案

感谢 Wanderley Guimarães， http:
//ideone.com/0iLS2

4

4 回答 4

2

你可以用动态规划解决这个问题。让矩阵value(i, j)位置(i, j)的值（第 i 行，第 j 列）。

if i <  0 then f(i, j) = 0
if i == 0 then f(i, j) = value(i, j)
if i >  0 then f(i, j) = max(f(i-1, j), f(i, j-1)) + value(i, j)

该重复假设您在下台时使用矩阵中的位置。所以，你的答案是max(f(m, 0), f(m-1, 1), f(m - 2, 2), ..., f(1, m))。

例如：

给出以下矩阵n = 4：

1 1 1 1
1 2 1 1
2 1 1 1
1 2 1 1

如果m = 2那么你不能去第二行。而你的答案是f(2, 2) = 4。

如果m = 4那么你不能去第三行。而你的答案是f(3, 2) = 5。

（我正在学习英语，所以如果您不明白某些内容，请告诉我，我会尽力改进我的解释）。

编辑 :: 允许向下/向左/向右移动

您可以实现以下重复：

if i == n, j == n, p == m, j == 0 then f(i, j, p, d) = 0
if d == DOWN  then f(i, j, p, d) = max(f(i+1, j, p+1, DOWN), f(i, j-1, p+1, RIGHT),   f(i, j+1, p+1,LEFT)) + value(i, j)
if d == LEFT  then f(i, j, p, d) = max(f(i+1, j, p+1, DOWN), f(i, j+1, p+1, LEFT )) + value(i, j)
if d == RIGHT then f(i, j, p, d) = max(f(i+1, j, p+1, DOWN), f(i, j-1, p+1, RIGHT)) + value(i, j)

这个解决方案是O(n^4)。我正在努力改进它。

您可以在http://ideone.com/tbH1j进行测试

于 2012-10-05T10:53:00.290 回答
1

这个问题是众所周知的。最有效的方法是动态规划。

Letdp[i][j]是从 0,0 到 i,j 时的最大总和。
然后，dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];

完成此操作后，检查您能够到达的每个位置值并获得最大值。

于 2012-10-05T10:37:21.280 回答
1

这实际上是一个 DAG，因此最长路径问题的动态规划解决方案有效。

你说为什么是 DAG？从水平相邻的两个顶点开始有一个明显的循环。当然，如果您使用“明显”的图表。

不太明显的方法是将其重新设计为（顶点，方向）的图形，其中方向是您从下/左/右采取的最后一个方向。具有向下方向的顶点可以向下、向左或向右，而具有向右方向的顶点只能向下/向右，而具有向左方向的顶点只能向左/向下。该图显然是无环的，它包含原始矩阵中的所有可能路径。

因此，忽略 limit m，到 (a, b, direction) 的最长路径的可能递归是

pdl[i][j] = max(pdl[i][j-1], pd[i-1][j])+arr[i][j];
pdr[i][j] = max(pdr[i][j+1], pd[i-1][j])+arr[i][j];
pd[i][j] = max(pdl[i][j], pdr[i][j]);

pd是“向下”顶点的数组，pdr右边pdl是左边的。作为一个实现细节，请注意我将左侧的最大值和对应的向下顶点保留在 中pdl，但这并不重要，因为任何具有“向下”方向的顶点都可以像“左侧”顶点一样向左和向下移动。对pdr.

限制意味着您必须向该 DP 解决方案添加另一个维度，也就是说，您必须保持pd[i][j][moves], 保持尽可能高的总和，直到顶点 (i, j) 使用精确moves的移动，获得递归

pdl[i][j][moves] = max(pdl[i][j-1][moves-1], pd[i-1][j][moves-1])+arr[i][j ];
pdr[i][j][moves] = max(pdr[i][j+1][moves-1], pd[i-1][j][moves-1])+arr[i][j ];
pd[i][j][moves] = max(pdl[i][j][moves-1], pdr[i][j][moves-1]);
于 2012-10-05T16:32:38.023 回答
1

这个问题可以使用递归和回溯来解决。保持到目前为止所涵盖的步骤数和迄今为止的路径成本。

这是我的实现 https://ideone.com/N6T55p 

void fun_me(int arr[4][4], int m, int n,int i,int j,int steps,int cost)
{

//cout<<steps<<endl;
if(i>=n || j>=n)
    return;
visited[i][j]=1;
if(i==n-1 && steps==m-1)
{
    if(maxer<arr[i][j]+cost)
        maxer=arr[i][j]+cost;
    //cout<<arr[i][j]+cost<<endl;
}

if(isvalid(i+1,j,n) && !visited[i+1][j])
    fun_me(arr,m,n,i+1,j,steps+1,cost+arr[i][j]);

if(isvalid(i,j+1,n) && !visited[i][j+1])
    fun_me(arr,m,n,i,j+1,steps+1,cost+arr[i][j]);

if(isvalid(i,j-1,n) && !visited[i][j-1])
    fun_me(arr,m,n,i,j-1,steps+1,cost+arr[i][j]);

visited[i][j]=0;
return ;
}
于 2015-06-21T19:29:15.250 回答