局部搜索算法及其在組合優(yōu)化問題中的應用

目錄
叢書序
前言
第1章 緒論 1
1.1 組合優(yōu)化問題 1
1.2 組合優(yōu)化問題的求解方法 2
1.2.1 精確算法 2
1.2.2 啟發(fā)式算法 2
1.2.3 兩類算法的優(yōu)缺點 3
1.3 相關工作 4
1.3.1 最小加權(quán)頂點覆蓋問題 4
1.3.2 最小有容量支配集問題 6
1.3.3 最小連通支配集問題 7
1.3.4 頂點覆蓋與支配集之間的關系 9
1.4 本書的研究內(nèi)容和貢獻 11
第2章 局部搜索算法 13
2.1 局部搜索概述 13
2.2 基本概念 14
2.3 局部搜索算法簡介 16
2.4 局部搜索算法的核心技術(shù) 22
2.5 本章小結(jié) 24
第3章 最小加權(quán)頂點覆蓋問題求解 26
3.1 基本符號和定義 26
3.2 基于動態(tài)邊權(quán)的打分策略 28
3.2.1 動態(tài)邊權(quán) 29
3.2.2 打分策略 29
3.2.3 快速增量評估技術(shù) 30
3.3 加權(quán)格局檢測策略 32
3.4 頂點選擇策略 34
3.5 DLSWCC算法的描述 35
3.6 實驗分析 38
3.6.1 基準實例 38
3.6.2 現(xiàn)有算法介紹 40
3.6.3 加權(quán)格局檢測策略的有效性 41
3.6.4 動態(tài)打分策略的有效性 43
3.6.5 快速增量評估技術(shù)的有效性 45
3.6.6 SPI組實例實驗結(jié)果 46
3.6.7 MPI組實例實驗結(jié)果 49
3.6.8 LPI組實例實驗結(jié)果 52
3.6.9 MGI組實例實驗結(jié)果 54
3.7 本章小結(jié) 56
第4章 最小有容量支配集問題求解 58
4.1 基本概念 58
4.2 基于頂點懲罰的打分策略 61
4.2.1 頂點懲罰策略 61
4.2.2 頂點打分策略 62
4.2.3 頂點選擇方法 62
4.3 兩種模式的被支配頂點選擇策略 64
4.4 強化策略 66
4.5 LS_PD算法的描述 67
4.6 實驗分析 69
4.6.1 基準實例 69
4.6.2 現(xiàn)有算法介紹 70
4.6.3 固定容量的實驗結(jié)果 71
4.6.4 變化容量的實驗結(jié)果 74
4.6.5 討論 78
4.7 本章小結(jié) 81
第5章 最小連通支配集問題求解 83
5.1 基本概念 83
5.2 GRASP算法框架 85
5.3 GRASP求解最小連通支配集問題 86
5.3.1 貪婪隨機構(gòu)造階段 86
5.3.2 局部搜索階段 89
5.4 實驗分析 92
5.4.1 基準實例 92
5.4.2 現(xiàn)有算法介紹 95
5.4.3 求解LPRNMR實例的實驗結(jié)果 96
5.4.4 求解隨機實例的實驗結(jié)果 97
5.4.5 求解MLSTP實例的實驗結(jié)果 99
5.5 本章小結(jié) 102
第6章 總結(jié)與展望 103
6.1 總結(jié) 103
6.2 展望 104
參考文獻 106