求解圆形packing问题的启发式方法
文献类型：学位论文
| 作者 | 康雁 |
| 学位类别 | 博士 |
| 答辩日期 | 2002 |
| 授予单位 | 中国科学院软件研究所 |
| 授予地点 | 中国科学院软件研究所 |
| 关键词 | 启发式方法 拟物拟人法 圆形packing问题 计算复杂性 |
| 其他题名 | The Heuristic Methods for the Disks Packing Problem |
| 学位专业 | 计算机软件与理论 |
| 中文摘要 | 我们提出了有效地近似求解具有NP难度的圆形packing问题的启发式方法.该文所做的工作主要有:第一,得出了一个高效地近似求解圆形packing问题的快速拟物拟人算法.此算法比之于前人所得的最好算法,其效能有了显著的提高.对于困难的问题实例,在保持优度相等的前提下,其速度大致提高了10~100倍.第二,受物理世界中弹性物体运动规律的启发,得到了一个预测搜索前景的策略,它通过及早地终止将会陷入局部极小值陷阱的搜索,提高了搜索的效率;受自然界中优胜劣汰规律的启发得出另一个策略,它通过很好地利用人类在社会活动中积累的智慧,使搜索逃离局部极小值的陷阱,并走向更有前途的方向.结合这两个启发式策略以及拟物拟人法得到了快速拟物拟人算法.第三,在模拟物理世界中弹性物体运动的基础上,借鉴模拟退火法的思想,得出了二个启发式方法.这两个方法通过在搜索过程中以不同的规则接受不优于当前解的新解,使搜索有可能逃离局部极小值陷阱,从而有效地求解了等圆packing问题.第四,在用各启发式方法有效地求解大量实例的基础上,研究了启发式方法的工作原理,提出了设计启发式方法的可行的方案. |
| 语种 | 中文 |
| 公开日期 | 2011-03-17 |
| 页码 | 96 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/7472]  |
| 专题 | 软件研究所_中科院软件所_中科院软件所 |
| 推荐引用方式 GB/T 7714 | 康雁. 求解圆形packing问题的启发式方法[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2002. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。