1

positive左端の列から始まるすべての整数の行列が与えられた場合0th、右端の列への最小経路を見つけます(n - 1)th。例えば：
ここに画像の説明を入力してください

最短経路は、1を含む経路です。

任意の正方形m[i, j]で、4つの方向に移動できます（left, right, up, down）; もちろん、左端、右端の行/列のすべてのコーナーケースを除きます。たとえば、では[0, 0]、移動できるのはrightまたはdownです。私の解決策は、頂点
のグラフを作成してから、Floyd-Warshallを実行して、任意の2つの頂点のすべてのペアの最短経路を計算することです。次に、別のネストされたループを実行して、列のすべての頂点と列のすべての頂点をチェックし、最小パスを見つけます。 しかし、私の教授は、次の繰り返しを使用して別のアルゴリズムを提案しました。m x n(u, v)for0th(n - 1)th

S[i, j, L] = 
    min(
        S[i - 1, j, L - 1] + cost[i - 1, j],
        S[i + 1, j, L - 1] + cost[i + 1, j],
        S[i, j - 1, L - 1] + cost[i, j - 1],
        S[i, j + 1, L - 1] + cost[i, j + 1]);

それがどのように機能するのか私にはわかりません！どの正方形でも[i, j]4方向に移動できるため、事前に計算された値に基づいてテーブルを作成することはできません。
私はここで何かを逃しましたか？この再発がどのように機能するのかわかりません。何か案が？

4

1 に答える 1

4

S [0、j、L] = 0を除いて、S [i、j、0] =無限大の場合、それは機能するはずです。最終的にはすべてのS[i、j、L] == S [i、j、L + 1]となり、反復を停止できます。S [i、j、L]は、最初の列からそのセルまでの最短経路のコストがかかります。

これは、Lの値を増やすために、この再発が左上隅でどのように見えるかを示しています。

0   inf inf inf inf
0   inf inf inf inf
0   inf inf inf inf

0   1   inf inf inf inf
0   20  inf inf inf inf
0   21  inf inf inf inf

0   1   2   inf inf inf
0   2   30  inf inf inf
0   21  22  inf inf inf

0   1   2   3   inf inf
0   2   3   39  inf inf
0   12  22  23  inf inf

0   1   2   3   4   inf
0   2   3   4   47  inf
0   12  12  23  24  inf

0   1   2   3   4   5  
0   2   3   4   5   48  
0   12  12  12  24  25 

0   1   2   3   4   5  
0   2   3   4   5   6   
0   12  12  12  6   25 

0   1   2   3   4   5
0   2   3   4   5   6
0   12  12  7   6   7

0   1   2   3   4   5
0   2   3   4   5   6
0   12  8   7   6   7

0   1   2   3   4   5
0   2   3   4   5   6
0   9   8   7   6   7

左上隅ではこれ以上の変更は行われません。各セルに到達するための最小コストをゆっくりと発見していることがわかります。

于 2013-03-24T07:13:42.237 に答える