發(fā)布時間：2017-11-07 16:28

  本文關(guān)鍵詞：求解擬陣約束下下模函數(shù)最小集合覆蓋的貪婪算法及其性能保證

  更多相關(guān)文章： 下模函數(shù) 擬陣約束 背包約束 貪婪算法 性能保證

【摘要】：組合優(yōu)化問題是在一些約束條件下給定的有限集合中,根據(jù)某一目標找出一個最符合要求的最優(yōu)解的這么一類數(shù)學規(guī)劃問題,也稱為組合規(guī)劃。組合優(yōu)化都是在由有限個方案構(gòu)成的集合中,選擇能夠使目標函數(shù)達到最優(yōu)解的最優(yōu)子集。組合優(yōu)化問題的發(fā)展在生產(chǎn)生活等各個領(lǐng)域有著廣泛的應用,例如在商品生產(chǎn),交通運輸航線問題,裝箱問題,工作指派問題等。等到擬陣理論進入到組合優(yōu)化問題的研究領(lǐng)域中,得到了很多理論成果,比如推銷問題,最短路問題和最大支撐樹問題。下模函數(shù)作為一類特殊的實值函數(shù),并且是被定義在冪集上。下模函數(shù)的變量是離散的不是連續(xù)的。由于這種特殊的性質(zhì)使得下模函數(shù)在求解最優(yōu)化問題中起到了重要作用。在組合優(yōu)化中,下模函數(shù)最大值問題的求解被當做一個中心問題,我們可以把很多組合優(yōu)化問題最優(yōu)值的求解轉(zhuǎn)化成求解下模函數(shù)的最大值問題,這使得組合優(yōu)化問題都可以認為是求解下模函數(shù)的最大值問題,歸納出很多重要問題比如最大割、最大熵采樣、最大設(shè)施選址和集合覆蓋的問題。因此我們研究下模函數(shù)的最值問題就有非常特殊的理論價值和實踐應用價值。然而,求解下模函數(shù)是一個NP-難問題,人們不斷地尋找有效的多項式算法。本文主要介紹了如何求解下模函數(shù)的最優(yōu)值理論和如何在求解下模函數(shù)最大值問題當中應用貪婪算法。我們主要給出一個近似貪婪算法,并將這個貪婪算法運用在被多重擬陣約束下任意非負的下模函數(shù)最大值問題。最后介紹了下模函數(shù)的最值被k維背包約束下的求解問題。并把各種算法進行了比較全面的理論分析進而得出其性能保證。本文一共分為五章,第一章首先介紹了最優(yōu)化理論問題的起源與發(fā)展和貪婪算法,以及針對不同的算法如何分析它們的性能保證,接著給出了這篇文章研究的背景,最后介紹了這篇文章的任務(wù)以及要解決什么樣的問題。第二章綜述了下模函數(shù)的概念及相關(guān)定理,以及貪婪算法解決最小集合的覆蓋問題,并給出了此貪婪算法的性能保證。第三章主要詳細介紹如何用近似貪婪算法和局部搜索程序?qū)τ谙履：瘮?shù)最大值被k個擬陣約束下的求解問題,并證明了貪婪算法的近似度為()111 k2ke??+++?÷è?第四章主要介紹了近似算法對于下模函數(shù)最大值被k維背包約束下的求解問題,并且證明此算法可以得到一個12 n?e?-?÷è?的近似解。第五章全面的對論文進行了總結(jié)、展望。
【學位授予單位】：蘭州交通大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O224

【相似文獻】

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

1 陳洪;蔡佳;張玉成;;多分類貪婪算法的一致性[J];湖北大學學報(自然科學版);2005年04期

2 楊潔;;基于貪婪算法的衛(wèi)星區(qū)域觀測擺角方案選擇方法[J];廣西科學院學報;2006年02期

3 高靜宇;馬文麗;孫漢順;孫立哲;鄭文嶺;;一種新的蛋白質(zhì)結(jié)構(gòu)字母序列優(yōu)化算法[J];生物信息學;2010年03期

4 馮光毅;;就背包和部件加工問題淺論貪婪算法的運用及優(yōu)化方案[J];計算機光盤軟件與應用;2013年24期

5 徐立新,張玉忠;集合核約束分劃的貪婪算法分析[J];系統(tǒng)工程理論與實踐;1999年04期

6 張巖;;單調(diào)多邊形三角剖分貪婪算法的分析與實現(xiàn)[J];牡丹江師范學院學報(自然科學版);2002年04期

7 田仲;李加祥;;基于貪婪算法的影響網(wǎng)絡(luò)行動方案優(yōu)選[J];指揮控制與仿真;2013年03期

8 肖華勇,田錚,師義民;資源公平分配的一種貪婪算法[J];運籌與管理;2000年02期

9 賈欣鑫;羅亮;郭麗峰;何尚錄;;求解組合拍賣問題的一種貪婪算法[J];溫州大學學報(自然科學版);2009年03期

10 周斌;程慧;楊立志;裴國慶;;基于貪婪算法的符號網(wǎng)絡(luò)中社團結(jié)構(gòu)快速發(fā)現(xiàn)算法[J];大眾科技;2009年12期

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

1 陳華;管樂樂;宗鵬安;黃星星;;TSP問題的一個新算法[A];全國第20屆計算機技術(shù)與應用學術(shù)會議（CACIS·2009）暨全國第1屆安全關(guān)鍵技術(shù)與應用學術(shù)會議論文集（上冊）[C];2009年

2 張興輝;馮明靜;;談智能滅火救援輔助指揮系統(tǒng)的設(shè)計與思考[A];2003年湖北省滅火救援學術(shù)研討會論文集[C];2003年

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

1 李海鋒;壓縮感知恢復算法及應用研究[D];華南理工大學;2014年

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

1 曹金;基于壓縮感知的信道估計關(guān)鍵技術(shù)研究[D];電子科技大學;2014年

2 張立群;求解擬陣約束下下模函數(shù)最小集合覆蓋的貪婪算法及其性能保證[D];蘭州交通大學;2015年

3 任文軒;運用貪婪算法構(gòu)建物流網(wǎng)絡(luò)的方法與應用研究[D];中國科學技術(shù)大學;2011年

4 王海洋;基于SVM的分段貪婪算法研究[D];西安科技大學;2009年

5 孫魁偉;基于貪婪算法的自動排課系統(tǒng)設(shè)計與實現(xiàn)[D];大連理工大學;2013年

6 孟慶敏;關(guān)于幾種光滑函數(shù)類的最佳逼近[D];華北電力大學;2014年

7 孫劍陽;復方藥物篩選前期的模型及算法[D];山東大學;2014年

8 袁毅;側(cè)圍焊接工位焊點分配及路徑規(guī)劃的研究[D];湖南大學;2013年

9 馮小軍;社會網(wǎng)絡(luò)環(huán)境下一種基于潛力的影響最大化算法[D];復旦大學;2010年

10 葉環(huán)球;限秩最大子集問題[D];浙江大學;2001年

，

本文編號：1153209