my788522 发表于 2011-11-30 14:48:24

一个关于平面坐标系的最优化算法问题

本帖最后由 my788522 于 2011-11-30 14:50 编辑



设平面上有一中心点 坐标可以是任何点位

此点位周边15米内有随机的黑点(已知xy坐标和黑点总数) 可能会出现在任何象限

此点位为圆心 5米为半径的圆内黑点忽略不计

5米到15米的这个圆环中 计划以5米为半径画灰色的圆圈 打算尽可能使用最少的圆圈 包含最多的黑点

算法应当尽量简洁 圆圈也不超过4个 剩下没有包括的应当是最不合适画圆包含的


我的目前设想是统计每个符合的黑点坐标 通过勾股定理计算所有其他黑点与其之间的距离 统计出此黑点距离5米内的黑点有多少
以此降序排列 选出最多的 以此黑点为圆心 5米为半径....

不过问题就在于如此算法肯定不符合最优化的原则 可导致包含的有局限性 因为只能以黑点为圆心
对人来说 很容易就可以模糊的判断出灰圈应该画在哪能包含最多的黑点 但程序如何算出呢

希望同学们能启发一下思维 能否有更优的算法

xms77 发表于 2011-11-30 20:54:16

高深的东东,看了就头疼啊!

afan 发表于 2011-11-30 21:52:39

不知道这个是在哪里的应用。如果是图像方面的可以考虑以每个点为圆心,5个单位为半径画圆,交集最多的区域就是需要的圆心所在地。

netegg 发表于 2011-11-30 22:40:59

本帖最后由 netegg 于 2011-11-30 22:42 编辑

回复 3# afan
这是个优化组合的问题,一时之间想不出用处,但是在工作流程安排中很有用,对了,在单位化矩阵时也很有用

afan 发表于 2011-11-30 22:46:47

回复 4# netegg


    我能想到的就是用在恐怖活动,如何用4个杀伤半径为5米的炸弹炸最多的人…

netegg 发表于 2011-11-30 22:48:29

回复 5# afan

工具嘛,没有好坏之分,看什么人用了{:face (239):}

my788522 发表于 2011-12-1 09:34:24

是游戏中对地面物品的判断拾取 优化跑腿的效率
A版说的也很正确 一样的

my788522 发表于 2011-12-1 09:36:29

回复 3# afan


   以每个点为圆心倒是很好处理 但这样就不能算作最优化了 会有一些遗漏
但人脑会很容易处理
如何以电脑模拟人脑的逻辑 这是个问题

netegg 发表于 2011-12-1 12:10:13

回复 8# my788522

如果你这么说的话,就不是你那个题目了,变成定位取定半径的圆了,相对来说要简单
n个点,一共是(n-1)!个距离,算呗

afan 发表于 2011-12-1 12:36:20

my788522 发表于 2011-12-1 20:32:46

A版的这个方法是计算所有的点为圆心的圆 包含最多的来排序对吧

这种方法会有遗漏的吧 圆只能排出三四个的

netegg 发表于 2011-12-2 00:54:52

三角形画圆会吗(不好意思,我记不住了)

jamer 发表于 2011-12-2 02:57:27

有点意思,慢慢琢磨下了··

jamer 发表于 2011-12-3 00:31:14

回复 10# afan
afan的方法可以适当优化,
第一步,利用afan的方法找出包含最多点的一个圆
第二步,不考虑上一步圆内包含的点(就如最内的那个圆内的点一样处理),在找出一个包含最多点的圆
循环第二步,一直到找出所有符合条件的圆

其实,没有实质性质的改变,只是稍微优化了下。治标不治本。哈哈

netegg 发表于 2011-12-3 01:21:31

本帖最后由 netegg 于 2011-12-3 01:24 编辑

错了,不是(n-1)!,好像应该是n*(n-1)/2个距离值
页: [1] 2 3
查看完整版本: 一个关于平面坐标系的最优化算法问题