布局問題NP難性質(zhì)的傳遞路線研究.pdf

1、布局問題作為研究NP難度問題的典型代表，在實踐領(lǐng)域中應(yīng)用較為廣泛。實際生產(chǎn)中，其表現(xiàn)出來的NP難性質(zhì)的求解性，已經(jīng)成為技術(shù)發(fā)展的瓶頸環(huán)節(jié)。當(dāng)前，計算機科學(xué)家和工程技術(shù)人員對NP難度問題的探索，還需要面對諸多挑戰(zhàn)。就目前的情況而言，對布局問題的研究主要是對其求解方法的研究，對布局問題復(fù)雜性研究的相對較少，但判別問題的復(fù)雜性是問題求解的基礎(chǔ)。本文對布局問題復(fù)雜性的傳遞路線進行研究，旨在厘清不同布局問題之間的復(fù)雜性傳遞關(guān)系，主要的研究內(nèi)容包括

2、:
　　(1)三類NP難性質(zhì)的布局問題劃分研究。首先是對布局問題NP難性質(zhì)的聲稱說法進行統(tǒng)計歸類;然后選擇基于問題難度劃界的分類策略，將布局問題分為已知NP難類、猜想NP難類和P類三類布局問題;最后針對三類問題實施不同的分類方案，得到比較合理的分類結(jié)果;
　　(2)托盤裝載問題歸結(jié)為NP難問題的證明嘗試。采用的證明思路是將頂點覆蓋問題多項式轉(zhuǎn)換為該問題，由于過程的復(fù)雜性，以失敗告終;但是由證明過程所啟發(fā)的求解方法（用頂點覆蓋

3、問題求解托盤問題）具有重要的意義，將該求解思路應(yīng)用到實際布局問題中，利用頂點覆蓋問題的方法求解實際直角邊下料問題，并取得較好的結(jié)果。
　　(3)不同布局文獻(xiàn)對布局問題NP難性質(zhì)的歸納。1）統(tǒng)計出證明（聲稱）不同布局問題復(fù)雜性的布局文獻(xiàn)，即一共有哪些文獻(xiàn)說明了其復(fù)雜性;2）不同布局問題的上一級布局文獻(xiàn);3）不同布局問題的下一級布局文獻(xiàn)。
　　(4)布局問題NP難證明中的歸結(jié)傳遞路線的梳理。參考W(a)scher等人對切割與布局

4、問題的六種基本問題類型，然后對不同布局問題NP難證明中的傳遞路線進行梳理，厘清不同布局問題之間的復(fù)雜性傳遞關(guān)系，建立布局問題復(fù)雜性歸結(jié)傳遞圖。
　　(5)布局問題難度判定系統(tǒng)的建立。布局問題難度判定系統(tǒng)包括布局問題分類查詢系統(tǒng)和布局問題復(fù)雜性判定兩個子系統(tǒng)，用戶可以實現(xiàn)布局問題分類類別的查詢和復(fù)雜性的判定。
　　本題的研究結(jié)果可以給研究布局問題的學(xué)者們在分類查詢和復(fù)雜性依據(jù)方面提供有價值的支持;同時從側(cè)面給工程技術(shù)人員在算法