求解长方体Packing问题的高效算法

摘要：

对典型的NP难度问题--著名的长方体Packing问题,通过观察体会人类几千年来在砌石头下围棋等活动中形成的经验和智慧,受到谚语”金角银边草肚皮”的启发,并将它发展提高到”价值最高钻石穴”,提出了一种最大穴度的占角动作优先处理的拟人算法.计算了Loh和Nee提出的15个代表性的算例,算法在合理的时间内得出了高空间利用率的布局,其精度达到了国际先进的纪录。

关键词： NP难度 长方体Packing问题 启发式 拟人算法 最大穴度

作者: 何琨 黄文奇

作者单位: 华中科技大学计算机科学与技术学院,武汉,430074

会议类型: 国内会议

会议名称: 2007全国理论计算机科学学术年会

会议地点: 南宁

会议语种:中文

页码: 7-10

在线出版日期: 2007-11-01（万方平台首次上网日期，不代表论文的发表时间）