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？

編集

可能な方向は下/右/左ですが、各要素にアクセスできるのは最大で1回だけです。

編集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/ソリューション

WanderleyGuimarães、http：//ideone.com/0iLS2に感謝し
ます

4

4 に答える 4

2

この問題は動的計画法で解決できます。行列の位置（i行目、j行目）value(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、2行目以降に進むことはできません。そして、あなたは答えますf(2, 2) = 4。

その場合m = 4、3行目以降は行けません。そして、あなたは答えます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

この問題はよく知られています。これを行う最も効率的な方法は、動的計画法です。

dp[i][j]0,0からi、jに到達するときの最大合計をLetとします。
次に、dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];

これを行った後、あなたが行くことができる位置のすべての値をチェックして、最大値を取得します。

于 2012-10-05T10:37:21.280 に答える
1

これは実際にはDAGであるため、最長パスの問題に対する動的計画法のソリューションが機能します。

なぜDAGだと思いますか？水平方向に隣接する2つの頂点からの明らかなサイクルがあります。もちろん、「明らかな」グラフを使用する場合。

あまり目立たないアプローチは、これを（頂点、方向）のグラフとして作り直すことです。この方向は、下/左/右から最後に取った方向です。下方向の頂点は下、左、右のいずれかになりますが、右方向の頂点は下/右にしか行けず、左方向の頂点は左/下にしか行けません。このグラフは明らかに非周期的であり、元のマトリックスで可能なすべてのパスで構成されています。

したがって、制限を無視するmと、（a、b、方向）への最長パスの再帰の可能性は次のようになります。

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 に答える