第1章算法設計與分析基礎1
1.1算法概述2
1.1.1什麼是算法2
1.1.2學習算法的重要性6
1.2問題的求解過程6
1.2.1問題及問題的求解過程6
1.2.2算法設計與算法表示7
1.2.3算法確認和算法分析8
1.3算法的復雜性分析8
1.3.1算法評價的基本原則9
1.3.2影響程序運行時間的因素10
1.3.3算法復雜度11
1.3.4使用程序步分析算法14
1.3.5漸近表示法15
1.4算法設計中常見的重要問題類型18
1.4.1排序問題18
1.4.2查找問題19
1.4.3圖問題19
1.4.4組合問題20
1.4.5幾何問題20
1.4.6數值問題21
1.4.7其他常見問題21
1.5常用的算法設計方法22
1.5.1數值計算算法23
1.5.2非數值計算算法24
1.6小結28
練習題29
第2章遞歸算法31
2.1遞歸算法的思想32
2.1.1遞歸算法的特性32
2.1.2遞歸算法的執行過程32
2.1.3遞推關繫33
2.2遞歸法應用舉例37
2.2.1漢諾塔問題37
2.2.2斐波那契數列問題39
2.2.3八皇後問題40
2.3典型問題的C++程序43
2.4小結48
練習題48
第3章分治算法50
3.1分治算法的思想51
3.2排序問題中的分治算法52
3.2.1歸並排序53
3.2.2快速排序55
3.3查找問題中的分治算法57
3.3.1折半查找57
3.3.2選擇問題59
3.4組合問題中的分治算法60
3.4.1最大子段和問題60
3.4.2棋盤覆蓋問題62
3.5典型問題的C++程序64
3.6小結70
練習題71
第4章貪心算法72
4.1貪心算法的思想73
4.1.1問題的提出73
4.1.2貪心算法設計思想73
4.1.3貪心算法的基本要素74
4.1.4貪心算法的求解過程74
4.2組合問題中的貪心算法75
4.2.1背包問題75
4.2.2多機調度問題77
4.3圖問題中的貪心算法78
4.3.1單源最短路徑問題78
4.3.2最小代價生成樹80
4.4典型問題的C++程序84
4.5小結92
練習題92
第5章動態規劃算法94
5.1動態規劃算法的思想95
5.2查找問題中的動態規劃算法97
5.2.1最優二叉搜索樹97
5.2.2近似串匹配問題100
5.3圖問題中的動態規劃算法102
5.3.1多段圖問題102
5.3.2每對結點間的最短距離105
5.4組合問題中的動態規劃算法108
5.4.10/1背包問題108
5.4.2最長公共子序列112
5.4.3流水作業調度115
5.5典型問題的C++程序120
5.6小結125
練習題126
第6章回溯算法128
6.1回溯算法的思想129
6.1.1基本概念129
6.1.2基本思路130
6.1.3回溯算法的適用條件132
6.1.4回溯算法的效率估計132
6.2組合問題中的回溯算法133
6.2.1裝載問題133
6.2.20/1背包問題134
6.2.3n皇後問題136
6.2.4圖的m著色問題139
6.2.5子集和數問題141
6.3圖問題中的回溯算法143
6.3.1深度優先搜索143
6.3.2貨郎(TSP)問題143
6.3.3最大團(MCP)問題145
6.3.4哈密頓環問題146
6.4算法效率的影響因素及改進途徑148
6.4.1影響算法效率的因素148
6.4.2回溯算法的改進途徑148
6.5典型問題的C++程序148
6.6小結165
練習題165
第7章分支限界算法167
7.1分支限界算法的思想168
7.2求最優解的分支限界算法170
7.2.1FIFO分支限界算法171
7.2.2LC分支限界算法172
7.3組合問題中的分支限界算法173
7.3.10/1背包問題173
7.3.2帶限期的作業排序175
7.4圖問題中的分支限界算法179
7.4.1旅行商問題179
7.4.2單源點最短路徑問題182
7.5典型問題的C++程序184
7.6小結188
練習題188
附錄實驗指導190
實驗一遞歸與分治算法191
1.1實驗目的與要求191
1.2實驗課時191
1.3實驗原理191
1.4實驗題目191
1.5思考題192
實驗二貪心算法192
2.1實驗目的與要求192
2.2實驗課時192
2.3實驗原理192
2.4實驗題目193
2.5思考題194
實驗三動態規劃算法194
3.1實驗目的與要求194
3.2實驗課時195
3.3實驗原理195
3.4實驗題目195
3.5思考題197
實驗四回溯算法197
4.1實驗目的與要求197
4.2實驗課時197
4.3實驗原理197
4.4實驗題目198
4.5思考題199
實驗五分支限界算法199
5.1實驗目的與要求199
5.2實驗課時200
5.3實驗原理200
5.4實驗題目200
5.5思考題203
參考文獻204