内容简介

本书是中国大学MOOC、智慧树和学银在线精品课程配套教材，也是工科联盟和专业课程配套教材。 本书以问题求解为主线，介绍问题求解的方法与优化技巧，分为算法与问题、算法分析、算法设计、问题复杂与求解、图算法6部分。算法与问题着重介绍问题求解过程和问题变换； 算法分析主要介绍算法复杂度、复杂度分析与比较方法、时空均衡； 算法设计主要介绍枚举算法、贪心算法、递推算法、分治算法、动态规划算法、回溯算法、分支限界、网络流算法策略与优化方法； 问题复杂与求解主要介绍问题复杂分类、NP问题证明与求解策略、算法似算法等； 图算法介绍结图的可图、连通图、可行遍和平面图问题。 本书提供了大量热点问题、应用实例和常用算法，每章均附有POJ配套编程实践题、思考题和习题。全书配套微课、PPT、知识梳理、章节测验、实践作业、在线题库和文档资源。 本书适合作为高等院校计算机科学与技术、软件工程、人工智能、信息、信息与计算、金融信息化、金融大数据、数字媒体与技术类专业高年级本科生、研究生的教材，也可作为ACM竞赛培训和成人教育自学教材，同时可供程序设计开发人员、广大科技工作者和研究人员参考。

目录

目录第1章算法与问题1.1稳定匹配问题1.1.1问题分析1.1.2稳定匹配算法1.1.3正确证明1.1.4算法实现1.1.5算结本节思考题1.2算法概述1.2.1算法的概念1.2.2算法的质1.2.3算法与程序1.2.4算法与问题1.2.5问题求解本节思考题1.3问题变换1.3.1大学入学申请1.3.2问题变换本节思考题本章习题第2章算法分析2.1算法分析概述2.1.1算法选择2.1.2分析方法2.1.3有效算法2.1.4事后统计2.1.5算法分结2.2复杂度2.2.1上界2.2.2下界2.2.3紧界2.2.4高阶和低阶2.2.5质2.3复杂度比较2.3.1阶的高低2.3.2比较方法2.4实例分析2.4.1非递归算法分析2.4.2分析实例本节思考题2.5时空均衡2.5.1空间复杂度2.5.2预处理2.5.3预构造2.5.4图的遍历本节思考题本章习题第3章枚举算法3.1枚举与优化3.1.1蛮力算法3.1.2枚举算法概述3.1.3枚举优化本节思考题3.2组合与排列3.2.1排列3.2.2子集本节思考题本章习题第4章贪心算法4.1概述4.1.1部分问题4.1.2贪心算法概述本节思考题4.2基本要素4.2.1质4.2.2优解证明4.2.3预处理技巧本节思考题4.3区间问题4.3.1区间调度问题4.3.2区间划分问题4.3.3区间选点问题4.3.4区间覆盖问题4.4MST问题4.4.1MST特4.4.2Prim算法4.4.3Kruskal算法4.4.4逆删除算法4.4.5MST本节思考题4.5哈夫曼编码4.5.1哈夫曼算法4.5.2木板问题本节思考题本章习题第5章递推算法5.1递推算法概述5.1.1递推5.1.2递推与递归5.1.3递推与循环5.1.4递归与非递归5.1.5切分问题5.1.6狱吏问题本节思考题5.2倒推算法5.2.1倒推与应用5.2.2约瑟夫问题本节思考题5.3递推求解5.3.1快速排序5.3.2递推方程求解本节思考题本章习题第6章分治算法6.1分治算法概述6.1.1设计思想6.1.2合并排序 6.1.3基本特点本节思考题6.2分治类型6.2.1不相似分治6.2.2不独立分治6.2.3三分法6.2.4减治法6.2.5排序算法本节思考题6.3减少子问题个数6.3.1二分搜索6.3.2大整数乘法6.3.3Strassen矩阵乘法6.4改进分治均衡度6.4.1快速排序6.4.2线时间选择本节思考题6.5减少分解合并时间6.5.1点对问题6.5.2计数逆序问题本节思考题本章习题第7章动态规划算法7.1动态规划7.1.1兔子序列7.1.2赋权区间调度问题7.1.3基本质7.1.4求解步骤本节思考题7.2决策与递推关系7.2.1数字三角形 7.2.2多阶段决策与递推关系本节思考题7.3问题7.3.101问题7.3.2恰好装满7.3.37.3.4多重7.3.5混合本节思考题7.4区间动态规划7.4.1矩阵相乘7.4.2矩阵连乘7.5DAG动态规划7.5.1拓扑排序7.5.2嵌套矩形7.5.3长不降子序列7.5.4硬币问题7.6树图动态规划7.6.1短路径问题7.6.2FloydWarshall算法7.6.3树状动态规划本节思考题7.7序列相似度7.7.1LCS问题7.7.2序列比对7.7.3动态规划复杂度本节思考题本章习题第8章回溯算法8.1装载问题 8.1.1装载问题分析8.1.2装载问题的回溯算法8.2旅行商问题 8.2.1旅行商问题分析8.2.2旅行商问题的回溯算法本节思考题8.3基本特征8.3.1解题步骤8.3.2回溯方式8.3.3解空间结构8.3.4算法效率8.401问题8.4.101问题的回溯算法8.4.2改进上界函数8.5n皇后问题8.5.1n皇后问题分析8.5.2n皇后问题的回溯算法8.6效率改进与估计8.6.1效率估计8.6.2效率改进8.6.3适用条件本章习题第9章分支限界9.101问题9.1.101问题的队列式分支限界9.1.201问题的优先队列式分支限界9.1.301问题的优先级改进9.2旅行商问题9.2.1旅行商问题的优先队列式分支限界9.2.2旅行商问题的优先级改进本节思考题9.3分支限界9.3.1分支限界方式9.3.2分支限界与回溯算法9.3.3剪枝函数9.3.4双向广度搜索9.4算结本章习题第10章网络流算法10.1大流和小割10.1.1大流10.1.2小割10.1.3大流算法10.2大流算法改进10.2.1容量缩放算法10.2.2短增广路算法本节思考题10.3预流推进算法10.4大流算法推广10.4.1多源点多汇点问题10.4.2无向图的大流问题10.4.3顶点容量限制问题10.4.4带需求的流通问题10.4.5带需求和下界的流通10.4.6调查设计10.5小费用流10.5.1小费用路算法10.5.2小逃逸问题10.6二分测试与二分匹配10.6.1二分测试10.6.2二分匹配10.6.3网络流算法10.6.4匈牙利算法10.7应用实例10.7.1二分匹配公式10.7.2二分匹配应用本节思考题10.8二分图佳匹配本章习题第11章算法11.1算法概述11.1.1确定算法和算法11.1.2算法分类11.1.3伪数11.1.4模运算11.2数值算法11.2.1计算π值11.2.2计算定积分11.3舍伍德算法11.3.1快速排序算法11.3.2选择算法11.3.3洗牌算法11.3.4搜索有序表11.4拉斯维加斯算法11.5蒙特卡罗算法11.5.1主元素问题11.5.2素数检测本节思考题本章习题第12章计算复杂12.1P与NP12.1.1易解与难解问题12.1.2判定与优化问题12.1.3计算模型12.1.4P类12.1.5NP类12.1.6COOK归约与KARP归约12.1.7多项式时间变换本节思考题12.2NP问题12.2.1NP12.2.2COOK定理12.3NP问题证明12.3.1局部替换12.3.2分支设计技术12.3.3限制技术本节思考题12.4NP问题求解12.4.1求解策略12.4.2子问题求解12.4.3参数化算法12.4.4图着色问题12.5coNP和PSPACE12.5.1coNP12.5.2PSPACE本章习题第13似算法13.1似算法13.2相似算法13.2.1相似算法概述13.2.2贪似13.2.3组合技术13.2.4定价法13.2.5线规划与舍入本节思考题13.3多项式时似方案13.3.101问题似算法13.3.201问题的多项式时似方案 13.3.301问题的多项式时似方案本节思考题本章习题第14章图算法14.1基本概念14.1.1无向图与有向图14.1.2握手定理14.1.3图的表示14.1.4路径14.1.5赋权图14.2可图14.2.1可图概述14.2.2图的同构14.3图的遍历14.3.1深度优先搜索14.3.2广度优先搜索14.4无向连通图14.4.1无向连通图概述14.4.2生成树14.4.3图的连通度14.4.4割点与桥14.4.5双连通分量14.4.6点连通度14.4.7边连通度14.5有向连通图14.5.1有向连通图概述14.5.2强连通分量14.5.3拓扑排序14.5.4传递14.6可行遍14.6.1无向欧拉图14.6.2有向欧拉图14.6.3欧拉图判定14.6.4欧拉回路14.6.5哈密顿图本节思考题14.7平面图14.7.1平面图概述14.7.2图着色问题14.7.3图着色算法14.7.4图的转化本节思考题本章习题参考文献