Two personification strategies for solving circles packing problem  

作　　者：黄文奇 许如初 

机构地区：[1]College of Computer Science, Huazhong University of Science and Technology [2]Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100080, China

出　　处：《Science China(Technological Sciences)》1999年第6期595-602,共8页中国科学（技术科学英文版）

基　　金：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 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 inJ. 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.

关 键 词：PACKING problem NP HARD HEURISTIC algorithm PERSONIFICATION METHOD quasi-physical method. 

分 类 号：O224[理学—运筹学与控制论]