求解長方體Packing問題的最大穴度算法.pdf

1、Packing問題大量地出現(xiàn)在機(jī)械制造、皮革服裝、造船、交通運(yùn)輸、航空航天、大規(guī)模集成電路的設(shè)計(jì)等諸多領(lǐng)域。求解Packing問題在科學(xué)研究和生產(chǎn)實(shí)踐中均有重要意義。典型的長方體Packing問題是在遠(yuǎn)洋運(yùn)輸、鐵路貨運(yùn)中常見的集裝箱裝載問題，該問題具有NP難度。求解NP難度問題一直是計(jì)算機(jī)科學(xué)技術(shù)中的瓶頸任務(wù)。自20世紀(jì)70年代以來的研究表明，很可能根本不存在求解此類問題的完整嚴(yán)格的有效算法。因此用啟發(fā)式算法求解成為當(dāng)前研究的一個(gè)熱點(diǎn)。

2、
　　 黃文奇教授提出了用一個(gè)擬人算法——最大穴度算法來解決長方體Packing問題。最大穴度算法已經(jīng)被黃教授應(yīng)用于求解二維的矩形Packing問題，并被證明對(duì)于解決矩形Packing問題是有效的。在此基礎(chǔ)上，黃教授把最大穴度算法從二維平面推廣到三維空間。作者詳細(xì)地介紹了該算法的思想起源、關(guān)鍵性定義(包括穴度、角區(qū)、占角動(dòng)作等)以及算法執(zhí)行步驟，最后用程序?qū)崿F(xiàn)了該算法。然后作者與黃教授一起針對(duì)該算法的一些不足作出了改進(jìn)，這些改進(jìn)