作者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