切割與布局問題的算法分類研究.pdf

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

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

3、問題類型。這樣，我們在面對新問題的時候，就可以根據(jù)這套系統(tǒng)對算法進行合理選擇或指導新算法的系統(tǒng)產生，克服手工設計新算法的缺點。 本文首先，對求解布局問題的文獻結構進行研究，找到各類求解文獻的共同點，提出算法分類系統(tǒng)的總體結構。其次，提出分類系統(tǒng)的各分類標準并對各分類標準進行細化，按照分位原則對代碼進行編寫建立起第一類編碼系統(tǒng)。再次，根據(jù)研究深度的不同，將算法分類系統(tǒng)進行分級建立起第二類編碼系統(tǒng)并給出編碼的文字表達形式；通過對典型