Two personification strategies for solving circles packing problem
Two personification strategies for solving circles packing problem
复制标题
DOI：
10.1007/bf02916995
复制
发表时间：
1999-12
期刊：
影响因子：
--
通讯作者：
Wenqi Huang;Ruchu Xu
中科院分区：
文献类型：
--
作者：
Wenqi Huang;Ruchu Xu
在拟物算法的基础上，提出了两种拟人策略，并给出了求解NP难问题之一--圆装箱问题的高效实用算法。Dorit S. Hochbaum和Wolfgang Maass在J. ACM。他们的算法是非常彻底的，具有重要的理论意义。但是，正如他们指出的那样，他们的算法仅在概念上是可行的，即使对于日常生活中经常遇到的小规模的例子，情况往往是需要长达一百万年的时间来执行这种算法的计算。最后，作者建议应寻求一种实用性更高的启发式算法。对他们的建议的直接回应是为了提供。
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.