algorithm - 爆弾投下アルゴリズム

Question

n x m非負の整数で構成される行列があります。例えば：

「爆弾を落とす」は、ターゲットセルとその隣接セルの8つすべての数を1つ減らし、最小でゼロにします。

x x x 
x X x
x x x

すべてのセルをゼロにするために必要な爆弾の最小数を決定するアルゴリズムは何ですか？

Bオプション（私が注意深い読者ではないため）

実際、問題の最初のバージョンは、私が答えを求めているものではありません。私はタスク全体を注意深く読んでいませんでした、追加の制約があります、私たちに言わせてください：

行のシーケンスが増加しない必要がある場合の単純な問題についてはどうでしょうか。

8 7 6 6 5可能な入力シーケンスです

7 8 5 5 27-> 8が連続して成長するため、不可能です。

たぶん、「より簡単な」ケースの答えを見つけることは、より難しいケースの解決策を見つけるのに役立つでしょう。

PS：同じ状況がいくつかある場合、上の行をクリアするために最小限の爆弾が必要な場合は、列の「左側」でほとんどの爆弾を使用するものを選択すると思います。それでも正しいかもしれない証拠はありますか？

score 38 · Accepted Answer

これを単純なサブ問題に減らす方法があります。

説明には、アルゴリズムと、アルゴリズムが最適なソリューションを提供する理由の 2 つの部分があります。1 つ目は 2 つ目がなければ意味をなさないので、まずはその理由から説明します。

四角形を爆撃することを考えると (大きな四角形を想定します - エッジケースはまだありません)、周囲の正方形の中空の四角形を 0 に減らす唯一の方法は、周囲を爆撃するか、中空の四角形を爆撃することです。周囲のすぐ内側の正方形。境界をレイヤー 1、その内側の長方形をレイヤー 2 と呼びます。

重要な洞察は、レイヤー 1 を爆撃するポイントがないということです。そうすることで得られる「爆発半径」は、常にレイヤー 2 からの別の正方形の爆発半径内に含まれているためです。これは簡単に納得できるはずです。

したがって、この問題を、周囲を爆撃する最適な方法を見つけることに減らし、すべての正方形が 0 になるまでそれを繰り返すことができます。

もちろん、最適とは言えない方法で周囲を爆撃することが可能である場合、常に最適な解決策が見つかるとは限りませんが、X 個の余分な爆弾を使用することで、X 個以上の爆弾によって内層を削減する問題がより簡単になります。では、パーミッターをレイヤー 1 と呼ぶ場合、追加の X 爆弾をレイヤー 2 のどこかに (レイヤー 1 のすぐ内側に) 配置すると、後でレイヤー 2 を爆撃する労力を X よりも多く減らすことができるでしょうか? 言い換えれば、貪欲に外周を縮小できることを証明しなければなりません。

しかし、私たちは貪欲になることができることを知っています。レイヤー2の爆弾は、レイヤー3に戦略的に配置された爆弾よりもレイヤー2を0に減らすのに効率的ではないからです。そして以前と同じ理由で、すべての正方形に影響を与えるレイヤー3に配置できる爆弾が常に存在します。レイヤー2に配置された爆弾ができるレイヤー2の。したがって、貪欲であることは私たちに害を及ぼすことは決してありません（この意味での貪欲です）。

したがって、私たちがしなければならないことは、次の内層を爆撃することによってパーミッターを 0 に減らす最適な方法を見つけることだけです。

最初にコーナーを 0 に爆撃してもダメージを受けることはありません。内側のレイヤーのコーナーだけがコーナーに到達できるためです。内層の角から爆風半径)。

これが完了すると、0 コーナーに隣接する周囲の正方形は、内側の層から 2 正方形だけ到達できます。

0       A       B

C       X       Y

D       Z

この時点で、爆弾は隣接する 3 つの正方形を縮小するため、周囲は実質的に 1 次元の閉じたループになります。コーナー付近のいくつかの奇妙な点を除いて - X は A、B、C、および D を「ヒット」できます。

これで、爆破範囲のトリックを使用できなくなりました。奇妙な角を除いて、各正方形の状況は対称的であり、爆破範囲がない場合でも別のサブセットです。これが閉じたループではなく線 (Colonel Panic が議論しているように) である場合、解決策は自明であることに注意してください。終点は 0 に減らす必要があり、爆破半径はスーパーセットであるため、終点に隣接するポイントを爆撃しても害はありません。エンドポイントを 0 にすると、まだ新しいエンドポイントがあるので、(行がすべて 0 になるまで) 繰り返します。

したがって、レイヤー内の 1 つの正方形を最適に 0 に減らすことができれば、アルゴリズムがあります (ループを切断し、端点のある直線が得られるため)。最小値の正方形に隣接する爆撃 (2 つのオプションを与える) が最適であり、その最小値の 2 つの正方形内の最大値が可能な限り最小になると思います (これを管理するには、爆撃を分割する必要がある場合があります)。（まだ？）証拠を持っていません。

score 26 · Accepted Answer

Pólya は、「問題を解決できない場合は、もっと簡単に解決できる問題があります。それを見つけてください」と言っています。

明らかに単純な問題は、1 次元の問題 (グリッドが 1 行の場合) です。最も単純なアルゴリズムから始めましょう - 最大のターゲットを貪欲に爆撃します。これはいつうまくいかないのですか？

が与えられ1 1 1た場合、貪欲なアルゴリズムは、最初に爆撃するセルに関係ありません。もちろん、中央のセルの方が優れています。3 つのセルすべてを一度にゼロにします。これは、新しいアルゴリズム A、「残りの合計を最小化するための爆弾」を示唆しています。このアルゴリズムはいつ失敗しますか?

が与えられた場合1 1 2 1 1、アルゴリズム A は 2 番目、3 番目、または 4 番目のセルを爆撃することに関係ありません。ただし、2 番目のセルを爆撃して離脱する0 0 1 1 1方が、3 番目のセルを爆撃して離脱するよりも優れてい1 0 1 0 1ます。それを修正する方法は？3 番目のセルを爆撃する際の問題は、左側の作業と右側の作業を別々に行う必要があることです。

「残りの合計を最小化する爆弾ですが、（爆撃した場所の）左側の最小値と右側の最小値を最大化します」はどうですか。このアルゴリズムを B と呼びます。このアルゴリズムがうまくいかないのはいつですか?

編集: コメントを読んだ後、はるかに興味深い問題は、端が結合するように変更された 1 次元の問題であることに同意します。それについての進展を楽しみにしています。

score 12 · Accepted Answer

時間がなかったので、部分的な解決策だけにとどまらなければなりませんでしたが、うまくいけば、この部分的な解決策でも、この問題を解決するための 1 つの潜在的なアプローチについての洞察が得られることを願っています。

難しい問題に直面したとき、私はより簡単な問題を考え出し、問題空間についての直感を養うのが好きです. ここで、私が取った最初のステップは、この 2 次元の問題を 1 次元の問題に還元することでした。次の行を考えてみましょう。

0 4 2 1 3 0 1

4どういうわけか、スポットを 0 にするために、スポットまたはその周辺で 4 回0爆撃4する必要があることはわかっています2。2実際、スポットが 0 になるまで爆撃することは、スポットを04にする他の戦略と少なくとも同じくらい有効であると私は信じています (ただし、厳密な証拠はありません) 。4このような：

index = 1
while index < line_length
  while number_at_index(index - 1) > 0
    bomb(index)
  end
  index++
end
# take care of the end of the line
while number_at_index(index - 1) > 0
  bomb(index - 1)
end

爆撃命令の例:

0 4[2]1 3 0 1
0 3[1]0 3 0 1
0 2[0]0 3 0 1
0 1[0]0 3 0 1
0 0 0 0 3[0]1
0 0 0 0 2[0]0
0 0 0 0 1[0]0
0 0 0 0 0 0 0

4[2]1 3 2 1 5
3[1]0 3 2 1 5
2[0]0 3 2 1 5
1[0]0 3 2 1 5
0 0 0 3[2]1 5
0 0 0 2[1]0 5
0 0 0 1[0]0 5
0 0 0 0 0 0[5]
0 0 0 0 0 0[4]
0 0 0 0 0 0[3]
0 0 0 0 0 0[2]
0 0 0 0 0 0[1]
0 0 0 0 0 0 0

何らかの方法で下げる必要のある数値から始めるというアイデアは魅力的なものです。なぜなら、少なくとも他のすべてのソリューションと同じくらい優れていると主張するソリューションを見つけることが突然達成可能になるからです。

複雑さの次のステップアップは、この検索が少なくとも同じくらい実行可能であり、ボードの端にあります。外側のエッジを爆撃することには、厳密なメリットがないことは明らかです。スポットを 1 つ爆撃して、他の 3 つのスペースを無料で取得する方がよいでしょう。これを考えると、エッジの内側のリングを爆撃することは、少なくともエッジを爆撃するのと同じくらい良いと言えます。さらに、これを直観と組み合わせることができます。これは、エッジの内側の右側を爆撃することが実際にはエッジスペースを 0 にする唯一の方法であるということです。コーナーの数を 0 にするために、少なくとも他の戦略と同じくらい良い)。これをすべてまとめると、2 次元空間での解にはるかに近づくことができます。

コーナーピースについての観察を考えると、任意のスターティングボードからすべてのコーナーがゼロのボードに移行するための最適な戦略を知っていると確信できます。これはそのようなボードの例です (数字は上の 2 つのリニアボードから借りました)。一部のスペースに別のラベルを付けました。その理由を説明します。

0 4 2 1 3 0 1 0
4 x x x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

一番上の行は、前に見た線形の例に非常によく似ていることに気付くでしょう。一番上の行をすべて 0 にする最適な方法は、2 番目の行 (行) を爆撃することであるという以前の観察を思い出してくださいx。列のいずれかを爆撃して一番上の列をクリアする方法はなく、y列の対応するスペースを爆撃するよりも一番上の列を爆撃しても追加の利点はありませんx。

上からの線形戦略 (行の対応するスペースを爆撃する)を適用することができます。次のようになります。x

0 4 2 1 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 3 1 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 2 0 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 1 0 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 0 0 0 3 0 1 0
4 x x x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

このアプローチの欠陥は、最後の 2 つの爆撃で非常に明白になります。4第 2 行の第 1 列の数字を減らす唯一の爆弾サイトが第 1xとy. 最後の 2 つの爆撃は、最初xのを爆撃した場合よりも明らかに劣っています。最初の . 現在の戦略が最適ではないことを実証したため、戦略の修正が明らかに必要です。

この時点で、複雑さから一歩下がって、1 つのコーナーだけに焦点を当てることができます。これを考えてみましょう：

0 4 2 1
4 x y a
2 z . .
1 b . .

スペースをゼロにする唯一の方法は、、、および4の組み合わせを爆撃することであることは明らかです。いくつかのアクロバットを考えてみると、最適な解決策は3 回爆撃してから. どうやってその解決策にたどり着いたかを理解することが今の問題であり、このローカルな問題を解決するために使用できる直感が明らかになれば. とスペースの爆撃がないことに気付きました。それらのスペースを爆撃するのが理にかなっているコーナーを見つけようとすると、次のようなコーナーが得られます。xyzxabyz

0 4 2 5 0
4 x y a .
2 z . . .
5 b . . .
0 . . . .

yこれについては、最適な解決策は5回と5回爆撃することであることは明らかですz。さらに一歩進みましょう。

0 4 2 5 6 0 0
4 x y a . . .
2 z . . . . .
5 b . . . . .
6 . . . . . .
0 . . . . . .
0 . . . . . .

aここで、最適な解決策は爆撃とb6 回、次にx4 回であることが同様に直感的に感じられます。

今では、それらの直感を、私たちが構築できる原則に変える方法のゲームになります.

うまくいけば続きます！

score 11 · Accepted Answer

更新された質問の場合、単純な貪欲なアルゴリズムが最適な結果をもたらします。

A[0,0] 爆弾をセル A[1,1] に投下し、次に A[1,0] 爆弾をセル A[2,1] に投下し、このプロセスを下方向に続けます。左下隅をきれいにするには、セル A[N-2,1] に max(A[N-1,0], A[N-2,0], A[N-3,0]) 個の爆弾をドロップします。これにより、最初の 3 列が完全にクリーンアップされます。

同じアプローチで、列 3、4、5、次に列 6、7、8 などをクリーンアップします。

残念ながら、これは元の問題の解決策を見つけるのには役立ちません。

「より大きな」問題（「非増加」制約なし）は、NP困難であることが証明される場合があります。ここに証明のスケッチがあります。

次数が 3 までの平面グラフがあるとします。このグラフの最小頂点カバーを見つけてみましょう。ウィキペディアの記事によると、この問題は次数が 3 までの平面グラフでは NP 困難です。これは、Planar 3SAT からの削減によって証明できます。そしてPlanar 3SATの硬度 - 3SATからの減少による。これらの証明はどちらも、教授による「アルゴリズムの下限」の最近の講義で提示されています。Erik Demaine (講義 7 および 9)。

元のグラフ (図の左のグラフ) のいくつかのエッジを分割し、それぞれに偶数の追加ノードがある場合、結果のグラフ (図の右のグラフ) は、元の頂点に対してまったく同じ最小頂点カバーを持つ必要があります。このような変換により、グラフの頂点をグリッド上の任意の位置に揃えることができます。

ここに画像の説明を入力

グラフの頂点を偶数の行と列にのみ配置すると (1 つの頂点に接する 2 つのエッジが鋭角を形成しないように)、エッジがある場所には「1」を挿入し、他のグリッド位置には「0」を挿入します。元の問題の任意のソリューションを使用して、最小の頂点カバーを見つけることができます。

score 9 · Accepted Answer

これは貪欲なアプローチになります。

次数 n X m の「スコア」マトリックスを計算します。ここで、スコア[i][j] は、位置 (i,j) が爆撃された場合のマトリックス内の総減点です。(ポイントの最大スコアは 9、最小スコアは 0)
行ごとに移動し、最高スコアの最初の位置を見つけて選択します ((i,j) とします)。
爆弾 (i,j)。爆弾の数を増やします。
元の行列のすべての要素がゼロでない場合は、1 に進みます。

ただし、これが最適なソリューションであることに疑問があります。

編集：

上記の貪欲なアプローチは機能しますが、おそらく最適なソリューションにはなりません。そこで、DP の要素をいくつか追加する必要があると考えました。

いつでも、最高の「スコア」 (score[i][j] = (i,j) が爆撃された場合の減点の合計) を持つ位置の 1 つをターゲットにする必要があることに同意できると思います。この仮定から始めて、新しいアプローチを次に示します。

NumOfBombs(M): (必要な爆撃の最小回数を返します)

次数 n X m の行列 M が与えられます。M のすべての要素がゼロの場合、0 を返します。
「スコア」行列 M を計算します。

k 個の個別の位置 P1、P2、...Pk (1 <= k <= n*m) を、M 内の最高スコアの位置とする。
return (1 + min( NumOfBombs(M1), NumOfBombs(M2), ..., NumOfBombs(Mk) ) )

ここで、M1、M2、...、Mk は、それぞれ位置 P1、P2、...、Pk を爆撃した場合の結果の行列です。

また、これに加えて位置の順序を nuke したい場合は、「min」の結果を追跡する必要があります。

score 9 · Accepted Answer

この問題は、整数計画問題として表すことができます。(これは、この問題に対処するための可能な解決策の 1 つにすぎません)

ポイントを持っている：

a b c d
e f g h
i j k l
m n o p

たとえば、点 f が成り立つ 16 の方程式を書くことができます。

f <= ai + bi + ci + ei + fi + gi + ii + ji + ki

すべてのインデックスと整数解の合計で最小化されます。

解決策はもちろん、このインデックスの合計です。

これは、すべての xi を境界 0 に設定することでさらに単純化できるため、この例では 4+1 の方程式が得られます。

問題は、そのような問題を解決するための自明なアルゴリズムがないことです。私はこれについて専門家ではありませんが、線形計画法は NP が難しいため、この問題を解決することは困難です。

score 9 · Accepted Answer

これは部分的な答えです。爆弾の可能な数の下限と上限を見つけようとしています。

3x3 以下のボードでは、解決策は常に最も大きな番号のセルです。

4x4 より大きいボードでは、最初の明らかな下限はコーナーの合計です。

*2* 3  7 *1*
 1  5  6  2
 2  1  3  2
*6* 9  6 *4*

どんなにボムを配置しても、2+1+6+4=13 個未満のボムではこの 4x4 ボードをクリアすることはできません。

他の回答では、コーナーをなくすために爆弾を 2 番目のコーナーに配置することは、コーナー自体に爆弾を配置するよりも決して悪いことではないことが言及されているため、ボードを考えると、次のようになります。

*2* 3  4  7 *1*
 1  5  2  6  2
 4  3  4  2  1
 2  1  2  4  1
 3  1  3  4  1
 2  1  4  3  2
*6* 9  1  6 *4*

コーナーから 2 番目のコーナーに爆弾を配置して新しいボードを作成することで、コーナーをゼロにすることができます。

 0  1  1  6  0
 0  3  0  5  1
 2  1  1  1  0
 2  1  2  4  1
 0  0  0  0  0
 0  0  0  0  0
 0  3  0  2  0

ここまでは順調ですね。コーナーをクリアするには 13 個の爆弾が必要です。

次に、下にマークされた 6、4、3、および 2 の番号を確認します。

 0  1  1 *6* 0
 0  3  0  5  1
 2  1  1  1  0
*2* 1  2 *4* 1
 0  0  0  0  0
 0  0  0  0  0
 0 *3* 0  2  0

1 つの爆弾を使用してこれらのセルのいずれか 2 つを爆撃する方法はないため、最小爆弾は 6+4+3+2 増加しました。したがって、コーナーをクリアするために使用した爆弾の数に追加すると、最小このマップに必要な爆弾の数は 28 爆弾になりました。28 個未満の爆弾でこのマップをクリアすることは不可能です。これがこのマップの下限です。

欲張りアルゴリズムを使用して上限を設定できます。他の回答では、貪欲なアルゴリズムが 28 個の爆弾を使用するソリューションを生成することが示されています。爆弾の数が 28 個未満の最適解は存在しないことを以前に証明したので、28 個の爆弾が実際に最適解です。

貪欲で、上で述べた最小境界を見つける方法が収束しない場合は、すべての組み合わせを確認する必要があると思います。

下限を見つけるためのアルゴリズムは次のとおりです。

番号が最も大きい要素を選び、P と名付けます。
P から 2 ステップ離れたすべてのセルと P 自体を選択不可としてマークします。
minimumsP を下のリストに加える。
すべてのセルが選択不能になるまで、手順 1 を繰り返します。
リストを合計しminimumsて下限を取得します。

score 8 · Accepted Answer

行全体で値が減少しないという新しい問題は、非常に簡単に解決できます。

左の列に最大の数値が含まれていることに注意してください。したがって、最適なソリューションでは、最初にこの列をゼロに減らす必要があります。したがって、この列に対して1 次元爆撃を実行して、その中のすべての要素をゼロに減らすことができます。爆弾は 2 列目に落下させ、最大のダメージを与えます。ここには 1D のケースを扱う記事がたくさんあると思うので、そのケースを飛ばしても安全だと思います。（説明してほしいなら、できます。）プロパティが減少するため、左端の 3 つの列はすべてゼロに減少します。ただし、左の列をゼロにする必要があるため、ここでは最小数の爆弾を使用します。

ここで、左の列がゼロになったら、現在ゼロになっている左端の 3 つの列を削除し、縮小された行列で繰り返します。各段階で使用する爆弾の数が最小限であるため、これにより最適な解決策が得られるはずです。

score 4 · Accepted Answer

分枝限定法を使用した Mathematica 整数線形計画法

すでに述べたように、この問題は整数線形計画法 ( NP-Hard ) を使用して解決できます。Mathematica にはすでに ILP が組み込まれています。"To solve an integer linear programming problem Mathematica first solves the equational constraints, reducing the problem to one containing inequality constraints only. Then it uses lattice reduction techniques to put the inequality system in a simpler form. Finally, it solves the simplified optimization problem using a branch-and-bound method."[ Mathematica の制約付き最適化のチュートリアルを参照してください。]

Mathematica の ILP ライブラリを利用する次のコードを書きました。驚くほど速いです。

solveMatrixBombProblem[problem_, r_, c_] := 
 Module[{}, 
  bombEffect[x_, y_, m_, n_] := 
   Table[If[(i == x || i == x - 1 || i == x + 1) && (j == y || 
        j == y - 1 || j == y + 1), 1, 0], {i, 1, m}, {j, 1, n}];
  bombMatrix[m_, n_] := 
   Transpose[
    Table[Table[
      Part[bombEffect[(i - Mod[i, n])/n + 1, Mod[i, n] + 1, m, 
        n], (j - Mod[j, n])/n + 1, Mod[j, n] + 1], {j, 0, 
       m*n - 1}], {i, 0, m*n - 1}]];
  X := x /@ Range[c*r];
  sol = Minimize[{Total[X], 
     And @@ Thread[bombMatrix[r, c].X >= problem] && 
      And @@ Thread[X >= 0] && Total[X] <= 10^100 && 
      Element[X, Integers]}, X];
  Print["Minimum required bombs = ", sol[[1]]];
  Print["A possible solution = ", 
   MatrixForm[
    Table[x[c*i + j + 1] /. sol[[2]], {i, 0, r - 1}, {j, 0, 
      c - 1}]]];]

問題で提供されている例:

solveMatrixBombProblem[{2, 3, 4, 7, 1, 1, 5, 2, 6, 2, 4, 3, 4, 2, 1, 2, 1, 2, 4, 1, 3, 1, 3, 4, 1, 2, 1, 4, 3, 2, 6, 9, 1, 6, 4}, 7, 5]

出力

ここに画像の説明を入力

貪欲なアルゴリズムでこれを読んでいる人のために

次の 10x10 問題でコードを試してください。

5   20  7   1   9   8   19  16  11  3  
17  8   15  17  12  4   5   16  8   18  
4   19  12  11  9   7   4   15  14  6  
17  20  4   9   19  8   17  2   10  8  
3   9   10  13  8   9   12  12  6   18  
16  16  2   10  7   12  17  11  4   15  
11  1   15  1   5   11  3   12  8   3  
7   11  16  19  17  11  20  2   5   19  
5   18  2   17  7   14  19  11  1   6  
13  20  8   4   15  10  19  5   11  12

ここではカンマ区切りです。

5, 20, 7, 1, 9, 8, 19, 16, 11, 3, 17, 8, 15, 17, 12, 4, 5, 16, 8, 18, 4, 19, 12, 11, 9, 7, 4, 15, 14, 6, 17, 20, 4, 9, 19, 8, 17, 2, 10, 8, 3, 9, 10, 13, 8, 9, 12, 12, 6, 18, 16, 16, 2, 10, 7, 12, 17, 11, 4, 15, 11, 1, 15, 1, 5, 11, 3, 12, 8, 3, 7, 11, 16, 19, 17, 11, 20, 2, 5, 19, 5, 18, 2, 17, 7, 14, 19, 11, 1, 6, 13, 20, 8, 4, 15, 10, 19, 5, 11, 12

この問題では、私のソリューションには208個の爆弾が含まれています。考えられる解決策は次のとおりです (約 12 秒で解決できました)。

ここに画像の説明を入力

Mathematica が生成している結果をテストする方法として、貪欲なアルゴリズムがより良い結果を出せるかどうかを確認してください。

score 3 · Accepted Answer

この貪欲な解決策~~は正しいようです~~：

コメントで指摘されているように、2Dでは失敗します。しかし、多分あなたはそれを改善するかもしれません。

1Dの場合： 2つ以上の数字がある場合は、2番目の数字までの撮影は悪くない
ので、左端の数字まで撮影する必要はありません。だから、あなたがそれをしなければならないので、最初が0ではない間、2番目に撃ちます。次のセルに移動します。最後のセルを忘れないでください。

C ++コード：

void bombs(vector<int>& v, int i, int n){
    ans += n;
    v[i] -= n;
    if(i > 0)
        v[i - 1] -= n;
    if(i + 1< v.size())
        v[i + 1] -= n;
}

void solve(vector<int> v){
    int n = v.size();
    for(int i = 0; i < n;++i){
        if(i != n - 1){
            bombs(v, i + 1, v[i]);
        }
        else
            bombs(v, i, v[i])
    }
}

したがって、2Dの場合：
繰り返しますが、最初の行で撮影する必要はありません（2番目の行がある場合）。だから2番目のものに撃ちます。最初の行の1Dタスクを解きます。（nullにする必要があるため）。降りる。最後の行を忘れないでください。

score 3 · Accepted Answer

問題を線形部分問題に変換する必要はありません。

代わりに、単純な貪欲なヒューリスティックを使用します。これは、最大のものから始めて、コーナーを爆撃することです。

この例では、{ 2, 1, 6, 4 } の 4 つのコーナーがあります。各コーナーでは、コーナーに対して斜めのセルを爆撃するよりも良い動きはありません。したがって、最初の 2+1+6+4 = 13 回の爆撃は、これらの斜めのセルにある必要があることがわかっています。爆撃を行った後、新しいマトリックスが残ります。

2 3 4 7 1      0 1 1 6 0      0 1 1 6 0     1 1 6 0     0 0 5     0 0 0 
1 5 2 6 2      0 3 0 5 1      0 3 0 5 1  => 1 0 4 0  => 0 0 3  => 0 0 0  
4 3 4 2 1      2 1 1 1 0      2 1 1 1 0     0 0 0 0     0 0 0     0 0 3  
2 1 2 4 1  =>  2 1 2 4 1  =>  2 1 2 4 1     0 0 3 0     0 0 3      
3 1 3 4 1      0 0 0 0 0      0 0 0 0 0 
2 1 4 3 2      0 0 0 0 0      0 0 0 0 0 
6 9 1 6 4      0 3 0 2 0      0 0 0 0 0

最初の 13 回の爆撃の後、ヒューリスティックを使用して 3 0 2 を 3 回の爆撃で排除します。これで、4 行目に 2 つの新しいコーナー { 2, 1 } ができました。それらを爆撃し、さらに3回爆撃します。行列を 4 x 4 に縮小しました。左上に角があります。私たちはそれを爆撃します。これで 2 つのコーナー { 5, 3 } が残りました。5 が最大のコーナーなので、最初に 5 を爆撃し、最後にもう一方のコーナーの 3 を爆撃します。合計は 13+3+3+1+5+3 = 28 です。

score 3 · Accepted Answer

これは、この「迷路」の位置を通る最短経路 (一連の爆撃) を広範囲に検索します。いいえ、より高速なアルゴリズムが存在しないことを証明することはできません。申し訳ありません。

#!/usr/bin/env python

M = ((1,2,3,4),
     (2,3,4,5),
     (5,2,7,4),
     (2,3,5,8))

def eachPossibleMove(m):
  for y in range(1, len(m)-1):
    for x in range(1, len(m[0])-1):
      if (0 == m[y-1][x-1] == m[y-1][x] == m[y-1][x+1] ==
               m[y][x-1]   == m[y][x]   == m[y][x+1] ==
               m[y+1][x-1] == m[y+1][x] == m[y+1][x+1]):
        continue
      yield x, y

def bomb(m, (mx, my)):
  return tuple(tuple(max(0, m[y][x]-1)
      if mx-1 <= x <= mx+1 and my-1 <= y <= my+1
      else m[y][x]
      for x in range(len(m[y])))
    for y in range(len(m)))

def findFirstSolution(m, path=[]):
#  print path
#  print m
  if sum(map(sum, m)) == 0:  # empty?
    return path
  for move in eachPossibleMove(m):
    return findFirstSolution(bomb(m, move), path + [ move ])

def findShortestSolution(m):
  black = {}
  nextWhite = { m: [] }
  while nextWhite:
    white = nextWhite
    nextWhite = {}
    for position, path in white.iteritems():
      for move in eachPossibleMove(position):
        nextPosition = bomb(position, move)
        nextPath = path + [ move ]
        if sum(map(sum, nextPosition)) == 0:  # empty?
          return nextPath
        if nextPosition in black or nextPosition in white:
          continue  # ignore, found that one before
        nextWhite[nextPosition] = nextPath

def main(argv):
  if argv[1] == 'first':
    print findFirstSolution(M)
  elif argv[1] == 'shortest':
    print findShortestSolution(M)
  else:
    raise NotImplementedError(argv[1])

if __name__ == '__main__':
  import sys
  sys.exit(main(sys.argv))

score 3 · Accepted Answer

ここでは、線形計画法のアプローチが非常に役立つようです。

P _{m xn}を位置の値を持つ行列とします。

位置のマトリックス

ここで、以下のように1 ≤ x ≤ m , 1 ≤ y ≤ nの爆弾行列 B(x, y) _mxnを定義します。

爆弾マトリックス

そのような方法で

爆弾行列の位置の値

例えば：

B(3,3)

したがって、次の行列B _{m xn} = [ b _ij ] を探しています。

爆弾行列の合計として定義できます。

( q _ijは、位置p _ijに投下する爆弾の数になります)
p _ij - b _ij ≤ 0 (より簡潔にするために、 P - B ≤ 0 としましょう)

また、Bは sum を最小化する必要があり爆弾の総量ます。

Bを先の醜い行列として書くこともできます。

量の合計の行列としての B

また、P - B ≤ 0 (つまりP ≤ B ) であるため、次のかなり線形の不等式システムが得られます。

投下された爆弾の数と位置の値の関係

q mn _{x 1}として定義される

量のベクトル

p _{mn x 1}として定義

ベクトルとして分布する P の値

S _{mn x mn}である系があると言えます。行列を逆にして、系を解く必要があります。私は自分で拡張しませんでしたが、コードで簡単に実行できるはずです。

ここで、次のように述べることができる最小の問題があります。

私たちが解決しなければならないシステム

シンプレックスアルゴリズムのようなもので解決するのは簡単で、ほとんど些細なことだと思います（これについてはかなりクールなドキュメントがあります）。しかし、私は線形プログラミングをほとんど知りません (Coursera でコースを受講しますが、それはまだ先のことです...)。それを理解しようとして頭が痛くなり、フリーランスの大きな仕事を終わらせなければならないので、私はここであきらめてください。ある時点で何か間違ったことをしたか、それ以上進むことができないかもしれませんが、この道が最終的に解決につながると信じています. とにかく、私はあなたのフィードバックを切望しています。

( LaTeX 式から画像を作成するこの素晴らしいサイトに感謝します)

score 2 · Accepted Answer

爆弾の数を最小限に抑えるには、すべての爆弾の効果を最大化する必要があります。これを達成するには、すべてのステップで最適なターゲットを選択する必要があります。それとそれの8つの隣人を合計する各ポイントについて-このポイントを爆撃する効率的な量として使用することができます。これにより、爆弾の最適なシーケンスに近くなります。

UPD：ゼロの数も考慮に入れる必要があります。なぜなら、それらをボンビンするのは非効率的だからです。実際、問題はヒットしたゼロの数を最小限に抑えることです。しかし、どのようなステップでもこの目標にどのように近づくことができるかはわかりません。問題はNP完全であるという考えに同意します。私は貪欲なアプローチを提案します。それは現実に近い答えを与えるでしょう。

score 2 · Accepted Answer

ここに別のアイデアがあります：

ボード上の各スペースに、そこに爆弾を落とすことによってどれだけの数字が減るかの重みを割り当てることから始めましょう。したがって、スペースにゼロ以外の数字がある場合はポイントを取得し、それに隣接するスペースにゼロ以外の数字がある場合は追加のポイントを取得します。したがって、1000 x 1000 のグリッドがある場合、100 万個のスペースのそれぞれに重みが割り当てられます。

次に、スペースのリストを重みで並べ替え、重みが最も高いものを爆撃します。いわば、これは私たちの費用対効果が最も高いものです。

その後、重量が爆弾の影響を受けるすべてのスペースの重量を更新します。これは、爆撃したスペースと、それに隣接するスペース、およびそれらに隣接するスペースになります。言い換えれば、爆撃によってその値がゼロに減少した可能性のあるスペース、または隣接するスペースの値がゼロに減少した可能性のあるスペース。

次に、リストスペースを重みで並べ替えます。爆撃によってウェイトが変更されたのはスペースのごく一部だけなので、リスト全体を並べ替える必要はなく、リスト内でそれらのスペースを移動するだけです。

新しい最大重量スペースを爆撃し、手順を繰り返します。

これにより、すべての爆撃が可能な限り多くのスペースを削減することが保証されます (基本的に、すでにゼロになっているスペースをできるだけ少なくします)。そのため、トップウェイトが同点の場合は、バックトラッキングを行う必要がある場合があります。ただし、トップウェイトの同点のみが重要であり、他の同点は重要ではないため、後戻りしすぎないことを願っています.

編集： 以下のMysticialの反例は、重みの関係に関係なく、実際にはこれが最適であることが保証されていないことを示しています. 場合によっては、特定のステップで可能な限り重量を減らすと、実際には残りの爆弾が分散しすぎて、最初のステップでわずかに貪欲でない選択をした場合と同じように、2 番目のステップの後に累積的な削減を達成できなくなります。結果が爆撃の順序に左右されないという考えに、私はいくぶん誤解されました。彼らは一連の爆撃を取り、最初から別の順序で再生し、同じ結果のボードで終わる可能性があるという点で、順序に敏感ではありません。しかし、だからと言って、それぞれの爆撃を独立して考えることができるということにはなりません。または、少なくとも、各爆撃は、後続の爆撃のためにボードをどのようにセットアップするかを考慮に入れた方法で検討する必要があります.

score 2 · Accepted Answer

爆弾の量を最小限に抑えるには、ダメージの量を最大化する必要があるだけだと思います..そのためには、最も強い力を持つ領域を確認する必要があります..最初に3x3カーネルでフィールドを分析し、合計がどこにあるかを確認します.より強い..そしてそこに爆撃..フィールドが平らになるまで..このフィールドの答えは28です

var oMatrix = [
[2,3,4,7,1],
[1,5,2,6,2],
[4,3,4,2,1],
[2,1,2,4,1],
[3,1,3,4,1],
[2,1,4,3,2],
[6,9,1,6,4]
]

var nBombs = 0;
do
{
    var bSpacesLeftToBomb = false;
    var nHigh = 0;
    var nCellX = 0;
    var nCellY = 0;
    for(var y = 1 ; y<oMatrix.length-1;y++) 
        for(var x = 1 ; x<oMatrix[y].length-1;x++)  
        {
            var nValue = 0;
            for(var yy = y-1;yy<=y+1;yy++)
                for(var xx = x-1;xx<=x+1;xx++)
                    nValue += oMatrix[yy][xx];

            if(nValue>nHigh)
            {
                nHigh = nValue;
                nCellX = x;
                nCellY = y; 
            }

        }
    if(nHigh>0)
    {
        nBombs++;

        for(var yy = nCellY-1;yy<=nCellY+1;yy++)
        {
            for(var xx = nCellX-1;xx<=nCellX+1;xx++)
            {
                if(oMatrix[yy][xx]<=0)
                    continue;
                oMatrix[yy][xx] = --oMatrix[yy][xx];
            }
        }
        bSpacesLeftToBomb = true;
    }
}
while(bSpacesLeftToBomb);

alert(nBombs+'bombs');

score 2 · Accepted Answer

これは、コーナーの優れた特性を一般化するソリューションです。

与えられたフィールドの完全なドロップポイント、つまりその値を減らす最良の方法を見つけることができると仮定しましょう。次に、投下される爆弾の最小数を見つけるために、アルゴリズムの最初のドラフトは次のようになります (コードは ruby 実装からコピーして貼り付けたものです)。

dropped_bomb_count = 0
while there_are_cells_with_non_zero_count_left
  coordinates = choose_a_perfect_drop_point
  drop_bomb(coordinates)
  dropped_bomb_count += 1
end
return dropped_bomb_count

課題はchoose_a_perfect_drop_point. まず、完璧な落下点とは何かを定義しましょう。

のドロップポイントはの値を(x, y)減少させます(x, y)。また、他のセルの値が減少する場合もあります。
bが減少するセルの適切なスーパーセット内の値を減少させる場合、ドロップポイントaは、ドロップポイントb(x, y)よりも優れています。(x, y)
他に適切なドロップポイントがない場合、ドロップポイントは最大です。
の 2 つのドロップポイントは、同じセットのセルを減少させる場合(x, y)は同等です。
のドロップポイントがのすべての最大ドロップポイントと等しい場合、のドロップポイント(x, y)は完全(x, y)です。

の完全なドロップポイントがある場合、の完全なドロップポイントの 1 つに爆弾を投下するよりも効果的(x, y)に値を減らすことはできません。(x, y)(x, y)

特定のフィールドの完全なドロップポイントは、そのセルのいずれかの完全なドロップポイントです。

以下にいくつかの例を示します。

セル(0, 0)(ゼロベースのインデックス) の完全なドロップポイントはです(1, 1)。、、、およびの他のすべてのドロップポイントで(1, 1)は(0, 0)、減少するセルが少なくなります。(0, 1)(1, 0)

(2, 2)セル(ゼロベースのインデックス)の完全なドロップポイントは(2, 2)であり、周囲のすべてのセル(1, 1)、(1, 2)、(1, 3)、(2, 1)、(2, 3)、(3, 1)、(3, 2)および(3, 3)です。

セルの完全なドロップポイント(2, 2)は次のとおりです。の値(3, 1)が減少し、の値が減少します。の他のすべてのドロップポイントは、セルが 1 つ減少するため、最大ではありません。の完璧なドロップポイントはの完璧なドロップポイントでもあり、フィールドの唯一の完璧なドロップポイントです。これは、このフィールドの完璧なソリューションにつながります (1 つの爆弾投下)。(2, 2)(4, 0)(2, 2)(2, 2)(4, 0)

の完全なドロップポイントはありません(2, 2):(1, 1)と(1, 3)減少(2, 2)と別のセルの両方 (これらはの最大ドロップポイントです(2, 2))。ただし、同等ではありません。しかし、(1, 1)はにとって完璧なドロップポイントで(0, 0)あり、(1, 3)はにとって完璧なドロップポイントです(0, 4)。

完璧なドロップポイントの定義と特定のチェック順序により、質問の例に対して次の結果が得られます。

Drop bomb on 1, 1
Drop bomb on 1, 1
Drop bomb on 1, 5
Drop bomb on 1, 5
Drop bomb on 1, 5
Drop bomb on 1, 6
Drop bomb on 1, 2
Drop bomb on 1, 2
Drop bomb on 0, 6
Drop bomb on 0, 6
Drop bomb on 2, 1
Drop bomb on 2, 5
Drop bomb on 2, 5
Drop bomb on 2, 5
Drop bomb on 3, 1
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 4
Drop bomb on 3, 4
Drop bomb on 3, 3
Drop bomb on 3, 3
Drop bomb on 3, 6
Drop bomb on 3, 6
Drop bomb on 3, 6
Drop bomb on 4, 6
28

ただし、アルゴリズムは、各ステップの後に少なくとも 1 つの完全なドロップポイントがある場合にのみ機能します。完全なドロップポイントがない例を作成することは可能です。

このような場合、アルゴリズムを変更して、完全なドロップポイントの代わりに、最大ドロップポイントの選択が最小限の座標を選択し、各選択の最小値を計算することができます。上記の場合、値を持つすべてのセルに 2 つの最大ドロップポイントがあります。たとえば、(0, 1)には最大のドロップポイント(1, 1)とがあり(1, 2)ます。いずれかを選択して最小値を計算すると、次の結果が得られます。

Drop bomb on 1, 1
Drop bomb on 2, 2
Drop bomb on 1, 2
Drop bomb on 2, 1
2

score 1 · Accepted Answer

評価関数、合計：

int f (int ** matrix, int width, int height, int x, int y)
{
    int m[3][3] = { 0 };

    m[1][1] = matrix[x][y];
    if (x > 0) m[0][1] = matrix[x-1][y];
    if (x < width-1) m[2][1] = matrix[x+1][y];

    if (y > 0)
    {
        m[1][0] = matrix[x][y-1];
        if (x > 0) m[0][0] = matrix[x-1][y-1];
        if (x < width-1) m[2][0] = matrix[x+1][y-1];
    }

    if (y < height-1)
    {
        m[1][2] = matrix[x][y+1];
        if (x > 0) m[0][2] = matrix[x-1][y+1];
        if (x < width-1) m[2][2] = matrix[x+1][y+1];
    }

    return m[0][0]+m[0][1]+m[0][2]+m[1][0]+m[1][1]+m[1][2]+m[2][0]+m[2][1]+m[2][2];
}

目的関数：

Point bestState (int ** matrix, int width, int height)
{
    Point p = new Point(0,0);
    int bestScore = 0;
    int b = 0;

    for (int i=0; i<width; i++)
        for (int j=0; j<height; j++)
        {
            b = f(matrix,width,height,i,j);

            if (b > bestScore)
            {
                bestScore = best;
                p = new Point(i,j);
            }
        }

    retunr p;
}

破壊機能：

void destroy (int ** matrix, int width, int height, Point p)
{
    int x = p.x;
    int y = p.y;

    if(matrix[x][y] > 0) matrix[x][y]--;
    if (x > 0) if(matrix[x-1][y] > 0) matrix[x-1][y]--;
    if (x < width-1) if(matrix[x+1][y] > 0) matrix[x+1][y]--;

    if (y > 0)
    {
        if(matrix[x][y-1] > 0) matrix[x][y-1]--;
        if (x > 0) if(matrix[x-1][y-1] > 0) matrix[x-1][y-1]--;
        if (x < width-1) if(matrix[x+1][y-1] > 0) matrix[x+1][y-1]--;
    }

    if (y < height-1)
    {
        if(matrix[x][y] > 0) matrix[x][y+1]--;
        if (x > 0) if(matrix[x-1][y+1] > 0) matrix[x-1][y+1]--;
        if (x < width-1) if(matrix[x+1][y+1] > 0) matrix[x+1][y+1]--;
    }
}

目標関数：

bool isGoal (int ** matrix, int width, int height)
{
    for (int i=0; i<width; i++)
        for (int j=0; j<height; j++)
            if (matrix[i][j] > 0)
                return false;
    return true;
}

線形最大化関数：

void solve (int ** matrix, int width, int height)
{
    while (!isGoal(matrix,width,height))
    {
        destroy(matrix,width,height, bestState(matrix,width,height));
    }
}

これは最適ではありませんが、より良い評価関数を見つけることで最適化できます。

..しかし、この問題について考えると、主要な問題の1つは、ある時点でゼロの真ん中に放棄された数字を取得することだと思っていたので、別のアプローチを取ります..最小値をゼロに支配してから、ゼロを可能な限りエスケープします。これにより、既存の最小値などが一般的に最小化されます。

score 1 · Accepted Answer

状態空間計画を使用できます。たとえば、次のf = g + hようなヒューリスティックと組み合わせて A* (またはそのバリアントの 1 つ) を使用します。

g: これまでに投下された爆弾の数
h: グリッドのすべての値の合計を 9 で割った値 (これが最良の結果であり、許容できるヒューリスティックがあることを意味します)

score 1 · Accepted Answer

これは、深さ O(3^(n)) のツリーを使用して解決できます。ここで、n はすべての平方の合計です。

最初に、O(9^n) のツリーを使用して問題を解決するのは簡単であると考えてください。考えられるすべての爆撃場所を単純に検討してください。例については、Alfe の実装を参照してください。

次に、ボトムアップで爆撃を行い、最小の爆撃パターンを得ることができることを認識します。

左下隅から始めます。
理にかなっている唯一のプレイ（上と右）で爆破してください。
右に1マス移動します。
ターゲットの値が 0 より大きい間、意味のある 2 つのプレイ (真上または右上) をそれぞれ検討し、ターゲットの値を 1 減らし、可能性ごとに新しい分岐を作成します。
もう1つ右に移動します。
ターゲットの値が 0 より大きい間、意味のある 3 つのプレイ (左上、右上、右上) のそれぞれを検討し、ターゲットの値を 1 減らし、可能性ごとに新しい分岐を作成します。
行が削除されるまで、手順 5 と 6 を繰り返します。
行を上に移動し、パズルが解決されるまで手順 1 ～ 7 を繰り返します。

このアルゴリズムは正しいため、

ある時点で各行を完了する必要があります。
行を完了するには、常にその行の 1 つ上、1 つ下、またはその行内でプレイする必要があります。
列または列の下のプレイよりも、最も低いクリアされていない列の 1 つ上のプレイを選択することは、常に同じかそれよりも優れています。

実際には、このアルゴリズムは定期的に隣人を爆撃し、検索のサイズを縮小するため、理論上の最大値よりも常に優れています。爆撃ごとに 4 つの追加ターゲットの値が減少すると仮定すると、アルゴリズムは O(3^(n/4)) または約 O(1.3^n) で実行されます。

このアルゴリズムは依然として指数関数的であるため、検索の深さを制限することが賢明です。許容される分岐の数をある数 X に制限する場合があります。この深さになると、これまでに識別された最適なパス (最終リーフの 1 つでボードの合計が最小になるパス) をアルゴリズムに強制的に選択させます。）。この場合、アルゴリズムは O(3^X) 時間で実行されることが保証されていますが、正しい答えが得られることは保証されていません。ただし、計算の増加とより良い答えの間のトレードオフが価値がある場合は、いつでも X を増やして経験的にテストできます。

score 1 · Accepted Answer

境界線を爆撃しない (正方形に非境界線がない場合を除く)
ゼロ角。
コーナーをゼロにするには、コーナーの値を 1 平方離れた対角線 (唯一の非境界隣接) にドロップします。
これにより、新しいコーナーが作成されます。2へ

編集: Kostek がほぼ同じアプローチを提案したことに気付かなかったので、今はより強い主張をします: クリアするコーナーが常に最外層にあるように選択されている場合、それが最適です。

OPの例では、5以外に2を（1 + 1または2として）ドロップしても、5にドロップするとヒットする正方形にヒットすることはありません。したがって、単純に 2 を 5 にドロップする必要があります (そして 6 を左下の 1 に ...)

この後、元の 1 (現在は 0) だった隅 (左上) をクリアする方法は 1 つしかありません。それは、B3 (Excel のような表記) に 0 をドロップすることです。等々。

A 列と E 列、1 列と 7 列をすべてクリアしてから、1 階層下の階層をクリアしてください。

意図的にクリアしたものだけをクリアすることを検討してください。0 値のコーナーをクリアするのに費用はかからず、それについて考えるのが簡単になります。

この方法で投下された爆弾はすべて投下する必要があり、これがフィールドのクリアにつながるため、最適なソリューションです。

ぐっすり眠った後、私はこれが真実ではないことに気づきました。検討

私のアプローチでは、B3 と C2 に爆弾を投下しますが、B2 に投下するだけで十分です。

score 1 · Accepted Answer

これが私の解決策です..時間がないのでまだコードに書きませんが、これにより毎回最適な数の移動が生成されるはずです-見つけるのにどれほど効率的かはわかりませんがボムするポイント。

まず、@Luka Rahne がコメントの 1 つで述べたように、爆撃の順序は重要ではなく、組み合わせのみが重要です。

第二に、他の多くの人が述べているように、コーナーよりも多くのポイントに触れるため、コーナーから対角線を離れて 1 爆撃するのが最適です。

これにより、私のバージョンのアルゴリズムの基礎が生成されます。「コーナーからの 1 オフ」を最初または最後に爆撃できます (理論上は問題ありません) (実際には) 後の決定が容易になるため、それらを最初に爆撃します (実際には)同時にそれらのコーナーを爆撃しながら、最も多くのポイントに影響を与えるポイントを爆撃します。

ポイントオブレジスタンスを、ボード内で爆撃不能ポイントが最も多く、その周囲に最大数の 0があるポイントと定義しましょう。

非爆撃ポイントは、私たちが見ているボードの現在のスコープに存在しないポイントとして定義できます。

また、スコープを処理する 4 つの境界を定義します: Top=0、Left=0、Bottom=k、right=j。(開始値)

最後に、最適な爆弾を、抵抗ポイントに隣接するポイントに投下され、(1) 最大値の抵抗ポイントと (2) 可能な最大数のポイントに触れている爆弾として定義します。

アプローチに関しては、我々が外側から内側に向かって作業していることは明らかです。同時に 4 つの「爆撃機」と作業することができます。

抵抗の最初のポイントは明らかに私たちのコーナーです。「範囲外」のポイントは爆撃可能ではありません (各コーナーの範囲外に 5 つのポイントがあります)。そのため、最初にコーナーから斜めにポイントを爆撃します。

アルゴリズム：

4 つの最適な爆弾ポイントを見つけます。
ボムポイントが 2 つの境界 (つまりコーナー) に接触している抵抗ポイントを爆撃している場合、そのポイントまで爆撃するのは 0 です。
各境界について: if(sum(bound)==0) 事前境界

TOP=BOTTOM および LEFT=RIGHT まで繰り返す

後で実際のコードを書いてみる

score 1 · Accepted Answer

最善のヒューリスティックを使用して爆撃キャンペーンを計算する以外に、実際の数を計算する方法は考えられません。妥当な結果が得られることを願っています。

したがって、私の方法は、各セルの爆撃効率メトリックを計算し、最も高い値のセルを爆撃し、....すべてを平坦化するまでプロセスを繰り返します。単純な潜在的なダメージ (つまり、0 から 9 までのスコア) を測定基準として使用することを提唱する人もいますが、価値の高いセルを叩き、ダメージの重複を利用しないため、不十分です。を計算cell value - sum of all neighbouring cellsし、正の値を 0 にリセットし、負の値の絶対値を使用します。直観的に、このメトリクスは、セルを直接叩くのではなく、カウントの高いセルでのダメージの重複を最大化するのに役立つ選択を行う必要があります。

以下のコードは、28 個の爆弾でテストフィールドの完全な破壊に達します (メトリックとして潜在的な損傷を使用すると、31 個が得られることに注意してください!)。

using System;
using System.Collections.Generic;
using System.Linq;

namespace StackOverflow
{
  internal class Program
  {
    // store the battle field as flat array + dimensions
    private static int _width = 5;
    private static int _length = 7;
    private static int[] _field = new int[] {
        2, 3, 4, 7, 1,
        1, 5, 2, 6, 2,
        4, 3, 4, 2, 1,
        2, 1, 2, 4, 1,
        3, 1, 3, 4, 1,
        2, 1, 4, 3, 2,
        6, 9, 1, 6, 4
    };
    // this will store the devastation metric
    private static int[] _metric;

    // do the work
    private static void Main(string[] args)
    {
        int count = 0;

        while (_field.Sum() > 0)
        {
            Console.Out.WriteLine("Round {0}:", ++count);
            GetBlastPotential();
            int cell_to_bomb = FindBestBombingSite();
            PrintField(cell_to_bomb);
            Bomb(cell_to_bomb);
        }
        Console.Out.WriteLine("Done in {0} rounds", count);
    } 

    // convert 2D position to 1D index
    private static int Get1DCoord(int x, int y)
    {
        if ((x < 0) || (y < 0) || (x >= _width) || (y >= _length)) return -1;
        else
        {
            return (y * _width) + x;
        }
    }

    // Convert 1D index to 2D position
    private static void Get2DCoord(int n, out int x, out int y)
    {
        if ((n < 0) || (n >= _field.Length))
        {
            x = -1;
            y = -1;
        }
        else
        {
            x = n % _width;
            y = n / _width;
        }
    }

    // Compute a list of 1D indices for a cell neighbours
    private static List<int> GetNeighbours(int cell)
    {
        List<int> neighbours = new List<int>();
        int x, y;
        Get2DCoord(cell, out x, out y);
        if ((x >= 0) && (y >= 0))
        {
            List<int> tmp = new List<int>();
            tmp.Add(Get1DCoord(x - 1, y - 1));
            tmp.Add(Get1DCoord(x - 1, y));
            tmp.Add(Get1DCoord(x - 1, y + 1));
            tmp.Add(Get1DCoord(x, y - 1));
            tmp.Add(Get1DCoord(x, y + 1));
            tmp.Add(Get1DCoord(x + 1, y - 1));
            tmp.Add(Get1DCoord(x + 1, y));
            tmp.Add(Get1DCoord(x + 1, y + 1));

            // eliminate invalid coords - i.e. stuff past the edges
            foreach (int c in tmp) if (c >= 0) neighbours.Add(c);
        }
        return neighbours;
    }

    // Compute the devastation metric for each cell
    // Represent the Value of the cell minus the sum of all its neighbours
    private static void GetBlastPotential()
    {
        _metric = new int[_field.Length];
        for (int i = 0; i < _field.Length; i++)
        {
            _metric[i] = _field[i];
            List<int> neighbours = GetNeighbours(i);
            if (neighbours != null)
            {
                foreach (int j in neighbours) _metric[i] -= _field[j];
            }
        }
        for (int i = 0; i < _metric.Length; i++)
        {
            _metric[i] = (_metric[i] < 0) ? Math.Abs(_metric[i]) : 0;
        }
    }

    //// Compute the simple expected damage a bomb would score
    //private static void GetBlastPotential()
    //{
    //    _metric = new int[_field.Length];
    //    for (int i = 0; i < _field.Length; i++)
    //    {
    //        _metric[i] = (_field[i] > 0) ? 1 : 0;
    //        List<int> neighbours = GetNeighbours(i);
    //        if (neighbours != null)
    //        {
    //            foreach (int j in neighbours) _metric[i] += (_field[j] > 0) ? 1 : 0;
    //        }
    //    }            
    //}

    // Update the battle field upon dropping a bomb
    private static void Bomb(int cell)
    {
        List<int> neighbours = GetNeighbours(cell);
        foreach (int i in neighbours)
        {
            if (_field[i] > 0) _field[i]--;
        }
    }

    // Find the best bombing site - just return index of local maxima
    private static int FindBestBombingSite()
    {
        int max_idx = 0;
        int max_val = int.MinValue;
        for (int i = 0; i < _metric.Length; i++)
        {
            if (_metric[i] > max_val)
            {
                max_val = _metric[i];
                max_idx = i;
            }
        }
        return max_idx;
    }

    // Display the battle field on the console
    private static void PrintField(int cell)
    {
        for (int x = 0; x < _width; x++)
        {
            for (int y = 0; y < _length; y++)
            {
                int c = Get1DCoord(x, y);
                if (c == cell)
                    Console.Out.Write(string.Format("[{0}]", _field[c]).PadLeft(4));
                else
                    Console.Out.Write(string.Format(" {0} ", _field[c]).PadLeft(4));
            }
            Console.Out.Write(" || ");
            for (int y = 0; y < _length; y++)
            {
                int c = Get1DCoord(x, y);
                if (c == cell)
                    Console.Out.Write(string.Format("[{0}]", _metric[c]).PadLeft(4));
                else
                    Console.Out.Write(string.Format(" {0} ", _metric[c]).PadLeft(4));
            }
            Console.Out.WriteLine();
        }
        Console.Out.WriteLine();
    }           
  }
}

結果の爆撃パターンは次のように出力されます (左側のフィールド値、右側のメトリック)

Round 1:
  2   1   4   2   3   2   6  ||   7  16   8  10   4  18   6
  3   5   3   1   1   1   9  ||  11  18  18  21  17  28   5
  4  [2]  4   2   3   4   1  ||  19 [32] 21  20  17  24  22
  7   6   2   4   4   3   6  ||   8  17  20  14  16  22   8
  1   2   1   1   1   2   4  ||  14  15  14  11  13  16   7

Round 2:
  2   1   4   2   3   2   6  ||   5  13   6   9   4  18   6
  2   4   2   1   1  [1]  9  ||  10  15  17  19  17 [28]  5
  3   2   3   2   3   4   1  ||  16  24  18  17  17  24  22
  6   5   1   4   4   3   6  ||   7  14  19  12  16  22   8
  1   2   1   1   1   2   4  ||  12  12  12  10  13  16   7

Round 3:
  2   1   4   2   2   1   5  ||   5  13   6   7   3  15   5
  2   4   2   1   0   1   8  ||  10  15  17  16  14  20   2
  3  [2]  3   2   2   3   0  ||  16 [24] 18  15  16  21  21
  6   5   1   4   4   3   6  ||   7  14  19  11  14  19   6
  1   2   1   1   1   2   4  ||  12  12  12  10  13  16   7

Round 4:
  2   1   4   2   2   1   5  ||   3  10   4   6   3  15   5
  1   3   1   1   0   1   8  ||   9  12  16  14  14  20   2
  2   2   2   2   2  [3]  0  ||  13  16  15  12  16 [21] 21
  5   4   0   4   4   3   6  ||   6  11  18   9  14  19   6
  1   2   1   1   1   2   4  ||  10   9  10   9  13  16   7

Round 5:
  2   1   4   2   2   1   5  ||   3  10   4   6   2  13   3
  1   3   1   1   0  [0]  7  ||   9  12  16  13  12 [19]  2
  2   2   2   2   1   3   0  ||  13  16  15  10  14  15  17
  5   4   0   4   3   2   5  ||   6  11  18   7  13  17   6
  1   2   1   1   1   2   4  ||  10   9  10   8  11  13   5

Round 6:
  2   1   4   2   1   0   4  ||   3  10   4   5   2  11   2
  1   3   1   1   0   0   6  ||   9  12  16  11   8  13   0
  2   2   2   2   0   2   0  ||  13  16  15   9  14  14  15
  5   4  [0]  4   3   2   5  ||   6  11 [18]  6  11  15   5
  1   2   1   1   1   2   4  ||  10   9  10   8  11  13   5

Round 7:
  2   1   4   2   1   0   4  ||   3  10   4   5   2  11   2
  1   3   1   1   0   0   6  ||   8  10  13   9   7  13   0
  2  [1]  1   1   0   2   0  ||  11 [15] 12   8  12  14  15
  5   3   0   3   3   2   5  ||   3   8  10   3   8  15   5
  1   1   0   0   1   2   4  ||   8   8   7   7   9  13   5

Round 8:
  2   1   4   2   1   0   4  ||   1   7   2   4   2  11   2
  0   2   0   1   0   0   6  ||   7   7  12   7   7  13   0
  1   1   0   1   0   2   0  ||   8   8  10   6  12  14  15
  4   2   0   3   3  [2]  5  ||   2   6   8   2   8 [15]  5
  1   1   0   0   1   2   4  ||   6   6   6   7   9  13   5

Round 9:
  2   1   4   2   1   0   4  ||   1   7   2   4   2  11   2
  0   2   0   1   0   0   6  ||   7   7  12   7   6  12   0
  1   1   0   1   0  [1]  0  ||   8   8  10   5  10 [13] 13
  4   2   0   3   2   2   4  ||   2   6   8   0   6   9   3
  1   1   0   0   0   1   3  ||   6   6   6   5   8  10   4

Round 10:
  2   1   4   2   1   0   4  ||   1   7   2   4   2  10   1
  0   2  [0]  1   0   0   5  ||   7   7 [12]  7   6  11   0
  1   1   0   1   0   1   0  ||   8   8  10   4   8   9  10
  4   2   0   3   1   1   3  ||   2   6   8   0   6   8   3
  1   1   0   0   0   1   3  ||   6   6   6   4   6   7   2

Round 11:
  2   0   3   1   1   0   4  ||   0   6   0   3   0  10   1
  0   1   0   0   0  [0]  5  ||   4   5   5   5   3 [11]  0
  1   0   0   0   0   1   0  ||   6   8   6   4   6   9  10
  4   2   0   3   1   1   3  ||   1   5   6   0   5   8   3
  1   1   0   0   0   1   3  ||   6   6   6   4   6   7   2

Round 12:
  2   0   3   1   0   0   3  ||   0   6   0   2   1   7   1
  0   1   0   0   0   0   4  ||   4   5   5   4   1   7   0
  1   0   0   0   0  [0]  0  ||   6   8   6   4   5  [9]  8
  4   2   0   3   1   1   3  ||   1   5   6   0   4   7   2
  1   1   0   0   0   1   3  ||   6   6   6   4   6   7   2

Round 13:
  2   0   3   1   0   0   3  ||   0   6   0   2   1   6   0
  0   1   0   0   0   0   3  ||   4   5   5   4   1   6   0
  1  [0]  0   0   0   0   0  ||   6  [8]  6   3   3   5   5
  4   2   0   3   0   0   2  ||   1   5   6   0   4   6   2
  1   1   0   0   0   1   3  ||   6   6   6   3   4   4   0

Round 14:
  2   0   3   1   0  [0]  3  ||   0   5   0   2   1  [6]  0
  0   0   0   0   0   0   3  ||   2   5   4   4   1   6   0
  0   0   0   0   0   0   0  ||   4   4   4   3   3   5   5
  3   1   0   3   0   0   2  ||   0   4   5   0   4   6   2
  1   1   0   0   0   1   3  ||   4   4   5   3   4   4   0

Round 15:
  2   0   3   1   0   0   2  ||   0   5   0   2   1   4   0
  0   0   0   0   0   0   2  ||   2   5   4   4   1   4   0
  0   0   0   0   0   0   0  ||   4   4   4   3   3   4   4
  3   1   0   3   0  [0]  2  ||   0   4   5   0   4  [6]  2
  1   1   0   0   0   1   3  ||   4   4   5   3   4   4   0

Round 16:
  2  [0]  3   1   0   0   2  ||   0  [5]  0   2   1   4   0
  0   0   0   0   0   0   2  ||   2   5   4   4   1   4   0
  0   0   0   0   0   0   0  ||   4   4   4   3   3   3   3
  3   1   0   3   0   0   1  ||   0   4   5   0   3   3   1
  1   1   0   0   0   0   2  ||   4   4   5   3   3   3   0

Round 17:
  1   0   2   1   0   0   2  ||   0   3   0   1   1   4   0
  0   0   0   0   0   0   2  ||   1   3   3   3   1   4   0
  0   0   0   0   0   0   0  ||   4   4   4   3   3   3   3
  3   1  [0]  3   0   0   1  ||   0   4  [5]  0   3   3   1
  1   1   0   0   0   0   2  ||   4   4   5   3   3   3   0

Round 18:
  1   0   2   1   0   0   2  ||   0   3   0   1   1   4   0
  0   0   0   0   0   0   2  ||   1   3   3   3   1   4   0
  0   0   0   0   0   0   0  ||   3   3   2   2   2   3   3
  3  [0]  0   2   0   0   1  ||   0  [4]  2   0   2   3   1
  1   0   0   0   0   0   2  ||   2   4   2   2   2   3   0

Round 19:
  1   0   2   1   0  [0]  2  ||   0   3   0   1   1  [4]  0
  0   0   0   0   0   0   2  ||   1   3   3   3   1   4   0
  0   0   0   0   0   0   0  ||   2   2   2   2   2   3   3
  2   0   0   2   0   0   1  ||   0   2   2   0   2   3   1
  0   0   0   0   0   0   2  ||   2   2   2   2   2   3   0

Round 20:
  1  [0]  2   1   0   0   1  ||   0  [3]  0   1   1   2   0
  0   0   0   0   0   0   1  ||   1   3   3   3   1   2   0
  0   0   0   0   0   0   0  ||   2   2   2   2   2   2   2
  2   0   0   2   0   0   1  ||   0   2   2   0   2   3   1
  0   0   0   0   0   0   2  ||   2   2   2   2   2   3   0

Round 21:
  0   0   1   1   0   0   1  ||   0   1   0   0   1   2   0
  0   0   0   0   0   0   1  ||   0   1   2   2   1   2   0
  0   0   0   0   0   0   0  ||   2   2   2   2   2   2   2
  2   0   0   2   0  [0]  1  ||   0   2   2   0   2  [3]  1
  0   0   0   0   0   0   2  ||   2   2   2   2   2   3   0

Round 22:
  0   0   1   1   0   0   1  ||   0   1   0   0   1   2   0
  0   0   0   0   0   0   1  ||   0   1   2   2   1   2   0
 [0]  0   0   0   0   0   0  ||  [2]  2   2   2   2   1   1
  2   0   0   2   0   0   0  ||   0   2   2   0   2   1   1
  0   0   0   0   0   0   1  ||   2   2   2   2   2   1   0

Round 23:
  0   0   1   1   0   0   1  ||   0   1   0   0   1   2   0
  0   0  [0]  0   0   0   1  ||   0   1  [2]  2   1   2   0
  0   0   0   0   0   0   0  ||   1   1   2   2   2   1   1
  1   0   0   2   0   0   0  ||   0   1   2   0   2   1   1
  0   0   0   0   0   0   1  ||   1   1   2   2   2   1   0

Round 24:
  0   0   0   0   0   0   1  ||   0   0   0   0   0   2   0
  0   0   0   0   0   0   1  ||   0   0   0   0   0   2   0
  0   0  [0]  0   0   0   0  ||   1   1  [2]  2   2   1   1
  1   0   0   2   0   0   0  ||   0   1   2   0   2   1   1
  0   0   0   0   0   0   1  ||   1   1   2   2   2   1   0

Round 25:
  0   0   0   0   0  [0]  1  ||   0   0   0   0   0  [2]  0
  0   0   0   0   0   0   1  ||   0   0   0   0   0   2   0
  0   0   0   0   0   0   0  ||   1   1   1   1   1   1   1
  1   0   0   1   0   0   0  ||   0   1   1   0   1   1   1
  0   0   0   0   0   0   1  ||   1   1   1   1   1   1   0

Round 26:
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
 [0]  0   0   0   0   0   0  ||  [1]  1   1   1   1   0   0
  1   0   0   1   0   0   0  ||   0   1   1   0   1   1   1
  0   0   0   0   0   0   1  ||   1   1   1   1   1   1   0

Round 27:
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0  [0]  0   0   0   0  ||   0   0  [1]  1   1   0   0
  0   0   0   1   0   0   0  ||   0   0   1   0   1   1   1
  0   0   0   0   0   0   1  ||   0   0   1   1   1   1   0

Round 28:
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0  [0]  0  ||   0   0   0   0   0  [1]  1
  0   0   0   0   0   0   1  ||   0   0   0   0   0   1   0

Done in 28 rounds

score 1 · Accepted Answer

ボードをきれいにする絶対最適解が必要な場合は、古典的なバックトラッキングを使用する必要がありますが、マトリックスが非常に大きい場合、最適解を見つけるのに時間がかかります。「可能な」最適解が必要な場合は、貪欲なアルゴリズムを使用できます、アルゴリズムを書くのに助けが必要なら、私はあなたを助けることができます

それが最善の方法だと考えてみてください。そこに爆弾を投下して削除したポイントを保存する別のマトリックスを作成し、最大ポイントを持つセルを選択し、そこに爆弾を投下してポイントマトリックスを更新し、続行します。例：

2 3 5 -> (2+(1*3)) (3+(1*5)) (5+(1*3))
1 3 2 -> (1+(1*4)) (3+(1*7)) (2+(1*4))
1 0 2 -> (1+(1*2)) (0+(1*5)) (2+(1*2))

0 より大きい値を持つすべての隣接セルのセル値 +1

score 1 · Accepted Answer

さて、ボードの位置に 1、2、...、nx m の番号を付けたとします。一連の爆弾投下は、このセット内の一連の数字で表すことができ、数字は繰り返すことができます。ただし、ボード上の効果は、爆弾を投下する順序に関係なく同じであるため、実際に投下する爆弾の選択は、nxm 番号のリストとして表すことができます。ここで、最初の数字は、位置 1 に投下された爆弾の数を表します。、2 番目の数字は位置 2 に投下された爆弾の数などを表します。この nxm 数字のリストを「キー」と呼びましょう。

最初に 1 回の爆弾投下によるすべてのボードの状態を計算し、次にこれらを使用して 2 回の爆弾投下によるすべてのボード状態を計算し、すべてゼロになるまで続けることができます。ただし、各ステップで、上で定義したキーを使用して状態をキャッシュするため、これらの結果を次のステップの計算に使用できます (「動的プログラミング」アプローチ)。

ただし、n、m、およびグリッド内の数値のサイズによっては、このアプローチのメモリ要件が過剰になる場合があります。N + 1 のすべての結果を計算したら、N 回の爆弾投下のすべての結果を捨てることができるので、いくらか節約できます。そしてもちろん、より長い時間がかかるという代償を払って何かをキャッシュすることはできません。動的プログラミングのアプローチでは、速度と引き換えにメモリが犠牲になります。

score 1 · Accepted Answer

私も28手でした。私は次の最良の手を決めるために 2 つのテストを使用しました。第二に、合計が等しい場合、次のように定義される最大密度を生成する移動:

number-of-zeros / number-of-groups-of-zeros

ハスケルです。「ソルブボード」は、エンジンのソリューションを示しています。「main」と入力してゲームをプレイし、目標点を入力するか、「best」を推奨するか、「quit」を入力して終了します。

出力:
*Main> 解決ボード
[(4,4),(3,6),(3,3),(2,2),(2,2),(4,6),(4,6), (2,6),(3,2),(4,2),(2,6),(3,3),(4,3),(2,6),(4,2),(4 ,6),(4,6),(3,6),(2,6),(2,6),(2,4),(2,4),(2,6),(3,6) ),(4,2),(4,2),(4,2),(4,2)]

import Data.List
import Data.List.Split
import Data.Ord
import Data.Function(on)

board = [2,3,4,7,1,
         1,5,2,6,2,
         4,3,4,2,1,
         2,1,2,4,1,
         3,1,3,4,1,
         2,1,4,3,2,
         6,9,1,6,4]

n = 5
m = 7

updateBoard board pt =
  let x = fst pt
      y = snd pt
      precedingLines = replicate ((y-2) * n) 0
      bomb = concat $ replicate (if y == 1
                                    then 2
                                    else min 3 (m+2-y)) (replicate (x-2) 0 
                                                         ++ (if x == 1 
                                                                then [1,1]
                                                                else replicate (min 3 (n+2-x)) 1)
                                                                ++ replicate (n-(x+1)) 0)
  in zipWith (\a b -> max 0 (a-b)) board (precedingLines ++ bomb ++ repeat 0)

showBoard board = 
  let top = "   " ++ (concat $ map (\x -> show x ++ ".") [1..n]) ++ "\n"
      chunks = chunksOf n board
  in putStrLn (top ++ showBoard' chunks "" 1)
       where showBoard' []     str count = str
             showBoard' (x:xs) str count =
               showBoard' xs (str ++ show count ++ "." ++ show x ++ "\n") (count+1)

instances _ [] = 0
instances x (y:ys)
  | x == y    = 1 + instances x ys
  | otherwise = instances x ys

density a = 
  let numZeros = instances 0 a
      groupsOfZeros = filter (\x -> head x == 0) (group a)
  in if null groupsOfZeros then 0 else numZeros / fromIntegral (length groupsOfZeros)

boardDensity board = sum (map density (chunksOf n board))

moves = [(a,b) | a <- [2..n-1], b <- [2..m-1]]               

bestMove board = 
  let lowestSumMoves = take 1 $ groupBy ((==) `on` snd) 
                              $ sortBy (comparing snd) (map (\x -> (x, sum $ updateBoard board x)) (moves))
  in if null lowestSumMoves
        then (0,0)
        else let lowestSumMoves' = map (\x -> fst x) (head lowestSumMoves) 
             in fst $ head $ reverse $ sortBy (comparing snd) 
                (map (\x -> (x, boardDensity $ updateBoard board x)) (lowestSumMoves'))   

solve board = solve' board [] where
  solve' board result
    | sum board == 0 = result
    | otherwise      = 
        let best = bestMove board 
        in solve' (updateBoard board best) (result ++ [best])

main :: IO ()
main = mainLoop board where
  mainLoop board = do 
    putStrLn ""
    showBoard board
    putStr "Pt: "
    a <- getLine
    case a of 
      "quit"    -> do putStrLn ""
                      return ()
      "best"    -> do putStrLn (show $ bestMove board)
                      mainLoop board
      otherwise -> let ws = splitOn "," a
                       pt = (read (head ws), read (last ws))
                   in do mainLoop (updateBoard board pt)

score 1 · Accepted Answer

ここには非二部一致部分構造があるようです。次の例を検討してください。

この場合の最適解は、サイズ 5 です。これは、9 サイクルの頂点をエッジでカバーする最小のサイズだからです。

特に、このケースは、何人かが投稿した線形計画法の緩和が正確でなく、機能せず、その他すべての悪いことを示しています。「平面立方グラフの頂点をできるだけ少ないエッジでカバーする」ことをあなたの問題に減らすことができると確信しています。

最悪の場合、これを多項式時間で解決する方法がわかりません。私が見ていない非常に巧妙な二分探索と DP の解決策があるかもしれません。

編集: コンテスト ( http://deadline24.pl ) は言語に依存していないようです。彼らはあなたにたくさんの入力ファイルを送り、あなたはそれらに出力を送ります。したがって、最悪の場合の多項式時間で実行されるものは必要ありません。特に、入力を見ることができます!

入力には小さなケースがたくさんあります。次に、10x1000 のケース、100x100 のケース、1000x1000 のケースがあります。3つの大きなケースはすべて非常に行儀が良いです。通常、水平方向に隣接するエントリは同じ値を持ちます。比較的強力なマシンでは、CPLEX を使用したブルートフォースによってすべてのケースをわずか数分で解決できます。私は 1000x1000 でラッキーでした。LP緩和にはたまたま積分最適解があります。.ans私のソリューションは、テストデータバンドルで提供されるファイルと一致します。

入力の構造を見ていただければ、私が行ったよりもはるかに直接的な方法で入力の構造を使用できると思います。最初の行、2 つ、または 3 つの行を、何もなくなるまで繰り返し削除できるようです。（1000x1000では、すべての行が増加していないように見えますか？それがあなたの「パートB」の由来だと思いますか？）

score 1 · Accepted Answer

強引な！

効率的ではないことはわかっていますが、より高速なアルゴリズムを見つけたとしても、いつでもこの結果をテストして、その精度を知ることができます。

次のように、再帰を使用します。

void fn(tableState ts, currentlevel cl)
{
  // first check if ts is all zeros yet, if not:
  //
  // do a for loop to go through all cells of ts, 
  // for each cell do a bomb, and then
  // call: 
  // fn(ts, cl + 1);

}

キャッシュすることでこれをより効率的にすることができます。別の方法で同じ結果が得られる場合は、同じ手順を繰り返さないでください。

詳しく説明するには:

セル 1,3,5 の爆撃がセル 5,3,1 の爆撃と同じ結果につながる場合、両方のケースで次のすべての手順をやり直す必要はありません。1 つだけで十分です。すべてをどこかに保存する必要があります。表の状態とその結果を使用します。

テーブル統計のハッシュを使用して、高速比較を行うことができます。

score 0 · Accepted Answer

これは最初に尋ねられた質問に対する答えでした。彼がパラメータを変更したことに気づかなかった。

すべてのターゲットのリストを作成します。ドロップによって影響を受ける正の値の数（それ自体、およびすべてのネイバー）に基づいて、ターゲットに値を割り当てます。最高値は9になります。

影響を受けたターゲットの数（降順）でターゲットを並べ替え、影響を受けた各ターゲットの合計に2番目の降順で並べ替えます。

最高ランクのターゲットに爆弾を投下し、ターゲットを再計算して、すべてのターゲット値がゼロになるまで繰り返します。

同意しましたが、これが常に最適であるとは限りません。例えば、

このアプローチでは、爆弾を5発クリアする必要があります。ただし、最適には4で実行できます。それでも、かなり近くにあり、バックトラックはありません。ほとんどの場合、それは最適であるか、非常に近いでしょう。

元の問題番号を使用して、このアプローチは28の爆弾で解決します。

このアプローチを示すコードを追加する（ボタン付きのフォームを使用）：

         private void button1_Click(object sender, EventArgs e)
    {
        int[,] matrix = new int[10, 10] {{5, 20, 7, 1, 9, 8, 19, 16, 11, 3}, 
                                         {17, 8, 15, 17, 12, 4, 5, 16, 8, 18},
                                         { 4, 19, 12, 11, 9, 7, 4, 15, 14, 6},
                                         { 17, 20, 4, 9, 19, 8, 17, 2, 10, 8},
                                         { 3, 9, 10, 13, 8, 9, 12, 12, 6, 18}, 
                                         {16, 16, 2, 10, 7, 12, 17, 11, 4, 15},
                                         { 11, 1, 15, 1, 5, 11, 3, 12, 8, 3},
                                         { 7, 11, 16, 19, 17, 11, 20, 2, 5, 19},
                                         { 5, 18, 2, 17, 7, 14, 19, 11, 1, 6},
                                         { 13, 20, 8, 4, 15, 10, 19, 5, 11, 12}};


        int value = 0;
        List<Target> Targets = GetTargets(matrix);
        while (Targets.Count > 0)
        {
            BombTarget(ref matrix, Targets[0]);
            value += 1;
            Targets = GetTargets(matrix);
        }
        Console.WriteLine( value);
        MessageBox.Show("done: " + value);
    }

    private static void BombTarget(ref int[,] matrix, Target t)
    {
        for (int a = t.x - 1; a <= t.x + 1; a++)
        {
            for (int b = t.y - 1; b <= t.y + 1; b++)
            {
                if (a >= 0 && a <= matrix.GetUpperBound(0))
                {
                    if (b >= 0 && b <= matrix.GetUpperBound(1))
                    {
                        if (matrix[a, b] > 0)
                        {
                            matrix[a, b] -= 1;
                        }
                    }
                }
            }
        }
        Console.WriteLine("Dropped bomb on " + t.x + "," + t.y);
    }

    private static List<Target> GetTargets(int[,] matrix)
    {
        List<Target> Targets = new List<Target>();
        int width = matrix.GetUpperBound(0);
        int height = matrix.GetUpperBound(1);
        for (int x = 0; x <= width; x++)
        {
            for (int y = 0; y <= height; y++)
            {
                Target t = new Target();
                t.x = x;
                t.y = y;
                SetTargetValue(matrix, ref t);
                if (t.value > 0) Targets.Add(t);
            }
        }
        Targets = Targets.OrderByDescending(x => x.value).ThenByDescending( x => x.sum).ToList();
        return Targets;
    }

    private static void SetTargetValue(int[,] matrix, ref Target t)
    {
        for (int a = t.x - 1; a <= t.x + 1; a++)
        {
            for (int b = t.y - 1; b <= t.y + 1; b++)
            {
                if (a >= 0 && a <= matrix.GetUpperBound(0))
                {
                    if (b >= 0 && b <= matrix.GetUpperBound(1))
                    {
                        if (matrix[ a, b] > 0)
                        {
                            t.value += 1;
                            t.sum += matrix[a,b];
                        }

                    }
                }
            }
        }

    }

必要なクラス：

        class Target
    {
        public int value;
        public int sum;
        public int x;
        public int y;
    }

score 0 · Accepted Answer

これまでのいくつかの答えは指数関数的な時間を与え、動的プログラミングを伴うものもあります。それらが必要かどうかは疑問です。

私の解決策はO(mnS)です。ここで、 m、nはボードの寸法、Sはすべての整数の合計です。アイデアはかなり強引です: 毎回最もキルできる場所を見つけて、0 で終了します。

指定されたボードに対して 28 回の移動が可能で、ドロップするたびにボードが出力されます。

完全な自明のコード:

import java.util.Arrays;

public class BombMinDrops {

    private static final int[][] BOARD = {{2,3,4,7,1}, {1,5,2,6,2}, {4,3,4,2,1}, {2,1,2,4,1}, {3,1,3,4,1}, {2,1,4,3,2}, {6,9,1,6,4}};
    private static final int ROWS = BOARD.length;
    private static final int COLS = BOARD[0].length;
    private static int remaining = 0;
    private static int dropCount = 0;
    static {
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                remaining = remaining + BOARD[i][j];
            }
        }
    }

    private static class Point {
        int x, y;
        int kills;

        Point(int x, int y, int kills) {
            this.x = x;
            this.y = y;
            this.kills = kills;
        }

        @Override
        public String toString() {
            return dropCount + "th drop at [" + x + ", " + y + "] , killed " + kills;
        }
    }

    private static int countPossibleKills(int x, int y) {
        int count = 0;
        for (int row = x - 1; row <= x + 1; row++) {
            for (int col = y - 1; col <= y + 1; col++) {
                try {
                    if (BOARD[row][col] > 0) count++;
                } catch (ArrayIndexOutOfBoundsException ex) {/*ignore*/}
            }
        }

        return count;
    }

    private static void drop(Point here) {
        for (int row = here.x - 1; row <= here.x + 1; row++) {
            for (int col = here.y - 1; col <= here.y + 1; col++) {
                try {
                    if (BOARD[row][col] > 0) BOARD[row][col]--;
                } catch (ArrayIndexOutOfBoundsException ex) {/*ignore*/}
            }
        }

        dropCount++;
        remaining = remaining - here.kills;
        print(here);
    }

    public static void solve() {
        while (remaining > 0) {
            Point dropWithMaxKills = new Point(-1, -1, -1);
            for (int i = 0; i < ROWS; i++) {
                for (int j = 0; j < COLS; j++) {
                    int possibleKills = countPossibleKills(i, j);
                    if (possibleKills > dropWithMaxKills.kills) {
                        dropWithMaxKills = new Point(i, j, possibleKills);
                    }
                }
            }

            drop(dropWithMaxKills);
        }

        System.out.println("Total dropped: " + dropCount);
    }

    private static void print(Point drop) {
        System.out.println(drop.toString());
        for (int[] row : BOARD) {
            System.out.println(Arrays.toString(row));
        }

        System.out.println();
    }

    public static void main(String[] args) {
        solve();
    }

}

score 0 · Accepted Answer

最も遅いが最も単純でエラーのないアルゴリズムは、すべての有効な可能性を生成してテストすることです。この場合は非常に単純です (結果は爆弾の配置の順序に依存しないため)。

bomp を N 回適用する関数を作成する
すべての爆弾配置/爆弾カウントの可能性のためのループを作成します (行列==0 で停止)
常に最善の解決策を覚えておいてください。
ループの終わりに、あなたは最善の解決策を持っています
- 爆弾の数だけでなく、その配置も

コードは次のようになります。

void copy(int **A,int **B,int m,int n)
    {
    for (int i=0;i<m;i++)
     for (int j=0;i<n;j++)
       A[i][j]=B[i][j];
    }

bool is_zero(int **M,int m,int n)
    {
    for (int i=0;i<m;i++)
     for (int j=0;i<n;j++)
      if (M[i][j]) return 0;
    return 1;
    }

void drop_bomb(int **M,int m,int n,int i,int j,int N)
    {
    int ii,jj;
    ii=i-1; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i-1; jj=j  ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i-1; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i  ; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i  ; jj=j  ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i  ; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i+1; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i+1; jj=j  ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i+1; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    }

void solve_problem(int **M,int m,int n)
    {
    int i,j,k,max=0;
    // you probably will need to allocate matrices P,TP,TM yourself instead of this:
    int P[m][n],min;             // solution: placement,min bomb count
    int TM[m][n],TP[m][n],cnt;   // temp
    for (i=0;i<m;i++)            // max count of bomb necessary to test
     for (j=0;j<n;j++)
      if (max<M[i][j]) max=M[i][j];
    for (i=0;i<m;i++)            // reset solution
     for (j=0;j<n;j++)
      P[i][j]=max;
    min=m*n*max; 
        copy(TP,P,m,n); cnt=min;

    for (;;)  // generate all possibilities
        {
        copy(TM,M,m,n);
        for (i=0;i<m;i++)   // test solution
         for (j=0;j<n;j++)
          drop_bomb(TM,m,n,TP[i][j]);
        if (is_zero(TM,m,n))// is solution
         if (min>cnt)       // is better solution -> store it
            {
            copy(P,TP,m,n); 
            min=cnt;    
            }
        // go to next possibility
        for (i=0,j=0;;)
            {
            TP[i][j]--;
            if (TP[i][j]>=0) break;
            TP[i][j]=max;
                 i++; if (i<m) break;
            i=0; j++; if (j<n) break;
            break;
            }
        if (is_zero(TP,m,n)) break;
        }
    //result is in P,min
    }

これは多くの方法で最適化できます...最も簡単なのは、M マトリックスでソリューションをリセットすることですが、最大値と TP[][] デクリメントコードを変更する必要があります

score 0 · Accepted Answer

この問題のすべては、編集距離を計算することです。与えられた行列とゼロ行列の間のレーベンシュタイン距離のバリアントを計算するだけで、編集が爆撃に置き換えられ、動的計画法を使用して中間配列間の距離が保存されます。行列のハッシュをキーとして使用することをお勧めします。疑似 Python の場合:

memo = {}

def bomb(matrix,i,j):
    # bomb matrix at i,j

def bombsRequired(matrix,i,j):
    # bombs required to zero matrix[i,j]

def distance(m1, i, len1, m2, j, len2):
    key = hash(m1)
    if memo[key] != None: 
        return memo[key]

    if len1 == 0: return len2
    if len2 == 0: return len1

    cost = 0
    if m1 != m2: cost = m1[i,j]
    m = bomb(m1,i,j)
    dist = distance(str1,i+1,len1-1,str2,j+1,len2-1)+cost)
    memo[key] = dist
    return dist

algorithm - 爆弾投下アルゴリズム

32 に答える 32

分枝限定法を使用した Mathematica 整数線形計画法

貪欲なアルゴリズムでこれを読んでいる人のために

Related

Reference