一种求解矩形packing问题的智能枚举算法

作     者：陈端兵 刘景发 尚明生 傅彦 CHEN Duan-bing;LIU Jing-fa;SHANG Ming-sheng;FU Yan

作者机构：电子科技大学计算机科学与工程学院成都610054 南京信息工程大学计算机与软件学院南京210044 

基　　金：国家高技术研究发展计划(06AA01Z414,07AA01Z440) 国家242信息安全计划项目(2007B27) 四川省应用技术研究与开发项目支撑计划(2008GZ0009) 

出 版 物：《重庆邮电大学学报（自然科学版）》 (Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition))

年 卷 期：2008年第20卷第4期

页      码：447-452页

摘      要：矩形packing问题有许多工业应用,如码头货物装载,木材下料,超大规模集成电路(VLSI)布局设计,新闻排版等。国内外已提出了许多求解此问题的算法,如:遗传算法,模拟退火算法以及启发式算法等。在目前已有研究的基础上,提出了一种智能枚举算法,该算法的关键在于设计一种快速有效的枚举策略。用Hopper和Turton提出的21个矩形packing实例对所提出的算法性能进行了实算测试,平均面积未利用率为0.04%,平均计算时间为277.69 s,并求得了其中18个实例的最优解。实算结果表明:该算法对求解矩形packing问题是行之有效的。

主 题 词：矩形packing NP完全 智能枚举算法 占角动作 穴度 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

馆 藏 号：203417168...