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

• 作者: 何琨 黄文奇
• 来源期刊: 中国科学(信息科学)
• 学科: 工学
• 关键词: NP难度 三维Packing 拟人策略 动作空间 穴度
• 年，卷（期）: 2010,（12）
• 页码范围: 1586-1595
• 页数: 10页
• 分类号: TP301.6
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄文奇	华中科技大学计算机科学与技术学院	88	1090	21.0	27.0
2	何琨	华中科技大学计算机科学与技术学院	31	263	10.0	16.0