→ ECZEMA :你所說的最大連通集合 是指連線的數目最大(edge最多) 11/18 23:17
→ ECZEMA :還是說經由線連在一起的點最多 11/18 23:17
→ ECZEMA :如果是後者的話 把已經連在一起的點視為新點可簡化問 11/18 23:18
→ ECZEMA :題 11/18 23:18
前幾天突然想到一個問題，不過我數學滿差的...
想不大出來，網路上也不知道要找什麼關鍵字 Orz
問題是這樣的
假設我一個平面上有一些點(假設是m個) 隨意分布
然後只要兩個點的距離小於x的話..當然x>0
就把兩個點連起來
這個步驟做完以後，應該會變成幾個connect set
或幾個零散的點散布在平面上
那如果我現在允許插入n個點
要怎麼放才能達到最大的連通集合@@?
還有我要怎麼樣才能在插入最少點的情況下，可以獲得最大的連通集合@@?
舉個例子好了 假設有A B C D E F G 這幾個點
{A,B} {C,D,E} {F} {G}
然後假設我插入H
使他變成{A,B,H,C,D,E} {F} {G} 使他connect的數目變多~
---------------------------------------------------------------------------
上面是我的問題，我自己想不到什麼好解法
只能想說把平面切成好幾個cell，用greedy的方式，一個一個cell把點放進去
看看效果怎樣...
然後一個一個慢慢加...
這樣好像沒什麼效率@_@||
所以想問問看有沒有什麼比較好的方法可以解決這個問題~~
在這裡問看看 謝謝各位
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.156.132