第1章　算法概述 ································· 1 1.1　引言·············································· 3 1.2　算法的概念····································· 4 1.3　算法復雜性分析······························· 8 1.4　本章小結······································· 16 習題···················································· 17 第2章　遞歸與分治策略 ······················19 2.1　遞歸············································· 22 2.2　分治策略······································· 28 2.3　分治法求解查找問題························ 30 2.4　分治法求解排序問題························ 33 2.5　分治法求解復雜計算問題·················· 38 2.6　分治法求解組合問題························ 51 2.7　本章小結······································· 55 習題···················································· 56 第3章　動態(tài)規(guī)劃算法··························59 3.1　動態(tài)規(guī)劃的基本概念························ 62 3.2　備忘錄方法···································· 64 3.3 動態(tài)規(guī)劃算法的總體設計思想和 基本要素······································· 65 3.4　矩陣連乘問題································· 67 3.5　最長公共子序列問題························ 74 3.6 0-1背包問題 ·································· 80 3.7　最大子段和問題······························ 83 3.8　凸多邊形最優(yōu)三角剖分····················· 88 3.9　本章小結······································· 90 習題···················································· 91 第4章　貪心算法 ································94 4.1　生活中的貪心算法··························· 96 4.2　貪心算法的基本思想························ 98 4.3　活動安排問題································100 4.4　最優(yōu)裝載問題································104 4.5　哈夫曼編碼···································108 4.6　貪心算法的正確性驗證····················116 4.7　本章小結······································117 習題···················································117 第5章　回溯法·································· 120 5.1　回溯法的基本思想··························122 5.2　回溯法的算法框架··························123 5.3　裝載問題······································127 5.4　批處理作業(yè)調(diào)度問題·······················130 5.5　符號三角形問題·····························133 5.6 0-1背包問題 ·································135 5.7　最大團問題···································138 5.8　旅行商問題···································141 5.9　連續(xù)郵資問題································145 5.10　回溯法的效率分析 ························148 5.11　本章小結·····································149 習題···················································149 第6章　分支限界法··························· 154 6.1　分支限界法的基本思想····················157 6.2　裝載問題······································161 6.3　布線問題······································171 6.4 0-1背包問題 ·································177 目　　錄 算法設計與分析（文前+1-4）.indd 7 2022/3/9 15:25:03 算法設計與分析 VIII 6.5　最大團問題···································182 6.6　旅行商問題···································185 6.7　本章小結······································189 習題···················································190 第7章　隨機算法 ······························ 193 7.1　隨機算法的設計思想·······················196 7.2　隨機數(shù)發(fā)生器································197 7.3　數(shù)值隨機算法································199 7.4　舍伍德算法···································200 7.5　拉斯維加斯算法·····························203 7.6　蒙特卡羅算法································208 7.7　本章小結······································210 習題···················································210 第8章　線性規(guī)劃與網(wǎng)絡流················· 212 8.1　線性規(guī)劃概述································215 8.2　單純形法的設計思想與步驟··············221 8.3　單純形法的描述與分析····················232 8.4　網(wǎng)絡最大流問題·····························235 8.5　最小費用流問題·····························244 8.6　本章小結······································257 習題···················································257 參考文獻 ·········································· 261