一种求解矩形块装填问题的拟人算法

计算机科学 ›› 2006, Vol. 33 ›› Issue (5): 234-237.

一种求解矩形块装填问题的拟人算法

陈端兵黄文奇

华中科技大学计算机科学与技术学院,武汉430074

出版日期:2018-11-17 发布日期:2018-11-17
基金资助:
国家自然科学基金资助项目10471051和973项目2004CB318000.

CHEN Duan-Bing, HUANG Wen-Qi （College of Computer Science, Huazhong University of Science and Technology, Wuhan 430074）

Online:2018-11-17 Published:2018-11-17

摘要/Abstract

摘要： 在货物装载、木材下料、超大规模集成电路（VLSI）设计等工作中提出了矩形块装填与切割问题，对这一问题，国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。本文利用人类的智慧和他们上万年以来形成的经验，提出了一种求解矩形块装填问题的拟人算法。谊算法使用了两个主要的思想策略，即矩形块选择策略和矩形块放置策略。用本文提出的算法，对21个测试算例进行了实算测试，测试结果表明：算法所得装填结果的优度高，计算时间短。对这21个测试算例。用本文算法计算，得到了其中16个算例的最优解，而计算时间都在

关键词: 矩形块装填切割,拟人算法,占角动作

Abstract: Rectangle packing/cutting problem is often raised in loading, timber cutting, Very Large Scale Integration （VLSI）design, and so on. For solving this problem, many algorithms such as simulated annealing, genetic algorithm, and other heuristic algorithms ha

Key words: Rectangle packing and cutting problem, Quasi-human heuristic, Corner-ocupying action

陈端兵黄文奇. 一种求解矩形块装填问题的拟人算法[J]. 计算机科学, 2006, 33(5): 234-237. https://doi.org/

CHEN Duan-Bing, HUANG Wen-Qi （College of Computer Science, Huazhong University of Science and Technology, Wuhan 430074）. [J]. Computer Science, 2006, 33(5): 234-237. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed