發(fā)布時(shí)間：2017-08-26 20:23

  本文關(guān)鍵詞：調(diào)整和權(quán)值下一類極大加和支撐樹(shù)逆問(wèn)題

  更多相關(guān)文章： 極大+和支撐樹(shù)逆問(wèn)題 瓶頸型哈明距離 二分法 單位和型哈明距離 不可近似性 Lagrange對(duì)偶問(wèn)題

【摘要】：本文研究的是一類調(diào)整和-費(fèi)用向量時(shí)的極大+和支撐樹(shù)逆問(wèn)題(IMSST)極大+和支撐樹(shù)問(wèn)題(MSST)是在一個(gè)邊賦權(quán)無(wú)向連通網(wǎng)絡(luò)G(V,E,c,ω)中,找一棵最優(yōu)支撐樹(shù)T,使得目標(biāo)函數(shù)maxe∈Tω(e)+∑e∈Tc(e)盡可能的小.本文研究的極大+和支撐樹(shù)逆問(wèn)題為：給定網(wǎng)絡(luò)G的一棵非最優(yōu)支撐樹(shù)T0,調(diào)整網(wǎng)絡(luò)各邊的費(fèi)用c(e)到c(e),使得T0為新網(wǎng)絡(luò)G(V,E,c,ω)下的最優(yōu)極大+和支撐樹(shù),其中0 c-l≤c≤c+ μ,l≥0,μ讓≥O.目標(biāo)函數(shù)是使得哈明距離下邊權(quán)調(diào)整費(fèi)用盡可能的小.第一章介紹了極大+和支撐樹(shù)逆問(wèn)題的背景和研究意義,并列出了研究哈明距離下極大+和支撐樹(shù)逆問(wèn)題需要的預(yù)備知識(shí).第二章研究有界瓶頸型哈明距離下極大+和支撐樹(shù)逆問(wèn)題.首先給出了該問(wèn)題的數(shù)學(xué)模型,進(jìn)而分析了其解的性質(zhì)和可行性檢驗(yàn)方法；接著設(shè)計(jì)求解該問(wèn)題的二分法,并分析了算法的復(fù)雜度為O(mlog~2(n)),其中n為頂點(diǎn)的個(gè)數(shù);最后進(jìn)行數(shù)值實(shí)驗(yàn),檢驗(yàn)該算法的有效性.第三章研究單位和型哈明距離下極大+和支撐樹(shù)逆問(wèn)題.先證明該問(wèn)題為NP-難的,而NP-難問(wèn)題很難找到最優(yōu)解,因此我們分析了該問(wèn)題的不可近似性.最后以該問(wèn)題的擴(kuò)充問(wèn)題為媒介求得該問(wèn)題的近似解.第四章對(duì)本文做出總結(jié)并對(duì)極大+和支撐樹(shù)逆問(wèn)題未來(lái)的研究方向進(jìn)行展望.
【關(guān)鍵詞】：極大+和支撐樹(shù)逆問(wèn)題 瓶頸型哈明距離 二分法 單位和型哈明距離 不可近似性 Lagrange對(duì)偶問(wèn)題
【學(xué)位授予單位】：東南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O221
【目錄】：

• 摘要4-5
• Abstract5-9
• 第一章 緒論9-24
• 1.1 研究背景及意義9-12
• 1.2 支撐樹(shù)的基礎(chǔ)知識(shí)12-13
• 1.3 算法復(fù)雜性簡(jiǎn)介13-17
• 1.3.1 算法的基本概念14-16
• 1.3.2 算法的設(shè)計(jì)16-17
• 1.4 模、共軛函數(shù)、Lagrange對(duì)偶函數(shù)17-23
• 1.4.1 向量的模17-19
• 1.4.2 矩陣的模19
• 1.4.3 對(duì)偶模、共軛函數(shù)19-20
• 1.4.4 Lagrange對(duì)偶函數(shù)20-23
• 1.5 本文主要研究工作23-24
• 第二章 有界瓶頸型哈明距離下的極大+和支撐樹(shù)逆問(wèn)題24-35
• 2.1 IMSST_(BH)~b的數(shù)學(xué)模型24-27
• 2.2 IMSST_(BH)~b的算法27-35
• 2.2.1 IMSS_(BH)~b的可行性27-28
• 2.2.2 IMSST_(BH)~b的算法28-31
• 2.2.3 IMSST_(BH)~b的一個(gè)實(shí)例31-33
• 2.2.4 數(shù)值實(shí)驗(yàn)33-35
• 第三章 單位和型哈明距離下的極大+和支撐樹(shù)逆問(wèn)題35-47
• 3.1 l_0模下極大+和支撐樹(shù)逆問(wèn)題的數(shù)學(xué)模型35-37
• 3.2 l_0模下極大+和支撐樹(shù)逆問(wèn)題的不可近似性37-41
• 3.2.1 不可近似性理論的相關(guān)定義37-39
• 3.2.2 l_0模下極大+和支撐樹(shù)逆問(wèn)題的復(fù)雜性和不可近似性39-41
• 3.3 l_0模下極大+和支撐樹(shù)逆問(wèn)題的近似解41-47
• 3.3.1 標(biāo)準(zhǔn)化模型41
• 3.3.2 l_0模下極大+和支撐樹(shù)逆問(wèn)題的擴(kuò)充問(wèn)題41-43
• 3.3.3 l_0模和l_1模下極大+和支撐樹(shù)逆問(wèn)題的Lagrange對(duì)偶問(wèn)題43-46
• 3.3.4 單位和型哈明距離下極大+和支撐樹(shù)逆問(wèn)題的近似解46-47
• 第四章 總結(jié)與展望47-48
• 致謝48-49
• 參考文獻(xiàn)49-52

【相似文獻(xiàn)】

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

1 周麗,黃哲浩,王博,賀北方;求最小支撐樹(shù)的方法探討[J];鄭州工業(yè)大學(xué)學(xué)報(bào);2001年03期

2 李幫義,姚恩瑜;嚴(yán)格第k最小支撐樹(shù)問(wèn)題[J];系統(tǒng)工程理論與實(shí)踐;2002年01期

3 連海峰,雷雪萍;最小支撐樹(shù)的新算法[J];淮陰師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2004年01期

4 王澤磊,張同全,李建平;關(guān)于K棵支撐樹(shù)的2個(gè)問(wèn)題[J];云南大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年S1期

5 付鉛生,李幫義;Pendants-median支撐樹(shù)及其一個(gè)相關(guān)問(wèn)題:復(fù)雜性和算法[J];高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào);2004年02期

6 李淑君;唐恒永;;約束最小支撐樹(shù)問(wèn)題[J];沈陽(yáng)師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年01期

7 許進(jìn);;幾類圖的支撐樹(shù)的計(jì)數(shù)公式[J];西北大學(xué)學(xué)報(bào)(自然科學(xué)版);1989年04期

8 周德鎮(zhèn);;最小支撐樹(shù)簡(jiǎn)算法及其應(yīng)用[J];管理現(xiàn)代化;1993年02期

9 朱娟萍;吳旭亭;楊子蘭;;網(wǎng)絡(luò)中支撐樹(shù)的邊擴(kuò)容問(wèn)題[J];云南大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年05期

10 左霞;關(guān)秀翠;;一類特殊的極大+和支撐樹(shù)在調(diào)整和權(quán)值下的逆問(wèn)題[J];南京大學(xué)學(xué)報(bào)(數(shù)學(xué)半年刊);2013年02期

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

1 章舜哲;圖的哈密爾頓連通性及支撐樹(shù)特征研究[D];華中師范大學(xué);2015年

2 陳園;圖中參數(shù)與樹(shù)型結(jié)構(gòu)研究[D];華中師范大學(xué);2013年

3 劉龍城;賦權(quán)哈明距離下若干網(wǎng)絡(luò)逆問(wèn)題的研究[D];浙江大學(xué);2009年

4 張斌武;哈明距離下的逆優(yōu)化問(wèn)題及多物品的制造與分配問(wèn)題[D];浙江大學(xué);2005年

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

1 朱芳;幾類網(wǎng)絡(luò)改進(jìn)問(wèn)題的算法研究[D];中國(guó)計(jì)量學(xué)院;2015年

2 何新燕;調(diào)整和權(quán)值下一類極大加和支撐樹(shù)逆問(wèn)題[D];東南大學(xué);2015年

3 王芳;網(wǎng)絡(luò)中的均勻度問(wèn)題和比值問(wèn)題[D];國(guó)防科學(xué)技術(shù)大學(xué);2004年

4 楊曉凌;最短路及最小支撐樹(shù)的靈敏度分析[D];國(guó)防科學(xué)技術(shù)大學(xué);2007年

5 徐何花;K_(1,5)-free圖中的支撐樹(shù)[D];華中師范大學(xué);2012年

6 潘陽(yáng);關(guān)于圖的最小線性布局的一些問(wèn)題與結(jié)果[D];福州大學(xué);2011年

7 王小燕;基于最小費(fèi)用支撐樹(shù)的合作對(duì)策問(wèn)題[D];國(guó)防科學(xué)技術(shù)大學(xué);2005年

8 張春明;圖論在聚類分析中的應(yīng)用[D];山東師范大學(xué);2004年

9 王妍;圖的在支撐樹(shù)上作限制的L（p，1）-點(diǎn)標(biāo)號(hào)及L（p，，q）-邊標(biāo)號(hào)問(wèn)題[D];山東師范大學(xué);2012年

本文編號(hào)：742803