確定至少需要放置多少個節點，才能覆蓋95%以上的區域？

01-11

在一個監視區域為邊長b=100(長度單位)的正方形中，每個節點的覆蓋半徑均為r=10(長度單位)。在設計感測網路時，需要知道對給定監視區域在一定的覆蓋保證下應放置節點的最少數量。對於上述給定的監視區域及覆蓋半徑，確定至少需要放置多少個節點，才能覆蓋95%以上的區域？

這是一個非常經典的circle packing問題，一直沒想過還有這樣的變形，但是覺得還挺有實際意義的。理論下限是33。

circle packing原始問題是在一個平面里堆一樣大小的圓，怎麼堆能覆蓋率最大，圓之間不能有重合。各種亂排可以如下面的左圖，也可以如右圖。

著名的拉格朗日1773年就證明了右圖的排法是最高效的排法[1]，

換成六邊形的範圍來理解，這樣的結構可以無限延伸，所以用這種方法的覆蓋率是，

$eta_h = frac{pi}{2sqrt3} approx 0.9069$

顯然如果沒有重合，這種牛逼的排法，還是無法達到95%的要求。

接下來就必須要有重合了。

重合可以這樣，這是當兩個圓重合部分最寬的地方等於 0.28*r 時。六邊形內的覆蓋率為100%，r為小圓的半徑。

也可以這樣，這是當兩個圓重合部分最寬的地方等於0.08*r 時，這樣的覆蓋率是 0.9559。

如果面積非常大，不需要考慮邊界問題的話，只需要這樣一直堆六邊形就可以無限堆下去了，

平均下來，需要3個圓來覆蓋這樣一個六邊形。六邊形的半徑是 1.92 * r, 因此六邊形的面積為： $area = frac{3sqrt3}{2} imes (1.92r)^2$

需要圓的個數是 $frac{total\_area}{area} imes 3$

r=10時， area ＝ 957.75，邊長為100的正方形面積10^4, 需要10.44個六邊形，也就是11個六邊形.

這樣需要圓個數的下限是：33個。因為邊界處利用率較低，實際數字要大於等於33。

代碼在 http://nbviewer.ipython.org/gist/haojian/2d87265d014c3a4199e3

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

當考慮邊界問題的時候，兩個圓重合部分最寬的地方等於0.08*半徑不一定是最優解，因為邊緣地區用這樣的六邊形來填充不怎麼實惠。

呃。。。考慮邊界的代碼還沒寫完。。

點間距約18.7,共36個點，覆蓋率95.35。不會算，在CAD里試出來的。

不過呢，我覺得95太苛刻了，我找到一個解法，33個點可以覆蓋超過94%。

------------------------------

35個，95.5。

--------------------------------------------------

順便說一下，是 @王希提示了我，如果3列6點+3列5點，就可以做到33個點覆蓋94%，然後我手工隨便加了兩個圓，剛好到了95%。

我是窮舉試出來的，腳本可以幫助我即時獲得面積比，所以試的效率其實蠻高的。

謝邀。

我來拋個磚，吸引大神來回答。

理論上來說，一個節點能覆蓋的區域最多是 $100pi$ ，所以，要覆蓋邊長為100的正方形的95%以上的區域，至少需要的： $N=frac{100 imes 100 imes 0.95}{100pi }approx 30.24$ 個節點，也就是31個節點。

但是，用圓來填滿平面顯然有點困難，所以我估計用 31 個節點覆蓋 95% 以上的區域應該是做不到的，實際上，如果有 35 以下的解我會感到驚訝。

現在我只能證明 N 不超過 39，方案如下圖所示：

此時覆蓋的區域達到 95.87%跪求大神把 N 的上限降下來。

寫個智能粒子群演算法算一下就有了。

當年幫老闆寫教材用得就是這個經典問題。

剛剛算了很長時間，忍不住看了前幾個大神，不敢放過程了，，，不知道科學計算器行不行，，，在自學，，，

在IEEE庫里，用WSN和coverage作關鍵詞，就能搜到你要的答案。