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

• 作者: 傅彦 刘景发 尚明生 陈端兵
• 来源期刊: 重庆邮电大学学报（自然科学版）
• 学科: 工学
• 关键词: 矩形packing NP完全 智能枚举算法 占角动作 穴度
• 年，卷（期）: 2008,（4）
• 所属期刊栏目: 计算机与自动控制
• 页码范围: 447-452
• 分类号: TP301.6
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	傅彦	电子科技大学计算机科学与工程学院	66	695	14.0	22.0
2	尚明生	电子科技大学计算机科学与工程学院	28	373	10.0	19.0
3	陈端兵	电子科技大学计算机科学与工程学院	23	221	8.0	14.0
4	刘景发	南京信息工程大学计算机与软件学院	21	45	4.0	6.0