壁に射手を置く

Question

私は城壁とその周囲を表す行列（0と1を持つ）を持っています。

私の仕事は、できるだけ多くの周囲をカバーするように、壁に弓術師をn置くことです。 2つのルールがあります。

：すべての射手は1の範囲にしている - 壁でない手段、彼は唯一の隣接するタイルの上に撮影することができます（各タイルは、8近傍を持っているが）、（フレンドリー・ファイアは、この中に禁止されていること軍！）。

：このような場合、その複数の射手は同じタイルで撮影することができます。そのタイルは1つだけカウントされます。

多項式時間に存在するものがあるかどうかわからないので、これは効果的な解を見つけるのに苦労しています。 ありますか？

私は最初のステップは、行列のすべてのタイルを評価するためにBFSアルゴリズムを使用することですが、私は効果的に第2のルールでそれを解決する方法がわかりません。ブルートフォースの解決策は非常に単純です - すべてのポジションを評価し、すべてを試してみてください。非常に効果がありません - 私はO（|可能なプレースメント|^n）と思っています。

簡単な例：

灰色のタイル壁を表します。タイルの中の数字は、そのタイルに置かれたアーチャーのカバレッジを表しています。確かに、オレンジ色のものを追加しました。これはタイルb2にアーチャーが立っているかどうかを表しています。そして、最後の情報 - 正しい解決策はb2とb6で、カバレッジは14です.b2とb4はできません。なぜなら、それらは11タイルしかカバーしないからです。

Answer 1

私は問題が保証多項式時間で解くことができる方法を見ていないが、あなたは、このようなGLPKとしてILPソルバーを使用して解決することができる整数線形プログラム、などの問題を表現することができます。

c[i]を0-1の整数変数にすることができます。これは、周囲の四角形ごとに1つです。これらは、この広場が少なくとも1人の射手によって覆われているかどうかを表します。

a[i]を0-1の整数変数にすることができます。これは、城壁の各正方形に対して1つです。射手がこの広場に立っているかどうかを表します。何の隣接射手がない場合sum(a[i] for i in castle walls) <= n

c[i]はゼロでなければならない：sum(a[j] for j castle wall adjacent to i) >= c[i]

最適化の対象はsum(c[i])を最大化することである

は、最もn射手がなければなりません。

たとえば、これはマップ（.が周囲にあり、#城壁）であり、2つの射手を配置したいとします。

次に、すべての変数が0-1の整数変数であるILPの問題があります。

maximize (
     c[0,0] + c[0,1] + c[0,2] + c[0,3] 
    + c[1,0] 
    + c[2,0] + c[2,1] + c[2,2] + c[2,3]) 

such that: 

a[1,1] + a[1,2] + a[1,3] <= 2 

c[0,0] <= a[1,1] 
c[0,1] <= a[1,1] + a[1,2] 
c[0,2] <= a[1,1] + a[1,2] + a[1,3] 
c[0,3] <= a[1,2] + a[1,3] 
c[1,0] <= a[1,1] 
c[2,0] <= a[1,1] 
c[2,1] <= a[1,1] + a[1,2] 
c[2,2] <= a[1,1] + a[1,2] + a[1,3] 
c[2,3] <= a[1,2] + a[1,3]