我有一些的寬度和高度，其中每個單元可以是三種可能值的網格（呈現爲白色，綠色和紅色在該圖示）：網格算法的益智
illustration http://corexii.com/grid-algorithm-problem-2.png
您可以選擇任何數量的綠色細胞（標記在下面的圖示藍色），其覆蓋所述選擇的細胞周圍的預定平方半徑（這裏）所有紅細胞（標記爲黃色）：
illustration http://corexii.com/grid-algorithm-problem-3.png
的目標是：
任何人有任何一個算法的想法？
我在看很多的理論，但我最感興趣的是近似做這個快速而不是準確。快速，合理的結果比整天計算最佳結果要好。
（上面的圖示可以呈現這些細胞的最正態分佈，但不應當被假定爲像的所有可能的分佈。）
此問題是重要的NP-硬set cover problem的一種特殊情況。 （宇宙由紅色單元組成，每個組由一個綠色單元的半徑內的紅色單元組成）。greedy algorithm獲得最佳結果的因子。
templatetypedef is right to point out這樣一個事實，這個問題是一個NP難問題的一種特殊情況並不能證明它實際上是NP難了。這就是爲什麼我在我的措辭中小心謹慎，而不是暗示後者。但是作爲一個NP難題的特殊情況是一個不容忽視的信號：許多特殊情況下進一步調查本身就是NP難題。
所以，這裏有一個粗略的草圖，說明這個問題實際上是NP-hard，通過在最常見的四個平面圖上減少VERTEX COVER。
假設我們有度的至多四個平面圖形，例如：
表示由綠色正方形的每個頂點，並且通過紅色和綠色的方塊，使得交替的鏈中的每個邊緣有偶數個綠色正方形，奇數個紅色正方形，每個綠色正方形只會覆蓋任何一邊的兩個紅色正方形，如果選擇的話。爲2的半徑，這是圖的一個可能的表示：
爲了覆蓋所有的紅色正方形，我們需要選擇綠色正方形的至少一半上對應於各鏈邊緣原始圖。如果我們在每個鏈上選擇恰好一半的綠色方塊，那麼在每個邊的一端留下一個未覆蓋的紅色方塊（我們可以選擇哪一端）。因此，如果我們可以找到最小的一組頂點，那麼我們就可以得到最小的一組綠色方塊，使得每條邊都入射到該組頂點。
在這個例子中，我們可以使用八個綠色方塊覆蓋紅色正方形，如果我們挑頂點一個和d：
與此對應的最小頂點覆蓋在原來的圖表：
符合第一和第三標準，在第二個標準中不合格 – 2012-03-20 23:32:24
這是集覆蓋的特例並不意味着它在計算上很難解決。例如，2SAT是SAT的特例，但具有線性時間解決方案。 – templatetypedef 2012-03-21 00:56:48
是的，如果半徑可以是無限的，那麼你只需要添加一個藍色方塊。如果半徑很小，那麼它也很容易計算。 – 2012-03-21 04:04:47
你的目標很模糊。是否有優先順序或效用函數？ – 2012-03-20 23:09:22
要求＃3可能很難，因爲它要求您證明沒有算法比找到的算法更快。 – Kaz 2012-03-20 23:11:36
我會使用邊界矩形的概念：包含所有紅色單元格的最小矩形區域。我懷疑該解決方案將具有覆蓋方塊在該邊界矩形內的屬性（前提是'n'能夠適合該矩形）。因爲沒有紅細胞可以覆蓋，所以在矩形外面橫行並沒有達到任何效果。你只會減少該廣場的潛在覆蓋面。 – Kaz 2012-03-20 23:14:18