PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [請益]超大集合中取符合規則的超小子集

看板Prob_Solve (計算數學 Problem Solving)作者hichcock (快樂一整年 ^^~~~)時間12年前 (2012/06/22 11:26)推噓0(0推 0噓 1→)

留言1則, 1人參與討論串2/2 (看更多)

※ 引述《j100002ben (波卡Poka)》之銘言： : 標題下的很爛，可是我真的不知道要下什麼標題會比較好... : 假設有一個矩形範圍（ex: 100cm*100cm）， : 裡面有非常多（ex:100000up）個隨機位置的圓形（ex:每個皆直徑10cm）， : 每一個圓形可能會和其他圓形相交/相割， : 目標要找出矩形範圍內，最多不重疊的圓形 : 除了暴力解之外，我想不太出來我知道的演算法能夠處理這個問題 : 因為感覺像是排列組合（附帶檢查兩圓是否重疊） : 一個矩形範圍不重複排滿頂多20-30個... : 然後100000個就要檢查100000 * 99999 * ... * (100000-30)次 : 有沒有比較快速處理這種問題的方法？ : 比較是否重疊應該可以直接當成O(1)時間， : Ram夠大可以把全部的狀態放進去... : 但是比較這麼多次也是很花時間的.. : 平行運算也有想過.... : 但是也要算法可以把資料切開來「平行」才行... 反過來想...用刪去法...先將所有點列入清單內找矩形範圍內的任一點...找出其半徑範圍x2內的點 (包含切 + 重疊) 將這些點從清單內刪除...再找這些點的半徑範圍x2內的點遞迴方式刪除掉大部分清單內重複的點反覆執行直到每個點都執行過上述動作就可以確定剩下的都是獨立的因為清單內的點越來越少, 所以速度相對應該比較快吧目前想到比較容易寫成程式的方式是這個 -- 只有現在能做到的事很多很多不要忽略眼前而一昧的考慮以後的事如果總是那樣的話到什麼時候也不會有所作為的 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 60.248.105.226