不等圆 packing 问题(拟人拟物法)

不等圆packing拟物拟人问题简单而言是在一个大圆中放置(packing)若干(M)个小园问题,通过拟物和拟人的方法寻找、优化找到这样的放置(packing)问题的方法。

拟物设想这M 个pans被挤缩在这个大圆中,由于各个物体由于挤压都有要恢复自己形状大小的趋势,它们之间产生了挤压弹性力的相互作用. 在这种挤压弹性力的驱使之下,各物体会产生一系列的运动. 作为这种运动的结果,可能就是问题的解的确立———各物体到达某种相互合适的位置,两两互不嵌入.而拟物会有一种“局部最小点问题”,即拟物求解会在极小点处停止,而这时并不是系统的最优解,拟人法相应的产生就是为了解决这样的“陷阱”,人为的在极小点状态下取出一个pan,随机放置到另一个地方(这样就走出了极小点),好像计算机“人为地”取一个盘摆脱这样的困境,这就是我理解的拟物拟人吧.

How many pans do you want to input in the circle!
【输入你想在大圆中输入多少个pans】
input the radius of the circle
【输入大圆的半径(其余的pans都放在这里面)】
input the radius of pans
【输入小圆的半径(放到大圆里的小圆半径)】
【输入格式: 浮点数/整数+回车】
the biggest pan‘s radius =【最大小圆的半径】
do you want to input the locations of pans? yes please press ’y‘
【如果自己想输入初始状态的话请press ’y‘,在小盘多的情况下不建议使用,但是给出好的初态,程序解决的会快很多

废话少说上图

123

程序下载

其实这个问题在之后我也考虑过,对于更复杂的情况,程序采用的策略就不是很合适了,主要的问题有几个:

  1. 下降梯度 h 下降的比较慢,程序中 h=0.9*h ,这样下降到极值点的速度就很慢了,但是 h 下降的太快,有可能没有到极值点就跳跃出来,这点可以通过改进参数优化。
  2. 没有实现把圆放到空缺最大的地方,后面我继续实现了将范围 x 从 –R 到 +R 范围内以间隔为 step 分割线分割,测试每个点,找到最大的空缺,将最拥挤的圆放到空缺中。
  3. 每次在极值点没有找到答案的话,总是把最拥挤的那个圆移动,这个策略有个问题就是可能把最大的圆移动了,这样就很有可能把之前行成的好的格局给破坏了。
  4. 结合2、3点,如果实现了找到最大空缺,选择最拥挤的是最大的圆放入可能有 3 问题,如果最拥挤的圆是小于空缺的圆的话也是个错误的选择,所以选取的圆:一、必须是拥挤的(如果不拥挤的圆选择了过去,可能破坏了之前的一些好的格局);二、必须是比空缺大的,如果将比空缺小得圆放了进去,可能浪费了大的空间并且很难把这个错误的小圆再次通过策略换出来。

这个问题像的复杂了就有点像人工智能的问题了,什么A*算法之类的啦。

写完以上的内容突然发现个很有意思的想法,如果每次都把最大的圆放到空隙最大的地方不都解决了么?哈哈,最简单描述的策略啊

ps:2012年1月3日更新:再议不等圆 packing 问题

不等圆 packing 问题(拟人拟物法)》上有2条评论

回复 mark 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据