求解二維矩形packing問(wèn)題的高效算法設(shè)計(jì).pdf

1、研究了二維矩形packing這一類(lèi)NP難度問(wèn)題。在黃文奇等人提出的擬人型穴度算法的基礎(chǔ)之上,提出了基于動(dòng)作空間的擬人型穴度算法,通過(guò)定義動(dòng)作空間來(lái)簡(jiǎn)化對(duì)不同放入動(dòng)作的評(píng)價(jià),使穴度的計(jì)算時(shí)間明顯縮短,從而使算法既繼承了原有穴度算法的優(yōu)勢(shì),又能夠快速地得到面積利用率較高的布局圖案。
　　重點(diǎn)研究了二維矩形裝填問(wèn)題,給出了格局、動(dòng)作空間、占角動(dòng)作、平整度、評(píng)價(jià)標(biāo)準(zhǔn)和比較策略的定義?；趧?dòng)作空間,簡(jiǎn)化了對(duì)不同放入動(dòng)作的評(píng)價(jià),明顯縮短了計(jì)算

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

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