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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 李海鋒;壓縮感知恢復(fù)算法及應(yīng)用研究[D];華南理工大學(xué);2014年

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

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

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

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

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

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

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

7 孫劍陽(yáng);復(fù)方藥物篩選前期的模型及算法[D];山東大學(xué);2014年

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

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

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

，

本文編號(hào)：1153209