| Two personification strategies for solving circles packing problem |
| |
| 作者姓名： | 黄文奇 许如初 |
| |
| 作者单位： | College of Computer Science，Huazhong University of Science and Technology，College of Computer Science，Huazhong University of Science and Technology Wuhan 430074，China，Laboratory of Computer Science，Institute of Software，Chinese Academy of Sciences，Beijing 100080，China，Wuhan 430074，China |
| |
| 基金项目： | Project supported by the 973 National Focus Program of China on Development of Fundamental Research, 863 National HighTech Programme of China, National Natural Science Foundation of China, and Chinese Science Foundation for National Doctoral Training. |
| |
| 摘 要： | Two personification strategies are presented, which yield a highly efficient and practical algorithm for solving one of the NP hard problems——circles packing problem on the basis of the quasi-physical algorithm. A very clever polynomial time complexity degree approximate algorithm for solving this problem has been reported by Dorit S.Hochbaum and Wolfgang Maass in J. ACM. Their algorithm is extremely thorough-going and of great theoretical significance. But, just as they pointed out, their algorithm is feasible only in conception and even for examples frequently encountered in everyday life and of small scale, it is the case more often than not that up to a million years would be needed to perform calculations with this algorithm. It is suggested toward the end of their paper that a heuristic algorithm of higher practical effectiveness should be sought out. A direct response to their suggestion is intented to provide.
|
Two personification strategies for solving circles packing problem |
| |
| Wenqi Huang,Ruchu Xu.Two personification strategies for solving circles packing problem[J].Science in China(Technological Sciences),1999,42(6):595-602. |
| |
| Authors: | Wenqi Huang Ruchu Xu |
| |
| Affiliation: | (1) College of Computer Science, Huazhong University of Science and Technology, 430074 Wuhan, China;(2) Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, 100080 Beijing, China;(3) College of Computer Science, Huazhong University of Science and Technology, 430074 Wuhan, China |
| |
| Abstract: | Two personification strategies are presented, which yield a highly efficient and practical algorithm for solving one of the NP hard problems-circles packing problem on the basis of the quasi-physical algorithm. A very clever polynomial time complexity degree approximate algorithm for solving this problem has been reported by Dorit S. Hochbaum and Wolfgang Maass in J. ACM. Their algorithm is extremely thorough-going and of great theoretical significance. But, just as they pointed out, their algorithm is feasible only in conception and even for examples frequently encountered in everyday life and of small scale, it is the case more often than not that up to a million years would be needed to perform calculations with this algorithm. It is suggested toward the end of their paper that a heuristic algorithm of higher practical effectiveness should be sought out. A direct response to their suggestion is intented to provide. |
| |
| Keywords: | packing problem NP hard heuristic algorithm personification method quasi-physical method |
| 本文献已被 CNKI SpringerLink 等数据库收录！ |
