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

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

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

【參考文獻】

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

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

2 管梅谷;奇偶點圖上作業(yè)法[J];數(shù)學學報;1960年03期

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

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

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

本文編號：487332