0

これが最大 L 合計に関する私の最初の質問です。

問題: mxnの 正の整数行列が与えられた場合、1 行目から m 行目までの L の合計の最小値を見つけます。L(4 項目) チェスの馬の動きが好き

例 : M = 3x3

0 1 2

1 3 2

4 2 1

可能な L の動きは次のとおりです: (0 1 2 2), (0 1 3 2) (0 1 4 2)

私はこれを動的プログラミングで解決しました。これが私のアルゴリズムです:

1. mxn の別の Minimum L Moves Sum 配列を取得し、メイン マトリックスの最初の行をコピーします。私はそれを (MLMS) と呼んでいます 2.最初のセルから開始し、L の動きを調べて計算し
ます 3.存在する値よりも小さい場合は MLMS に挿入します4.
ステップ2 を実行します. m 番目の行まで5.最小値を選択しますm行目の合計

私の例を段階的に説明しましょう：

  1. M[ 0 ][ 0 ] sum(L1 = (0, 1, 2, 2)) = 5 ; 合計 (L2 = (0,1,3,2)) = 6; したがって、MLMS[ 0 ][ 1 ] = 6
    sum(L3 = (0, 1, 3, 2)) = 6 ; 合計 (L4 = (0,1,4,2)) = 7; したがって、MLMS[ 2 ][ 1 ] = 6

  2. M[ 0 ][ 1 ] sum(L5 = (1, 0, 1, 4)) = 6; 合計 (L6 = (1,3,2,4)) = 10; したがって、MLMS[ 2 ][ 2 ] = 6

    ... 最後の MSLS は次のとおりです。
    0 1 2
    4 3 6
    6 6 6
    これは、6 が 0 から m まで到達できる最小 L 合計であることを意味します。

O(8*(m-1) n) = O(m n)だと思います。この問題に適合する最適なソリューションまたは動的計画法アルゴリズムはありますか?

ありがとう、長い質問でごめんなさい

4

1 に答える 1

1

合計行を含む行列にとの0-th両方の行がどのように存在する可能性がありますか？m-thm

とにかく、単純なダイクストラはで最適なパスを提供O(n*m)します（まだ到達していないポイントのリストで最小値を見つけるための優れたデータ構造があると仮定します）。

また、騎士がボードの下にしか移動できない場合（パスの総重量を減らすために時々上に移動すると便利な場合があります）、単純なDPを作成できます。ボードの下部から始めて、位置ごとに下部に到達するのにかかる時間を計算します。各位置から最大4回の移動が可能であるため、最小限の簡単なチェックです。このようなもの

for (int row = m - 1; row >= 0; --row) {
    for (int col = 0; col < m; ++col) {
        int path1 = a[row][col + 1] + a[row][col + 2] + a[row + 1][col + 2] + best[row + 1][col + 2];
        int path2 = a[row][col + 1] + a[row + 1][col + 1] + a[row + 2][col + 1] + best[row + 2][col + 1];
        int path3 = ...
        int path4 = ...
        best[row][col] = min(path1, path2, path3, path4);
    }
}

編集
なぜあなたは上がる必要があるのですか？このような行列を想像してみてください（*1000000000のような途方もなく大きな数を意味します）。明らかに、(0, 0)降りる前にボードの右側に移動する必要があります。

111111111111
111111111111
*********111
*********111

したがって、パスは次のようになります

...1...1...1
11...1...1..
*********11.
*********11.
于 2010-12-23T13:57:00.280 に答える