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

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

工具嘛,没有好坏之分,看什么人用了

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个距离值

		自动登录	找回密码
密码			加入

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

本帖子中包含更多资源

相关帖子

本帖子中包含更多资源