作者j100002ben (波卡Poka)
看板Prob_Solve
標題[請益] 超大集合中取符合規則的超小子集
時間Fri Jun 22 04:56:13 2012
標題下的很爛，可是我真的不知道要下什麼標題會比較好...
假設有一個矩形範圍（ex: 100cm*100cm），
裡面有非常多（ex:100000up）個隨機位置的圓形（ex:每個皆直徑10cm），
每一個圓形可能會和其他圓形相交/相割，
目標要找出矩形範圍內，最多不重疊的圓形
除了暴力解之外，我想不太出來我知道的演算法能夠處理這個問題
因為感覺像是排列組合（附帶檢查兩圓是否重疊）
一個矩形範圍不重複排滿頂多20-30個...
然後100000個就要檢查100000 * 99999 * ... * (100000-30)次
有沒有比較快速處理這種問題的方法？
比較是否重疊應該可以直接當成O(1)時間，
Ram夠大可以把全部的狀態放進去...
但是比較這麼多次也是很花時間的..
平行運算也有想過....
但是也要算法可以把資料切開來「平行」才行...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.168.233.250
※ 編輯: j100002ben 來自: 118.168.233.250 (06/22 04:56)
1F：推 EdisonX:比較那麼多次？ 06/22 05:20
2F：推 EdisonX:疑！是找最多「不重疊」，還是最多「不相切、相割」？ 06/22 05:27
3F：→ j100002ben:應該是說最多「互相]不相切也不相交的圓 06/22 05:31
4F：→ j100002ben:差一個等號www 06/22 05:32
5F：→ j100002ben:我說得比較那麼多次主要是說：先找一個，看看剩下符合 06/22 05:33
6F：→ j100002ben:的在找一個，遞迴跑20-30層進去（迴圈也可以XD） 06/22 05:34
7F：→ j100002ben:所以真的會跑很久.... 06/22 05:35
8F：推 fatalismo:座標為整數嗎？ 06/22 08:18
9F：推 LPH66:這問題可以轉換成 maximum independent set 問題 06/22 10:47
10F：→ LPH66:感覺不太妙... 06/22 10:47
11F：→ tkcn:greedy 要做出不錯結果應該不難，但要保證最佳解恐怕不容易 06/22 14:10
12F：→ j100002ben:座標是整數，因為擔心精確度問題.. 06/23 14:20
13F：→ j100002ben:Greedy應該不行，不然可能會再某個角落停住.. 06/23 14:21
14F：推 bigpigbigpig:可以考慮先把這100000個點用x,y座標排序，先比x再比y 06/24 13:30
15F：→ bigpigbigpig:這樣就只需要考慮一些小block附近的圓是否互相cover 06/24 13:31