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

my788522 · 发表于 2011-12-3 22:03:15

Func getyuan($infos)
Local $fanhui[29][3]
For $i = 1 To 29
$yuange = 0
$xiaxia = ""
$zuobiao = $infos[$i]
If $zuobiao <> "" And StringInStr($zuobiao, ",") Then
For $i2 = 1 To 29
If $i2 = $i Then ContinueLoop
If $infos[$i2] <> "" And StringInStr($infos[$i2], ",") Then
If farxy($zuobiao, $infos[$i2]) <= 5 Then
$yuange = $yuange + 1
$xiaxia = $xiaxia & "/" & $infos[$i2]
EndIf
EndIf
Next
$fanhui[$i][1] = $zuobiao
$fanhui[$i][0] = $yuange
$fanhui[$i][2] = $xiaxia
EndIf
Next
_ArraySort($fanhui, 1, 0, 0, 0)
$del = ""
For $i = 0 To 20
$zuobiao = $fanhui[$i][1]
$zuobiao2 = $fanhui[$i][2]
If $zuobiao <> "" And $fanhui[$i + 1][1] <> "" Then
;MsgBox(0, $zuobiao, $fanhui[$i2][1])
If StringInStr($zuobiao2, $fanhui[$i + 1][1]) Then
$del = $del & "," & $i
_ArrayDelete($fanhui, $i + 1)
$i = $i - 1
If $i < 0 Then
$i = 0
EndIf
EndIf
EndIf
Next

Return $fanhui
EndFunc
Func farxy($xy1, $xy2)
$xxyy1 = StringSplit($xy1, ",")
$xxyy2 = StringSplit($xy2, ",")
$x1 = $xxyy1[1]
$y1 = $xxyy1[2]
$x2 = $xxyy2[1]
$y2 = $xxyy2[2]
Return Abs(Sqrt(($x1 - $x2) * ($x1 - $x2) + ($y1 - $y2) * ($y1 - $y2)))
EndFunc ;==>farxy

目前我只是根据各点为圆心
传入的是一个包含各点坐标的数组
建立2维数组计算每个点为圆心 5米为半径的圆中包含的各点坐标以及包含的点个数
将2维数组按点个数排序
处理前者对后者的包含删除被包含的点

jamer · 发表于 2011-12-3 23:18:04

本帖最后由 jamer 于 2011-12-3 23:34 编辑

afan的那个方法还是有些弊端,例如所找到的包含最多点的圆可能还是没有尽可能包含最多，毕竟它的圆心是固定的，会舍弃掉紧挨着圆外的点
又琢磨的一个新方法：
以每个点为圆心，5为半径做圆。这些个圆会将圆环分割成许多个小区域。我们可以知道，如果以某个点为圆心的圆包括这个小区域，那么以这个区域任一点为圆心，5为半径的圆就能包括原先那个圆心点。
所以找到被最多圆覆盖的小块区域，以其内任一点为圆心做圆，那么最后这个圆肯定是能包含最多的点。
然后不考虑这个圆内包含的点，重复以上步骤，依次寻找包含最多点的圆，一直到限制的四个圆都找到或者所有的点都被包括了为止
优点：每次找到的圆都是当前情况下所能包含点最多的一个圆。所以最后找到的四个圆几乎是能包括最多的点
缺点：1.道理上说，小区域内任一点为圆心都行，所以可以用随机数字，或者某一种固定方法（如，最高点坐在直线上的中点等）
2.算法实现比较困难。方法只是道理上能实现，如果用算法会比较复杂，看看有没有有其他优化的办法了。或者把整个圆环分割成N*N网格，网络的密度要能保证每个小区域内都有一个完整的网格存在，网格的方法可以较方便的以网格的中心为圆心，解决上一个缺点。兼可采用人工的方法。去选择合适的网格和圆心。
3.一个致命的缺点。虽然每次都能保证得到包含点最多的圆，但是没有考虑圆与圆间的耦合性。所以最终得到的几个圆可能不是最优解。

netegg · 发表于 2011-12-3 23:20:13

回复 17# jamer
明显不能用每个点为圆心做圆,起码是三个点,否则不能保证点数最大

魔导 · 发表于 2011-12-3 23:20:14

本拉登2代

jamer · 发表于 2011-12-3 23:31:12

本帖最后由 jamer 于 2011-12-3 23:38 编辑

回复 18# netegg

可以的，你可以按照我说的方法去画图试验一下。
和用三点作图不是同一种思路。

回复 19# 魔导
这个可以用于以下
用最少的信号发射机覆盖最多的信号需求源
用最少的浇灌设备覆盖最多的果树
等方面吧。
哈哈

netegg · 发表于 2011-12-3 23:46:08

本帖最后由 netegg 于 2011-12-3 23:48 编辑

回复 20# jamer

不用试,想想就知道,简单说,先以两个点为例,如果两个点的距离恰好大于定值,必须以两个点为圆心画两个圆,如果以两点连线的中点画圆,一个就够了

jamer · 发表于 2011-12-3 23:56:44

回复 21# netegg

看来你是没有读完我写的东西。
以两点为例，各以其为圆心做两个圆，如果这两个点的距离小于10，则这两个圆肯定有个相交的小区域。那么以这个小区域任意一点为圆心做圆，那么肯定能把原两个点包含在内。
更多点的也是依次类推的。原理就是这样。

netegg · 发表于 2011-12-4 00:00:15

回复 22# jamer
既然你知道这个,不是很简单吗,就是三角形画圆的事呀

jamer · 发表于 2011-12-4 00:09:10

回复 23# netegg

三角形画圆是什么意思？
三点画圆的意思？
三点确定一个圆，那这个圆的半径呢？不考虑了
确实能保证这三点能在这个圆内，更多的点怎么保证？或者你后面的怎么处理

刚才又仔细研究了下Afan的画法，就是我刚才说明的那个方法。
不过之前没有看懂，也被楼主的解释给带到沟里了，呵呵。

netegg · 发表于 2011-12-4 03:07:03

本帖最后由 netegg 于 2011-12-4 03:12 编辑

afan那个也是画圆但是具体做法我也没明白,圆半径可以从三个边导出来,通过欧拉定理和圆面积公式可以导出圆半径,也就是说,不是从圆找点,而是从点找圆
n个点,随便取三个,有三条的边的边长,只要这个圆的半径小于定值,则符合要求,圆心同时确定,找出根据这个圆心以给定半径的圆内的所有匹配点(也就是到这个圆心的所有距离小于给定半径的点),然后再根据圆外的点同样方法继续

jamer · 发表于 2011-12-4 12:25:41

回复 25# netegg

你也许确实找到了至少包含三个点一个圆，但你如何保证这个圆包含的点最多？
如果只是找到包含3个或以上点的圆，方法有很多了，但是和题目无关啊。

rolaka · 发表于 2011-12-4 12:45:10

凑个热闹, 可以考虑四叉树...

netegg · 发表于 2011-12-4 14:59:33

回复 26# jamer
你到底是要最少的圆还是要最多的点

kn007 · 发表于 2011-12-4 15:14:56

Mark

jamer · 发表于 2011-12-4 20:07:50

回复 28# netegg

题目中已经提到了“尽可能少得圆包含尽可能多的点”
我的目的就是每次找到当前情况下能包含最多点的圆。

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

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