本文關(guān)鍵詞：最小點(diǎn)覆蓋近似算法及其應(yīng)用研究，由筆耕文化傳播整理發(fā)布。

【摘要】：最小點(diǎn)覆蓋問題,是指給定一個無向圖?EVG),(,其中V為頂點(diǎn)集,E為邊集,求頂點(diǎn)集V的一個最小子集S,使得對于邊集E的任意一條邊Euv?,有Su?或Sv?.最小點(diǎn)覆蓋問題是組合優(yōu)化中一個典型的NP完全問題,因其有著廣泛的應(yīng)用,所以備受關(guān)注.至今雖然已經(jīng)有很多求解該問題的近似算法,但許多人仍致力于最小點(diǎn)覆蓋的研究,以便尋求更簡潔、更精確的算法.因此,本文利用經(jīng)典的最短路算法Dijkstra算法和蟻群算法對最小點(diǎn)覆蓋問題分別進(jìn)行了研究,具體內(nèi)容如下:(1)基于最短路算法,分別研究了無權(quán)圖與賦權(quán)圖的最小點(diǎn)覆蓋問題,并設(shè)計了算法.首先,在給定的圖中任選一點(diǎn)作為初始點(diǎn),并給出允許集及相關(guān)定義.然后,利用經(jīng)典的最短路算法Dijkstra算法,求出初始點(diǎn)到允許集中各頂點(diǎn)的最短路徑,并按照一定的原則選擇近似點(diǎn)覆蓋集.最后,通過算例闡釋了算法的實現(xiàn)過程的合理性及有效性.(2)關(guān)于蟻群算法,研究了賦權(quán)圖的最小點(diǎn)覆蓋問題.給出了一個基于蟻群算法的近似算法,求解最小點(diǎn)覆蓋問題的近似解.通過修改螞蟻的狀態(tài)轉(zhuǎn)移概率公式,簡化狀態(tài)轉(zhuǎn)移規(guī)則,建立了相應(yīng)的數(shù)學(xué)模型,從而得出求解最小點(diǎn)覆蓋的近似算法步驟,最后進(jìn)行了實例解析.(3)將最小點(diǎn)覆蓋問題應(yīng)用到求解停車場選址問題中.利用已獲得的近似算法,對停車場選址問題進(jìn)行了求解,并且給出了停車場選址問題的較優(yōu)方案.
【關(guān)鍵詞】：最小點(diǎn)覆蓋 近似算法 Dijkstra算法 蟻群算法 停車場選址
【學(xué)位授予單位】：蘭州交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要4-5
• Abstract5-8
• 1 緒論8-10
• 1.1 研究動態(tài)及現(xiàn)狀8-9
• 1.2 研究目的及意義9
• 1.3 目前該領(lǐng)域存在的問題9
• 1.4 研究內(nèi)容和方法9-10
• 2 基于最短路算法的最小點(diǎn)覆蓋問題10-24
• 2.1 引言10
• 2.2 算法設(shè)計10-14
• 2.2.1 無權(quán)圖的最小點(diǎn)覆蓋問題12
• 2.2.2 點(diǎn)賦權(quán)圖的最小點(diǎn)覆蓋問題12-13
• 2.2.3 邊賦權(quán)圖的最小點(diǎn)覆蓋問題13
• 2.2.4 點(diǎn)、邊賦權(quán)圖的最小點(diǎn)覆蓋問題13-14
• 2.3 算法實例14-22
• 2.3.1 無賦權(quán)圖算法實例14-16
• 2.3.2 點(diǎn)賦權(quán)圖算法實例16-18
• 2.3.3 邊賦權(quán)圖算法實例18-20
• 2.3.4 點(diǎn)、邊賦權(quán)圖算法實例20-22
• 2.4 算法性質(zhì)22-23
• 2.5 本章小結(jié)23-24
• 3 基于蟻群算法的最小點(diǎn)覆蓋問題24-30
• 3.1 蟻群算法24-27
• 3.1.1 蟻群算法基本原理24-25
• 3.1.2 蟻群算法解決最小點(diǎn)覆蓋問題的基本原理25-27
• 3.2 算法設(shè)計27-28
• 3.3 算法實例28-29
• 3.4 本章小結(jié)29-30
• 4 最小點(diǎn)覆蓋問題在實際中的應(yīng)用30-33
• 4.1 引言30
• 4.2 模型建立及應(yīng)用30-32
• 4.3 本章小結(jié)32-33
• 結(jié)論33-34
• 致謝34-35
• 參考文獻(xiàn)35-37
• 讀學(xué)位期間的研究成果37

【相似文獻(xiàn)】

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

1 孫俊逸;一類函數(shù)最小點(diǎn)及最小值的插值解法[J];阜陽師范學(xué)院學(xué)報(自然科學(xué)版);1993年01期

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

1 崔笑川;最小點(diǎn)覆蓋近似算法及其應(yīng)用研究[D];蘭州交通大學(xué);2015年

2 許小雙;二分圖的受約束最小點(diǎn)覆蓋問題研究[D];中南大學(xué);2007年

3 常樂;參數(shù)化點(diǎn)覆蓋及最小點(diǎn)覆蓋問題研究[D];中南大學(xué);2007年

  本文關(guān)鍵詞：最小點(diǎn)覆蓋近似算法及其應(yīng)用研究，由筆耕文化傳播整理發(fā)布。

，

本文編號：481019