2

重み付けされた N*N グリッド W が与えられます。2 台のロボット r1、r2 がそれぞれ左上隅と右上隅から開始します。R1 は右下隅に到達し、R2 は左下隅に到達する必要があります。有効な動きは次のとおりです。

  • R1 は 1 マス下に移動し、R2 は 1 マス左に移動します。
  • R1 は 1 マス右に移動し、R2 は 1 マス下に移動します。

それらは、訪問する正方形 (開始および終了の正方形を含む) の重みの合計が最大になるように移動する必要があります。

たとえば、グリッドが次の場合:

6   0   3   1
7   4   2   4
3   3   2   8
13  10  1   4

この例では、以下に示すように、R1 が * でマークされたパスをたどり、R2 が ^ でマークされたパスをたどると、合計スコアは 56 になります。

 6*   0     3^   -1^
 7*   4*^   2^    4
-3    3*^  -2*    8*
 13^  10^  -1    -4*

これが、このグリッドで達成できる最高の総合スコアであることを確認できます。

N <= 2500 であり、制限時間は 2 秒であるため、再帰によってこれを解決することはできません。
問題にロボットが 1 つしかない場合は、動的計画法を使用してこれを解決できます。

この問題に対して同様のアプローチを使用してみました。

2 つの追加の N*N グリッド G1、G2、

for i from 1 to N:
   for j from 1 to N and K from N down to 1:  
     if (G1[i-1][j] + G2[i][k+1]) > (G1[i][j-1] + G2[i-1][k]):
        G1[i][j] = G1[i-1][j] + W[i][j]
        G2[i][k] = G2[i][k+1] + W[i][k]
     else:
        G1[i][j] = G1[i][j-1] + W[i][j]
        G2[i][k] = G2[i-1][k] + W[i][k]

return G1[N][N] + G2[N][1]

しかし、これは間違った答えになります。アルゴリズムの何が問題なのか理解できません。各正方形について、そこに到達するための最大加重パスを計算しているためです。

私の方法の何が問題なのか、正しい答えを得るためにどのように修正すればよいのか、誰か教えてもらえますか?

4

2 に答える 2

1

2番目の有効なシナリオでタイプミスが見られました

有効な2番目のシナリオは次のようになります

R1は1マス右に移動し、R2は1マス下に移動します

しかし、として与えられました

R2は1マス右に移動し、R2は1マス下に移動します

于 2012-12-28T07:20:01.170 に答える
1

これはグラフの問題であり、グラフは次のとおりですG=(V,E)。

  • V = Squares x Squares (すべての正方形 のデカルト積
    ) ((x1,y1)=(x2,y2) の点を除外したい場合がありますが、これは簡単に行うことができます)。
  • E = { ターン中に移動するすべての可能な方法 } = (または形式的に) =
    { (((x1,y1),(x2,y2)),((x1-1,y1),(x1,y1-1) )), (((x1,y1),(x2,y2)),((x1,y1-1),(x1-1,y1))) | x1、y1、x2、y2につき}

さて、グラフを取得すると、実際にはDAGであることがわかります。これは良いことです。なぜなら、一般的なケースのグラフでは、最長パスの問題はNP-Hardですが、DAG ではそうではないからです。

ここで、 DAG が与えられた場合、 からへGの最長パスを見つけたいと考えています。これは、次のアプローチで実行できます。((0,0),(n,n))((n,n),(0,0))

簡単にするために、次のように定義しますweight((x1,y1),(x2,y2)) = weight(x1,y1) + weight(x2,y2)。

アルゴリズム:

  1. グラフでトポロジカル ソートを使用する
  2. Init D((n,n),(0,0)) = weight((n,n),(0,0)) (対象ノード)
  3. 降順で並べ替えに従ってグラフを反復し、頂点ごとに次のようにしvます。
    D(v) = max { D(u) | 上記のように E の各 (v,u) に対して } + weight(v)

完了すると、 D((0,0),(n,n)) が最適な結果になります。

于 2012-12-28T07:26:00.690 に答える