本文關(guān)鍵詞：布局問題NP難性質(zhì)的傳遞路線研究

  更多相關(guān)文章： 布局問題 復(fù)雜性 NP難 NP完全

【摘要】：布局問題作為研究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)容包括：(1)三類NP難性質(zhì)的布局問題劃分研究。首先是對布局問題NP難性質(zhì)的聲稱說法進行統(tǒng)計歸類;然后選擇基于問題難度劃界的分類策略,將布局問題分為已知NP難類、猜想NP難類和P類三類布局問題；最后針對三類問題實施不同的分類方案,得到比較合理的分類結(jié)果；(2)托盤裝載問題歸結(jié)為NP難問題的證明嘗試。采用的證明思路是將頂點覆蓋問題多項式轉(zhuǎn)換為該問題,由于過程的復(fù)雜性,以失敗告終；但是由證明過程所啟發(fā)的求解方法(用頂點覆蓋問題求解托盤問題)具有重要的意義,將該求解思路應(yīng)用到實際布局問題中,利用頂點覆蓋問題的方法求解實際直角邊下料問題,并取得較好的結(jié)果。(3)不同布局文獻對布局問題NP難性質(zhì)的歸納。1)統(tǒng)計出證明(聲稱)不同布局問題復(fù)雜性的布局文獻,即一共有哪些文獻說明了其復(fù)雜性；2)不同布局問題的上一級布局文獻；3)不同布局問題的下一級布局文獻。(4)布局問題NP難證明中的歸結(jié)傳遞路線的梳理。參考Wascher等人對切割與布局問題的六種基本問題類型,然后對不同布局問題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ù)人員在算法大類的選擇和設(shè)計上給予輔助。
【關(guān)鍵詞】：布局問題 復(fù)雜性 NP難 NP完全
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TB115
【目錄】：

• 致謝5-6
• 摘要6-7
• ABSTRACT7-12
• 1 引言12-24
• 1.1 研究背景和意義12-14
• 1.1.1 研究背景12
• 1.1.2 研究意義12-14
• 1.2 布局問題概述14-18
• 1.2.1 布局問題的定義14-15
• 1.2.2 布局問題的復(fù)雜性15-16
• 1.2.3 布局問題的求解方法16-18
• 1.3 國內(nèi)外研究現(xiàn)狀18-19
• 1.4 研究內(nèi)容19-21
• 1.4.1 主要研究內(nèi)容19-20
• 1.4.2 論文章節(jié)結(jié)構(gòu)20-21
• 1.5 本章小結(jié)21-24
• 2 布局問題NP難性質(zhì)的劃分研究24-36
• 2.1 NP完全理論概述24-26
• 2.1.1 P類和NP類問題24-25
• 2.1.2 NP-omplete類問題25-26
• 2.1.3 NP-Hard類問題26
• 2.2 布局問題NP難性質(zhì)的聲稱說法研究26-30
• 2.2.1 聲稱說法的統(tǒng)計26-29
• 2.2.2 聲稱說法的分類29-30
• 2.3 布局問題復(fù)雜性的劃分研究30-31
• 2.3.1 分類策略的選擇30
• 2.3.2 分類方案的實施30-31
• 2.4 對布局問題NP難性質(zhì)統(tǒng)計分類結(jié)果的分析31-35
• 2.4.1 統(tǒng)計結(jié)果31-34
• 2.4.2 結(jié)果分析34-35
• 2.5 本章小結(jié)35-36
• 3 布局問題NP難性質(zhì)的證明嘗試36-44
• 3.1 托盤裝載問題歸結(jié)為NP難問題的證明嘗試36-38
• 3.1.1 托盤裝載問題概述36-37
• 3.1.2 證明思路37-38
• 3.2 由證明過程所啟發(fā)的問題求解方法38-40
• 3.2.1 求解思路38-39
• 3.2.2 求解實例39-40
• 3.3 求解方法的應(yīng)用40-42
• 3.4 本章小結(jié)42-44
• 4 布局問題NP難性質(zhì)的傳遞路線梳理44-56
• 4.1 WASCHER布局問題分類法概述44-46
• 4.2 布局問題復(fù)雜性的傳遞路線梳理46-51
• 4.2.1 六種基本布局問題47
• 4.2.2 復(fù)雜性傳遞關(guān)系的建立47-51
• 4.3 布局問題NP難證明中的歸結(jié)傳遞圖的建立51-53
• 4.4 關(guān)于歸納不同布局問題NP難性質(zhì)的布局文獻研究53-54
• 4.5 本章小結(jié)54-56
• 5 布局問題難度判定系統(tǒng)的建立56-68
• 5.1 布局問題難度判定系統(tǒng)的設(shè)計57-59
• 5.1.1 系統(tǒng)結(jié)構(gòu)設(shè)計57-58
• 5.1.2 系統(tǒng)數(shù)據(jù)庫設(shè)計58-59
• 5.2 布局問題NP難性質(zhì)的描述模型59-63
• 5.2.1 描述模型的建立59-60
• 5.2.2 描述模型的內(nèi)容60-63
• 5.3 布局問題難度判定系統(tǒng)的建立及運行63-66
• 5.4 本章小結(jié)66-68
• 6 總結(jié)與展望68-70
• 6.1 研究總結(jié)68-69
• 6.3 研究展望69-70
• 參考文獻70-74
• 作者簡歷及攻讀碩士學(xué)位期間取得的研究成果74-78
• 學(xué)位論文數(shù)據(jù)集78

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 湯全林;胡安定;;赴瑞典參加“工業(yè)維修的組織與管理”國際研修班學(xué)習(xí)的主要內(nèi)容(續(xù))[J];設(shè)備維修;1984年02期

2 吳斐,侯云章;基于啟發(fā)式結(jié)果的模擬退火算法在布局問題中的應(yīng)用[J];物流科技;2005年09期

3 王金敏,查建中,王玉新;布局問題的聚塊算法[J];機械設(shè)計;1999年02期

4 王金敏,王玉新,查建中;布局問題約束的分類及表達[J];計算機輔助設(shè)計與圖形學(xué)學(xué)報;2000年05期

5 劉先暢;縣域小城鎮(zhèn)布局的幾個問題[J];小城鎮(zhèn)建設(shè);2000年03期

6 周娜;宓為建;徐子奇;;設(shè)備混合布局問題研究[J];上海海事大學(xué)學(xué)報;2013年04期

7 朱國金;;廣珠(澳)鐵路選線布局問題的探討[J];中國鐵路;1993年08期

8 王金敏;齊楊;;矩形布局問題吸引子法研究[J];圖學(xué)學(xué)報;2012年06期

9 唐曉君,查建中,陸一平;布局問題的復(fù)雜性和建模方法[J];北方交通大學(xué)學(xué)報;2003年01期

10 王金敏;王保春;朱艷華;;求解矩形布局問題的自適應(yīng)算法[J];圖學(xué)學(xué)報;2012年03期

中國重要會議論文全文數(shù)據(jù)庫 前1條

1 丁梅;朱美琳;;鉆井布局問題的模型及解法[A];中國運籌學(xué)會第六屆學(xué)術(shù)交流會論文集（上卷）[C];2000年

中國重要報紙全文數(shù)據(jù)庫 前4條

1 駐京記者 金豐杰;24小時供應(yīng)≠24小時營業(yè)[N];醫(yī)藥經(jīng)濟報;2004年

2 本報評論員;配套服務(wù)應(yīng)跟上[N];白銀日報;2008年

3 記者 王靜;中小學(xué)校布局問題亟待破題[N];石家莊日報;2013年

4 許昌縣將官池鎮(zhèn)黨委書記 王建民;抓住三個關(guān)鍵環(huán)節(jié) 解決好三大問題[N];許昌日報;2012年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前2條

1 徐義春;衛(wèi)星艙布局問題的智能求解方法研究[D];華中科技大學(xué);2008年

2 黃振東;衛(wèi)星艙布局問題的啟發(fā)式求解與涌現(xiàn)計算[D];華中科技大學(xué);2014年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 宋真真;基于蟻群算法的布局問題研究[D];天津職業(yè)技術(shù)師范大學(xué);2016年

2 楊萌;布局問題NP難性質(zhì)的傳遞路線研究[D];北京交通大學(xué);2016年

3 謝艷芳;求解加權(quán)圓集布局問題的啟發(fā)式演化算法研究[D];湘潭大學(xué);2012年

4 季美;衛(wèi)星艙布局問題的求解研究[D];華中科技大學(xué);2011年

5 楊林;布局問題的演化算法[D];湖南師范大學(xué);2007年

6 王璐;切割與布局問題的算法分類研究[D];北京交通大學(xué);2009年

7 馬國通;兩類矩形布局問題的啟發(fā)式算法研究[D];北京交通大學(xué);2008年

8 楊林;求解帶性能約束圓集布局問題的啟發(fā)式蟻群算法研究[D];湘潭大學(xué);2010年

9 譚思捷;單行布局問題的變鄰域算法研究及其應(yīng)用[D];西南交通大學(xué);2013年

10 劉玉飛;容量限制CVT及其在布局問題中的應(yīng)用[D];合肥工業(yè)大學(xué);2013年

，

本文編號：522826