頂點覆蓋問題的求解算法研究

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