算法设计与分析

本书共8章，主要从算法的分析与设计两个方面进行介绍。首先，系统地介绍了算法分析的基本方法，包括非递归算法和递归算法，并详细介绍了Master定理。然后，系统地介绍了各种算法设计策略，包括分治策略、动态规划算法、贪心算法、回溯法、分支限界法、线性规划与网络流等。对于每种算法设计策略，从该策略的基本思想、适用问题、算法步骤或框架、应用范例等多个方面详细讲解，对于复杂的算法设计策略还给出了相关例题。书中包含大量的范例和对应的实现代码，让读者对算法设计策略的基本思想和核心设计步骤有深入的理解与掌握，能够让读者掌握各种算法设计策略的精髓，能够提高读者的算法设计能力，能够让读者具备分析具体问题、选择算法设计策略、给出算法代码的能力。 本书主要作为普通高校教材，适用于计算机科学与技术相关专业的本科和研究生阶段的教材，也可以作为从事实际问题求解的研究工作者的入门教材。

汪国华，博士，教授，博士生导师，东北林业大学。《算法设计与分析》课程组负责人，主持校教育教学研究项目1项。该课程已经评为了校一流在线课程，并获得了校《优秀研究生教材建设》项目。目前担任东北林业大学信息与计算机工程学院院长，一直致力于人工智能、大数据领域与生命、林学、其他工科领域的多学科交叉的教育模式探索。科研方向是人工智能和生物信息学，主要是利用海量生物高通量数据进行基因组组装与比对算法设计、疾病调控机制、单细胞分类模型研究。作为负责人主持国家863项目1项，863子课题项目1项，国家自然科学基金3项等。2013年入选教育部“新世纪优秀人才支持计划”，2014年入选国家博士后基金会百名博士后国际交流计划派出项目。2011年博士学位论文获得中国计算机学会“2011CCF优秀博士学位论文奖提名”。 李艳娟，女，博士，副教授，硕士生导师，现任衢州学院电气与信息工程学院教师。中国计算机学会（CCF）会员，生物信息学专委会委员。 主要从事生物信息学，机器学习等研究。主持国家自然科学基金1项，主持省级项目2项，主持中央高校基金4项，作为主要成员参与863项目、国家自然科学基金、省级项目6项。以第一作者或通讯作者发表论文20多篇，其中SCI、EI检索18篇。出版教材5部，授权专利12项，计算机软件著作权9项。 先后承担数据机构，算法设计与分析，计算机图形学等课程主讲工作。

第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