[請益]超大集合中取符合規則的超小子集
看板Prob_Solve (計算數學 Problem Solving)作者j100002ben (波卡Poka)時間12年前 (2012/06/22 04:56)推噓5(5推 0噓 10→)留言15則, 6人參與討論串1/2 (看更多)
標題下的很爛，可是我真的不知道要下什麼標題會比較好...
假設有一個矩形範圍（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)
推
06/22 05:20, , 1F
06/22 05:20, 1F
推
06/22 05:27, , 2F
06/22 05:27, 2F
→
06/22 05:31, , 3F
06/22 05:31, 3F
→
06/22 05:32, , 4F
06/22 05:32, 4F
→
06/22 05:33, , 5F
06/22 05:33, 5F
→
06/22 05:34, , 6F
06/22 05:34, 6F
→
06/22 05:35, , 7F
06/22 05:35, 7F
推
06/22 08:18, , 8F
06/22 08:18, 8F
推
06/22 10:47, , 9F
06/22 10:47, 9F
→
06/22 10:47, , 10F
06/22 10:47, 10F
→
06/22 14:10, , 11F
06/22 14:10, 11F
→
06/23 14:20, , 12F
06/23 14:20, 12F
→
06/23 14:21, , 13F
06/23 14:21, 13F
推
06/24 13:30, , 14F
06/24 13:30, 14F
→
06/24 13:31, , 15F
06/24 13:31, 15F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
