頂點(diǎn)覆蓋問題的求解算法研究

目錄
前言
第1章　緒論　1　
1.1　研究背景和意義　1　
1.2　相關(guān)研究工作　4　
1.2.1　*小頂點(diǎn)覆蓋問題的研究現(xiàn)狀　4　
1.2.2　*小加權(quán)頂點(diǎn)覆蓋問題的研究現(xiàn)狀　7　
1.2.3　泛化頂點(diǎn)覆蓋問題的研究現(xiàn)狀　10　
1.2.4　*小分區(qū)頂點(diǎn)覆蓋問題的研究現(xiàn)狀　12　
1.3　主要研究內(nèi)容和成果　14　
1.4　本書主要結(jié)構(gòu)　16　
第2章　相關(guān)算法介紹　18　
2.1　局部搜索算法　18　
2.1.1　局部搜索算法框架　18　
2.1.2　局部搜索算法的核心技術(shù)　20　
2.2　模因算法　22　
2.2.1　模因算法框架　22　
2.2.2　模因算法特點(diǎn)　25　
2.3　模擬退火算法　25　
2.3.1　模擬退火算法原理　26　
2.3.2　模擬退火算法流程　27　
2.3.3　模擬退火算法優(yōu)勢(shì)　27　
2.4　本章小結(jié)　29　
第3章　*小加權(quán)頂點(diǎn)覆蓋問題的求解　30　
3.1　基本概念　30　
3.2　邊加權(quán)打分策略　32　
3.3　初始化過程　33　
3.3.1　約簡規(guī)則　34　
3.3.2　基于約簡規(guī)則的初始化方法　34　
3.4　帶有特赦準(zhǔn)則的格局檢測(cè)策略　35　
3.4.1　格局檢測(cè)策略　36　
3.4.2　基于特赦準(zhǔn)則的頂點(diǎn)選擇策略　36　
3.4.3　討論　37　
3.5　NuMWVC算法的描述　38　
3.5.1　自適應(yīng)頂點(diǎn)刪除策略　38　
3.5.2　NuMWVC算法框架　39　
3.6　實(shí)驗(yàn)分析　41　
3.6.1　基準(zhǔn)實(shí)例　41　
3.6.2　對(duì)比算法介紹　42　
3.6.3　LPI、BHOSLIB和DIMACS組實(shí)驗(yàn)結(jié)果　43　
3.6.4　超大規(guī)模實(shí)例實(shí)驗(yàn)結(jié)果　46　
3.6.5　地圖標(biāo)注問題實(shí)例實(shí)驗(yàn)結(jié)果　52　
3.6.6　參數(shù)設(shè)置　54　
3.6.7　討論　57　
3.7　本章小結(jié)　59　
第4章　泛化頂點(diǎn)覆蓋問題的求解　60　
4.1　基本概念　60　
4.2　打分函數(shù)　63　
4.3　模因算法求解GVCP　64　
4.3.1　種群初始化過程　65　
4.3.2　交叉操作　67　
4.3.3　迭代鄰域搜索　68　
4.4　實(shí)驗(yàn)分析　71　
4.4.1　基準(zhǔn)實(shí)例　71　
4.4.2　對(duì)比算法和實(shí)驗(yàn)環(huán)境　73　
4.4.3　實(shí)驗(yàn)結(jié)果　74　
4.5　本章小結(jié)　83　
第5章　*小分區(qū)頂點(diǎn)覆蓋問題的求解　84　
5.1　基本概念　84　
5.2　模擬退火算法求解P-MVC問題　87　
5.3　隨機(jī)局部搜索算法　88　
5.3.1　打分策略　89　
5.3.2　邊加權(quán)策略　89　
5.3.3　兩階段交換策略　90　
5.3.4　格局檢測(cè)策略　90　
5.3.5　P-VCSLS算法框架　91　
5.4　實(shí)驗(yàn)分析　93　
5.4.1　基準(zhǔn)實(shí)例　93　
5.4.2　實(shí)驗(yàn)結(jié)果　93　
5.5　本章小結(jié)　108　
第6章　總結(jié)　109　
參考文獻(xiàn)　111