三维矩形Packing问题的拟人求解算法  

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

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

出　　处：《中国科学：信息科学》2010年第12期1586-1595,共10页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:60773194)资助项目

摘　　要：基于当前格局下可能填充的最大矩形空间的概念以及围城战术,将求解三维矩形Packing这一典型NP难度问题的拟人型穴度算法做了关键性的改进,得到了新的更强有力的算法ICDA.在时间开销与当今代表性算法大致相当的前提下,ICDA对于国际上公开的由100个实例组成的天然的最困难的问题类,即待放长方体的形状大小随机给定、几乎两两皆不相同的情形,得到了90.92%的平均空间利用率.所得精度比国际学术界最新公开发表的同时也是迄今为止最好的结果要高出0.54个百分点.

关 键 词：NP难度 三维Packing 拟人策略 动作空间 穴度 

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