最小點覆蓋問題（Minimum Vertex Cover problem,MVCP）是給定一個無向圖G=（V,E）,求頂點集V的最小子集S,使G中每條邊在S中至少有一個端點。該問題是經典的NP完全問題,目前沒有多項式時間算法,因此研究的重點是在合理計算時間內找到一個接近最優(yōu)解的可行解。本文利用蟻群算法對最小點覆蓋問題進行研究,主要工作如下:（1）將最小點覆蓋問題與TSP問題進行比較,通過對狀態(tài)轉移規(guī)則和信息素更新規(guī)則的修改,得到蟻群算法求解該問題的基本原理。利用改進的蟻群算法,分別研究了無權圖和賦權圖的最小點覆蓋問題,且設計了算法。最后給出實例分析了該算法的合理性和有效性。（2）蟻群算法的正反饋機制易使搜索陷入局部收斂,出現(xiàn)局部最優(yōu)解。將基本的蟻群算法與最大最小蟻群算法進行比較,得到最大最小蟻群算法求解該問題的基本原理。通過對狀態(tài)轉移規(guī)則和信息素更新規(guī)則增加限定條件,有效的避免了局部最優(yōu)現(xiàn)象。利用改進的最大最小蟻群算法,研究了無權圖的最小點覆蓋問題。最后給出實例驗證了該算法的可行性。（3）考慮共享單車對城市交通的影響和企業(yè)的運營成本,將共享單車投放點的選擇看作是有條件的最小點覆蓋問題,... 

【文章頁數(shù)】：42 頁

【學位級別】：碩士

【文章目錄】：
摘要
Abstract
1 緒論
    1.1 選題背景及意義
    1.2 國內外研究現(xiàn)狀
        1.2.1 最小點覆蓋問題研究現(xiàn)狀
        1.2.2 蟻群算法的研究
    1.3 本文研究內容
2 蟻群算法及其優(yōu)化算法
    2.1 蟻群算法的簡介
        2.1.1 蟻群系統(tǒng)
        2.1.2 蟻群算法基本原理
    2.2 最大最小蟻群算法
    2.3 本章小結
3 基于蟻群算法的最小點覆蓋問題
    3.1 蟻群算法求解最小點覆蓋問題基本原理
    3.2 算法設計
        3.2.2 點賦權圖的最小點覆蓋問題
        3.2.3 邊賦權圖的最小點覆蓋問題
        3.2.4 點、邊賦權圖的最小點覆蓋問題
    3.3 算法實例
        3.3.1 無權圖算法實例
        3.3.2 點賦權圖算法實例
        3.3.3 邊賦權圖算法實例
        3.3.4 點、邊賦權圖算法實例
    3.4 本章小結
4 基于最大最小蟻群算法的最小點覆蓋問題
    4.1 最大最小蟻群算法解決最小點覆蓋的基本原理
    4.2 算法設計
    4.3 算法實例
    4.4 本章小結
5 最小點覆蓋問題在共享單車投放點選取的應用
    5.1 引言
    5.2 模型建立
    5.3 算法設計
    5.4 算例求解及結果分析
    5.5 本章小結
結論
致謝
參考文獻
攻讀學位期間的研究成果


【參考文獻】：
期刊論文
[1]最小權點覆蓋的掃描測試向量生成算法[J]. 王力,穆東旭.  計算機仿真. 2019(07)
[2]服務半徑約束下城市快遞雙層配送網絡節(jié)點選址優(yōu)化[J]. 杜剛誠,冉林娜.  上海海事大學學報. 2019(02)
[3]基于蟻群算法的動態(tài)共享單車調度優(yōu)化[J]. 汪慎文,徐亮,楊鋒,李美羽.  南昌工程學院學報. 2019(03)
[4]基于改進勢場蟻群算法的移動機器人最優(yōu)路徑規(guī)劃[J]. 張強,陳兵奎,劉小雍,劉曉宇,楊航.  農業(yè)機械學報. 2019(05)
[5]基于蟻群算法的無人機任務規(guī)劃優(yōu)化模型研究[J]. 蔣莎,劉學文,葉家君.  重慶師范大學學報(自然科學版). 2019(01)
[6]基于最小點覆蓋的共享單車投放點選取方法[J]. 郝斌斌,呂斌,陳京榮.  交通信息與安全. 2018(05)
[7]基于子群劃分的共享單車調度優(yōu)化[J]. 葉錦程,胡驥.  綜合運輸. 2018(08)
[8]基于核心化技術的點覆蓋改進算法[J]. 駱偉忠,蔡昭權.  計算機工程與科學. 2018(08)
[9]一種增量式約簡方法求解最小頂點覆蓋問題[J]. 占善華,謝小軍.  計算機應用研究. 2018(12)
[10]混合算法求解多目標平衡旅行商問題[J]. 董學士,董文永,王豫峰.  計算機研究與發(fā)展. 2017(08)

碩士論文
[1]基于合作競爭理論的設施選址問題研究[D]. 郭倩.北京交通大學 2014



本文編號：3693460