目 錄 第1章 算法概述 1 1.1 算法與程序 1 1.2 算法復(fù)雜性分析 1 1.3 NP完全性理論 4 算法分析題1 7 算法實(shí)現(xiàn)題1 7 第2章 遞歸與分治策略 11 2.1 遞歸的概念 11 2.2 分治法的基本思想 16 2.3 二分搜索技術(shù) 17 2.4 大整數(shù)的乘法 18 2.5 Strassen矩陣乘法 19 2.6 棋盤覆蓋 20 2.7 合并排序 22 2.8 快速排序 24 2.9 線性時(shí)間選擇 26 2.10 最接近點(diǎn)對(duì)問題 29 2.11 循環(huán)賽日程表 35 算法分析題2 36 算法實(shí)現(xiàn)題2 40 第3章 動(dòng)態(tài)規(guī)劃 46 3.1 矩陣連乘問題 47 3.2 動(dòng)態(tài)規(guī)劃算法的基本要素 51 3.3 最長(zhǎng)公共子序列 54 3.4 最大子段和 57 3.5 凸多邊形最優(yōu)三角剖分 62 3.6 多邊形游戲 65 3.7 圖像壓縮 68 3.8 電路布線 70 3.9 流水作業(yè)調(diào)度 71 3.10 0-1背包問題 74 3.11 最優(yōu)二叉搜索樹 79 算法分析題3 81 算法實(shí)現(xiàn)題3 82 第4章 貪心算法 95 4.1 活動(dòng)安排問題 95 4.2 貪心算法的基本要素 98 4.3 最優(yōu)裝載 100 4.4 哈夫曼編碼 101 4.5 單源最短路徑 105 4.6 最小生成樹 108 4.7 多機(jī)調(diào)度問題 111 算法分析題4 113 算法實(shí)現(xiàn)題4 113 第5章 回溯法 120 5.1 回溯法的算法框架 120 5.2 裝載問題 125 5.3 批處理作業(yè)調(diào)度 131 5.4 符號(hào)三角形問題 133 5.5 n后問題 135 5.6 0-1背包問題 137 5.7 最大團(tuán)問題 140 5.8 圖的m著色問題 142 5.9 旅行售貨員問題 144 5.10 圓排列問題 146 5.11 電路板排列問題 148 5.12 連續(xù)郵資問題 151 5.13 回溯法的效率分析 153 算法分析題5 155 算法實(shí)現(xiàn)題5 156 第6章 分支限界法 167 6.1 分支限界法的基本思想 167 6.2 單源最短路徑問題 170 6.3 裝載問題 172 6.4 布線問題 178 6.5 0-1背包問題 181 6.6 最大團(tuán)問題 185 6.7 旅行售貨員問題 187 6.8 電路板排列問題 190 6.9 批處理作業(yè)調(diào)度 193 算法分析題6 197 算法實(shí)現(xiàn)題6 198 第7章 隨機(jī)化算法 207 7.1 隨機(jī)數(shù) 208 7.2 數(shù)值隨機(jī)化算法 209 7.3 舍伍德算法 214 7.4 拉斯維加斯算法 225 7.5 蒙特卡羅算法 231 算法分析題7 236 算法實(shí)現(xiàn)題7 239 第8章 線性規(guī)劃與網(wǎng)絡(luò)流 243 8.1 線性規(guī)劃問題和單純形算法 243 8.2 最大網(wǎng)絡(luò)流問題 256 8.3 最小費(fèi)用流問題 274 算法分析題8 292 算法實(shí)現(xiàn)題8 293 第9章 串與序列的算法 306 9.1 子串搜索算法 306 9.2 后綴數(shù)組與最長(zhǎng)公共字串 318 9.3 序列比較算法 328 算法分析題9 336 算法實(shí)現(xiàn)題9 338 附錄A C++概要 342 參考文獻(xiàn) 349