算法設計與分析

第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章　動態規劃算法··························59
3.1　動態規劃的基本概念························ 62
3.2　備忘錄方法···································· 64
3.3 動態規劃算法的總體設計思想和
基本要素······································· 65
3.4　矩陣連乘問題································· 67
3.5　 長公共子序列問題························ 74
3.6 0-1背包問題 ·································· 80
3.7　 子段和問題······························ 83
3.8　凸多邊形 三角剖分····················· 88
3.9　本章小結······································· 90
習題···················································· 91

第4章　貪心算法 ································94
4.1　生活中的貪心算法··························· 96
4.2　貪心算法的基本思想························ 98
4.3　活動安排問題································100
4.4　 裝載問題································104
4.5　哈夫曼編碼···································108
4.6　貪心算法的正確性驗證····················116
4.7　本章小結······································117
習題···················································117

第5章　回溯法·································· 120
5.1　回溯法的基本思想··························122
5.2　回溯法的算法框架··························123
5.3　裝載問題······································127
5.4　批次處理作業調度問題·······················130
5.5　符號三角形問題·····························133
5.6 0-1背包問題 ·································135
5.7　 團問題···································138
5.8　旅行商問題···································141
5.9　連續郵資問題································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　隨機數發生器································197
7.3　數值隨機算法································199
7.4　舍伍德算法···································200
7.5　拉斯維加斯算法·····························203
7.6　蒙特卡羅算法································208
7.7　本章小結······································210
習題···················································210

第8章　線性規劃與網路流················· 212
8.1　線性規劃概述································215
8.2　單純形法的設計思想與步驟··············221
8.3　單純形法的描述與分析····················232
8.4　網路 流問題·····························235
8.5　 小費用流問題·····························244
8.6　本章小結······································257
習題···················································257

參考文獻 ·········································· 261

汪國華，博士，教授，博士生導師，東北林業大學。《算法設計與分析》課程組負責人，主持校教育教學研究專案1項。該課程已經評為了校線上課程，並獲得了校《研究生教材建設》專案。目前擔任東北林業大學資訊與電腦工程學院院長，一直致力於人工智慧、大數據領域與生命、林學、其他工科領域的多學科交叉的教育模式探索。科研方向是人工智慧和生物資訊學，主要是利用海量生物高通量數據進行基因組組裝與比對算法設計、疾病調控機制、單細胞分類模型研究。作為負責人主持863專案1項，863子課題專案1項，自然科學基金3項等。2013年入選“新世紀人才支持計畫”，2014年入選博士後基金會百名博士後交流計畫派出專案。2011年博士學位論文獲得中國電腦學會“2011CCF博士學位論文獎提名”。
 
李豔娟，女，博士，副教授，碩士生導師，現任衢州學院電氣與資訊工程學院教師。中國電腦學會（CCF）會員，生物資訊學專委會委員。主要從事生物資訊學，機器學習等研究。主持自然科學基金1項，主持省級專案2項，主持中央高校基金4項，作為主要成員參與863專案、自然科學基金、省級專案6項。以作者或通訊作者發表論文20多篇，其中SCI、EI檢索18篇。出版教材5部，授權專利12項，電腦軟體著作權9項。先後承擔數據機構，算法設計與分析，電腦圖形學等課程主講工作。