求解长方体Packing问题的纯粹拟人算法  

作　　者：黄文奇[1] 何琨[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《中国科学（F辑:信息科学）》2009年第6期617-622,共6页

基　　金：国家自然科学基金(批准号:60773194);国家重点基础研究发展计划(批准号:2004CB318000);中国博士后科学基金(批准号:20070420174)资助项目

摘　　要：对于具有NP难度的长方体Packing问题,挖掘出了中国古代谚语"金角银边草肚皮"中隐藏的智慧,并进一步发展出新子句"价值最高钻石穴".在利用现代西方的先进数学工具经过确切化、完整化与形式化后,得出了一种纯粹拟人型的求解算法.试算了国际上公开通行的两组有代表性的算例(benchmark).对于100个强异构型的困难算例,所得布局图案达到了87.31%的平均空间利用率,刷新了当今国际上的最好纪录,将它提高了1.83个百分点.对于47个无方向约束的困难算例,得到了92.05%的平均空间利用率,将当今国际上的最好纪录提高了1.05个百分点.

关 键 词：PACKING问题 NP难度 启发式算法 拟人方法 穴度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]