1、布局問題是一種經(jīng)典的組合優(yōu)化問題，具有建模和求解上的雙重復(fù)雜性。自從該問題問世以來，就被應(yīng)用到許多工程領(lǐng)域，吸引了來自工程、數(shù)學(xué)、計(jì)算機(jī)等領(lǐng)域的學(xué)者對(duì)其進(jìn)行研究，并取得了大量成果。由于布局問題在求解上具有NP完全性，且布局問題本身種類繁多，因此出現(xiàn)了大量算法對(duì)其進(jìn)行研究和求解。 1990年Dyckhoff發(fā)表的布局問題分類法論文和2007年Gerhard Wascher等人發(fā)表的改進(jìn)的布局問題分類法論文都對(duì)布局問題的分類進(jìn)行了歸

2、類和編碼。他們都對(duì)紛繁復(fù)雜的C&P問題進(jìn)行了系統(tǒng)的組織和歸類，并各自得到了一套關(guān)于布局問題分類的編碼系統(tǒng)。這兩套編碼簡(jiǎn)單易懂，解決了C&P問題之間可參考性不足的問題，其影響力相當(dāng)大。 本文以近年出現(xiàn)的關(guān)于布局問題的文獻(xiàn)為基礎(chǔ)，研究這些文獻(xiàn)所應(yīng)用的算法、證明手段、達(dá)到的效果，把各種算法進(jìn)行歸類和總結(jié)，編制了針對(duì)布局問題求解算法的兩類代碼系統(tǒng)；同時(shí)，通過對(duì)典型文獻(xiàn)所使用的算法進(jìn)行研究和歸類，給出求解方法的發(fā)展趨勢(shì)和各種算法適合求解的

3、問題類型。這樣，我們?cè)诿鎸?duì)新問題的時(shí)候，就可以根據(jù)這套系統(tǒng)對(duì)算法進(jìn)行合理選擇或指導(dǎo)新算法的系統(tǒng)產(chǎn)生，克服手工設(shè)計(jì)新算法的缺點(diǎn)。 本文首先，對(duì)求解布局問題的文獻(xiàn)結(jié)構(gòu)進(jìn)行研究，找到各類求解文獻(xiàn)的共同點(diǎn)，提出算法分類系統(tǒng)的總體結(jié)構(gòu)。其次，提出分類系統(tǒng)的各分類標(biāo)準(zhǔn)并對(duì)各分類標(biāo)準(zhǔn)進(jìn)行細(xì)化，按照分位原則對(duì)代碼進(jìn)行編寫建立起第一類編碼系統(tǒng)。再次，根據(jù)研究深度的不同，將算法分類系統(tǒng)進(jìn)行分級(jí)建立起第二類編碼系統(tǒng)并給出編碼的文字表達(dá)形式；通過對(duì)典型