求解二維矩形packing問題的高效算法設計.pdf

1、研究了二維矩形packing這一類NP難度問題。在黃文奇等人提出的擬人型穴度算法的基礎之上,提出了基于動作空間的擬人型穴度算法,通過定義動作空間來簡化對不同放入動作的評價,使穴度的計算時間明顯縮短,從而使算法既繼承了原有穴度算法的優(yōu)勢,又能夠快速地得到面積利用率較高的布局圖案。
　　重點研究了二維矩形裝填問題,給出了格局、動作空間、占角動作、平整度、評價標準和比較策略的定義?；趧幼骺臻g,簡化了對不同放入動作的評價,明顯縮短了計算

2、時間。在算法的設計中,著重考慮了如何分割矩形框內(nèi)的剩余空間使放入塊與周圍的已放入塊更緊密、采用哪種數(shù)據(jù)結(jié)構(gòu)使得剩余空間的更新更快捷、如何選取一個唯一的占角動作使之遵循“可持續(xù)發(fā)展的路線”、選取哪種搜索策略可以使結(jié)果不斷趨近全局最優(yōu)解而不至于陷入局部最小值的陷阱。
　　進一步地,將此算法適當調(diào)整以求解二維strip packing問題和二維矩形packing價值優(yōu)化問題。針對二維strip packing問題的特點,結(jié)合了加1法和二

3、分法以求解已知矩形敞口框的最優(yōu)高度和未知矩形敞口框的最優(yōu)高度的兩類子問題。針對二維矩形packing價值優(yōu)化問題的特點,修改了占角動作的比較策略,加入了放入塊的單位價值作為比較因子,并將目標函數(shù)調(diào)整為所有放入塊的總價值。
　　對二維矩形裝填問題、二維strip packing問題和二維矩形packing價值優(yōu)化問題,試算了國際上著名的相關算例。所提出的算法均能在較短的時間內(nèi)得到較優(yōu)的結(jié)果。對二維矩形裝填問題,在Hopper和Tur