| 求解圆形packing问题的一个快速拟物算法 |
| |
| 引用本文： | 康雁,黄文奇.求解圆形packing问题的一个快速拟物算法[J].计算机工程与应用,2003,39(35):30-32. |
| |
| 作者姓名： | 康雁 黄文奇 |
| |
| 作者单位： | 1. 云南大学软件学院,昆明,650091
2. 华中科技大学计算机科学与技术学院,武汉,430074 |
| |
| 基金项目： | 国家973基础研究发展规划项目基金资助(编号:G1998030600) |
| |
| 摘 要： | 求解NP难问题一直是计算机科学技术中的一个瓶颈任务。自20世纪70年代以来的研究表明,不存在求解此类问题的完整严格的有效算法。因此用启发式方法求解成为当今研究的一个热点。圆形packing问题是一个有着很高理论和实用价值的NP难问题。该文提出了一些有效的搜索策略,得到了一个求解它的快速有效启发式算法。最后用计算实例验证了此算法的有效性,计算结果表明此算法明显优于已有快速算法。
|
| 关 键 词： | 圆形Packing问题 拟物方法 NP难度 启发式方法 |
| 文章编号： | 1002-8331-(2003)35-0030-03 |
| 修稿时间： | 2003年10月1日 |
A Fast Quasi-physical Algorithm for the Disks Packing Problem |
| |
| Kang Yan,Huang Wenqi.A Fast Quasi-physical Algorithm for the Disks Packing Problem[J].Computer Engineering and Applications,2003,39(35):30-32. |
| |
| Authors: | Kang Yan Huang Wenqi |
| |
| Affiliation: | Kang Yan 1 Huang Wenqi 21 |
| |
| Abstract: | Solving NP hard problems is always the bottleneck task for computer science and techniques.Investigations from the1970s to now show that there does not exist an exactly effective algorithm that can provide an optimal solu-tion for NP-hard problems within a reasonable time limit.In recent years,people turn to obtain heuristic methods for solving NP hard problems.The disks packing problem is of high theoretical and practical value.In this paper,a fast heuristic method is presented by using efficient search strategies.A lot of computational experiments demonstrate the ef-fectiveness of this algorithm. |
| |
| Keywords: | The disks packing problem Quasi-physical method NP-hard problem Heuristic methods |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
