一个关于平面坐标系的最优化算法问题
本帖最后由 my788522 于 2011-11-30 14:50 编辑设平面上有一中心点 坐标可以是任何点位
此点位周边15米内有随机的黑点(已知xy坐标和黑点总数) 可能会出现在任何象限
此点位为圆心 5米为半径的圆内黑点忽略不计
5米到15米的这个圆环中 计划以5米为半径画灰色的圆圈 打算尽可能使用最少的圆圈 包含最多的黑点
算法应当尽量简洁 圆圈也不超过4个 剩下没有包括的应当是最不合适画圆包含的
我的目前设想是统计每个符合的黑点坐标 通过勾股定理计算所有其他黑点与其之间的距离 统计出此黑点距离5米内的黑点有多少
以此降序排列 选出最多的 以此黑点为圆心 5米为半径....
不过问题就在于如此算法肯定不符合最优化的原则 可导致包含的有局限性 因为只能以黑点为圆心
对人来说 很容易就可以模糊的判断出灰圈应该画在哪能包含最多的黑点 但程序如何算出呢
希望同学们能启发一下思维 能否有更优的算法 高深的东东，看了就头疼啊！ 不知道这个是在哪里的应用。如果是图像方面的可以考虑以每个点为圆心，5个单位为半径画圆，交集最多的区域就是需要的圆心所在地。 本帖最后由 netegg 于 2011-11-30 22:42 编辑
回复 3# afan
这是个优化组合的问题,一时之间想不出用处,但是在工作流程安排中很有用,对了,在单位化矩阵时也很有用 回复 4# netegg
我能想到的就是用在恐怖活动，如何用4个杀伤半径为5米的炸弹炸最多的人… 回复 5# afan
工具嘛,没有好坏之分,看什么人用了{:face (239):} 是游戏中对地面物品的判断拾取 优化跑腿的效率
A版说的也很正确 一样的 回复 3# afan
以每个点为圆心倒是很好处理 但这样就不能算作最优化了 会有一些遗漏
但人脑会很容易处理
如何以电脑模拟人脑的逻辑 这是个问题 回复 8# my788522
如果你这么说的话,就不是你那个题目了,变成定位取定半径的圆了,相对来说要简单
n个点,一共是(n-1)!个距离,算呗 A版的这个方法是计算所有的点为圆心的圆 包含最多的来排序对吧
这种方法会有遗漏的吧 圆只能排出三四个的 三角形画圆会吗(不好意思,我记不住了) 有点意思，慢慢琢磨下了·· 回复 10# afan
afan的方法可以适当优化，
第一步，利用afan的方法找出包含最多点的一个圆
第二步，不考虑上一步圆内包含的点（就如最内的那个圆内的点一样处理），在找出一个包含最多点的圆
循环第二步，一直到找出所有符合条件的圆
其实，没有实质性质的改变，只是稍微优化了下。治标不治本。哈哈 本帖最后由 netegg 于 2011-12-3 01:24 编辑
错了,不是(n-1)!,好像应该是n*(n-1)/2个距离值