※ 引述《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 ※ 编辑: hichcock 来自: 60.248.105.226 (06/22 11:42)