重庆邮电大学学报（自然科学版）
重慶郵電大學學報（自然科學版）
중경유전대학학보（자연과학판）
JOURNAL OF CHONGQING UNIVERSITY OF POSTS AND TELECOMMUNICATIONS(NATURAL SCIENCE EDITION)
2008年
4期
447-452
,共6页
陈端兵%刘景发%尚明生%傅彦
陳耑兵%劉景髮%尚明生%傅彥
진단병%류경발%상명생%부언
矩形packing%NP完全%智能枚举算法%占角动作%穴度
矩形packing%NP完全%智能枚舉算法%佔角動作%穴度
구형packing%NP완전%지능매거산법%점각동작%혈도
矩形packing问题有许多工业应用,如码头货物装载,木材下料,超大规模集成电路(VLSI)布局设计,新闻排版等.国内外已提出了许多求解此问题的算法,如:遗传算法,模拟退火算法以及启发式算法等.在目前已有研究的基础上,提出了一种智能枚举算法,该算法的关键在于设计一种快速有效的枚举策略.用Hopper和Turton提出的21个矩形packing实例对所提出的算法性能进行了实算测试,平均面积未利用率为0.04%,平均计算时间为277.69s,并求得了其中18个实例的最优解.实算结果表明:该算法对求解矩形packing问题是行之有效的.
矩形packing問題有許多工業應用,如碼頭貨物裝載,木材下料,超大規模集成電路(VLSI)佈跼設計,新聞排版等.國內外已提齣瞭許多求解此問題的算法,如:遺傳算法,模擬退火算法以及啟髮式算法等.在目前已有研究的基礎上,提齣瞭一種智能枚舉算法,該算法的關鍵在于設計一種快速有效的枚舉策略.用Hopper和Turton提齣的21箇矩形packing實例對所提齣的算法性能進行瞭實算測試,平均麵積未利用率為0.04%,平均計算時間為277.69s,併求得瞭其中18箇實例的最優解.實算結果錶明:該算法對求解矩形packing問題是行之有效的.
구형packing문제유허다공업응용,여마두화물장재,목재하료,초대규모집성전로(VLSI)포국설계,신문배판등.국내외이제출료허다구해차문제적산법,여:유전산법,모의퇴화산법이급계발식산법등.재목전이유연구적기출상,제출료일충지능매거산법,해산법적관건재우설계일충쾌속유효적매거책략.용Hopper화Turton제출적21개구형packing실례대소제출적산법성능진행료실산측시,평균면적미이용솔위0.04%,평균계산시간위277.69s,병구득료기중18개실례적최우해.실산결과표명:해산법대구해구형packing문제시행지유효적.
