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 v...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.展开更多
We excavate the wisdom from an old Chinese proverb ＂gold corner, silver side and strawy void＂, and further improve it into ＂maximum value in diamond cave＂ for solving the NP-hard cuboid packing problem. We extract...We excavate the wisdom from an old Chinese proverb ＂gold corner, silver side and strawy void＂, and further improve it into ＂maximum value in diamond cave＂ for solving the NP-hard cuboid packing problem. We extract, integrate and formalize the idea by west modern mathematical tools, and propose a pure quasi-human algorithm. The performance of the algorithm is evaluated on two sets of public benchmarks. For 100 strongly heterogeneous difficult benchmarks, experiments show an average packing utilization of 87.31%, which surpasses current best record reported in the literature by 1.83%. For 47 difficult benchmarks without orientation constraint, experiments show an average volume utilization of 92.05%, which improves current best record reported in the literature by 1.05%.展开更多
基金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.
基金Supported by the National Natural Science Foundation of China (Grant No. 60773194)the National Basic Research Program of China (GrantNo. 2004CB318000)Postdoctoral Science Foundation of China (Grant No. 20070420174)
文摘We excavate the wisdom from an old Chinese proverb ＂gold corner, silver side and strawy void＂, and further improve it into ＂maximum value in diamond cave＂ for solving the NP-hard cuboid packing problem. We extract, integrate and formalize the idea by west modern mathematical tools, and propose a pure quasi-human algorithm. The performance of the algorithm is evaluated on two sets of public benchmarks. For 100 strongly heterogeneous difficult benchmarks, experiments show an average packing utilization of 87.31%, which surpasses current best record reported in the literature by 1.83%. For 47 difficult benchmarks without orientation constraint, experiments show an average volume utilization of 92.05%, which improves current best record reported in the literature by 1.05%.
