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

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

【學(xué)位級別】：碩士

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


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

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



本文編號：3693460