本文關(guān)鍵詞：兩類組合最優(yōu)化問題的探討，由筆耕文化傳播整理發(fā)布。

【摘要】：中國郵遞員問題是一個(gè)重要的組合最優(yōu)化問題,涉及到在網(wǎng)絡(luò)中如何在特殊的限定下最優(yōu)地選取路線的問題,該問題由中國數(shù)學(xué)家管梅谷1960年首次提出。到今天,國內(nèi)外對(duì)中國郵遞員問題及其相關(guān)問題的研究已有50多年,得到了大量豐富而又深刻的結(jié)果。在計(jì)算復(fù)雜性領(lǐng)域,中國郵遞員問題是一個(gè)P類問題,即存在多項(xiàng)式時(shí)間算法能得到該問題的最優(yōu)解。本文首先對(duì)中國郵遞員問題的結(jié)構(gòu)予以了清晰的描述,通過巧oin的概念引入,給出了求解中國郵遞員問題的各種算法介紹；其次,我們研究了無向賦權(quán)圖上的最大權(quán)圈裝箱問題,并從算法復(fù)雜性角度給予了中國郵遞員問題與最大權(quán)圈裝箱問題的等價(jià)性的完整證明；最后,基于我們得到的關(guān)于中國郵遞員問題與最大權(quán)圈裝箱問題的相關(guān)結(jié)果,我們引入了所謂的最大類歐拉回路概念,并作了一些探討,指明了未來研究的方向。 平行機(jī)排序是一個(gè)經(jīng)典的組合最優(yōu)化問題,帶拒絕費(fèi)用的平行機(jī)排序問題是經(jīng)典平行機(jī)排序問題的一個(gè)推廣,該問題是NP-難的,除非P=NP,否則我們不可能找到多項(xiàng)式時(shí)間算法求得該問題的最優(yōu)解。在本文中,我們給出了帶拒絕費(fèi)用的平行機(jī)排序問題的一個(gè)2-近似強(qiáng)多項(xiàng)式時(shí)間算法,并且給出了實(shí)例來說明我們給出的算法是緊的,即算法不可能取得比2更好的近似比。同時(shí),我們也給出了該問題的一個(gè)多項(xiàng)式時(shí)間近似方案,且得到了該方案的時(shí)間復(fù)雜度為O
【關(guān)鍵詞】：中國郵遞員 圈裝箱 排序 多項(xiàng)式時(shí)間算法 近似算法 PTAS
【學(xué)位授予單位】：昆明理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：F618;O224
【目錄】：

• 摘要6-7
• Abstract7-11
• 第一章 緒論11-15
• §1.1 中國郵遞員問題與最大權(quán)圈裝箱問題11-12
• §1.2 帶拒絕費(fèi)用的平行機(jī)排序問題12-13
• §1.3 文章內(nèi)容結(jié)構(gòu)13-15
• 第二章 預(yù)備知識(shí)15-26
• §2.1 組合最優(yōu)化簡(jiǎn)介15-17
• §2.2 圖論基礎(chǔ)17-20
• §2.3 排序相關(guān)術(shù)語和記號(hào)20-22
• §2.4 算法和計(jì)算復(fù)雜性22-26
• 第三章 中國郵遞員問題與最大權(quán)圈裝箱問題26-39
• §3.1 無向賦權(quán)圖上的中國郵遞員問題算法27-29
• §3.1.1：奇偶點(diǎn)圖上作業(yè)算法27-28
• §3.1.2：最小權(quán)完美匹配算法28
• §3.1.3：T-join定義與中國郵遞員問題28-29
• §3.2 無向圖上中國郵遞員問題與最大權(quán)圈裝箱問題29-37
• §3.3 最大類歐拉回路問題37-38
• §3.4 小結(jié)及其未來的研究方向38-39
• 第四章 帶拒絕費(fèi)用的平行機(jī)排序問題39-61
• §4.1 帶拒絕費(fèi)用的平行機(jī)排序問題的2-近似強(qiáng)多項(xiàng)式時(shí)間算法40-47
• §4.2 帶拒絕費(fèi)用平行機(jī)排序問題的近似排序方案47-60
• §4.2.1：帶拒絕費(fèi)用的平行機(jī)排序問題的輔助實(shí)例47-52
• §4.2.2：輔助實(shí)例和原始實(shí)例52-58
• §4.2.3：近似排序方案：?jiǎn)栴}P|∑_(Jj∈R)e_j≤B|C_(max)的一個(gè)PTAS58-60
• §4.3 小結(jié)及未來研究的方向60-61
• 第五章 結(jié)論61-62
• 致謝62-63
• 參考文獻(xiàn)63-66
• 附錄A 攻讀碩士期間發(fā)表論文目錄66

【參考文獻(xiàn)】

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

1 越民義,韓繼業(yè);n個(gè)零件在m臺(tái)機(jī)床上的加工順序問題(Ⅰ)[J];中國科學(xué);1975年05期

2 管梅谷;奇偶點(diǎn)圖上作業(yè)法[J];數(shù)學(xué)學(xué)報(bào);1960年03期

3 管梅谷;中國投遞員問題綜述[J];數(shù)學(xué)研究與評(píng)論;1984年01期

4 張峰;唐國春;;工件可拒絕排序問題的研究[J];同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年01期

  本文關(guān)鍵詞：兩類組合最優(yōu)化問題的探討，，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：487332