高级算法

在所有算法讲解中都贯穿了图问题，同时还专门介绍了高级图算法。 每章都给出了相关算法的应用实例。 对课堂教学进行了实录，目前录课已经发布在 B站，账号为 foretmer。 配套提供电子课件、教学大纲、微课视频、MOOC（B站）、试卷及答案。

本书的内容主要包括两个方面：一是困难问题(NPC问题)；二是人工智能的关键问题(图问题)。包括：困难问题的概念和证明；困难问题的常用模型，如线性规划和整数规划；困难问题的常用算法，如近似算法、随机算法、在线算法、启发式算法。本书在所有算法讲解中都贯穿了图问题，同时还专门介绍了高级图算法，其中，中心性算法和社群发现算法是人工智能的基础。此外，本书的每章都给出了相关算法的应用实例。
本书可作为高等院校计算机类专业的研究生算法课程的教材，也可作为各行业从事算法设计和开发技术人员的参考书。

前言
第1章线性规划
1.1基本概念
1.2标准型和松弛型
1.3单纯形法
1.3.1单纯形法原理
1.3.2单纯形法步骤
1.3.3单纯形表
1.4对偶
1.4.1什么是对偶
1.4.2对偶怎么来的
1.4.3对偶的性质
1.4.4对偶实例*
1.5整数规划
1.5.1分支限界
1.5.20-1整数规划
1.6原始-对偶算法（Primal-Dual Algorithm）
1.7原始-对偶算法的应用：顶点覆盖
1.8本章小结
第2章高级图算法
2.1最大流问题
2.1.1Ford-Fulkerson算法
2.1.2最大流最小割定理
2.1.3Edmonds-Karp算法
2.1.4对偶性质*
2.2图的中心性算法
2.2.1度中心性
2.2.2紧密中心性
2.2.3中介中心性*
2.2.4特征向量中心性
2.2.5PageRank
2.3社群发现算法（Community Detection Algorithms）
2.3.1基于模块度的算法
2.3.2基于标签传播的算法
2.3.3基于团的算法
2.4社群发现在物流仓储中的应用
2.5本章小结
第3章NP问题
3.1基本概念
3.1.1P问题、NP问题、NP难问题和NPC问题
3.1.2归约性
3.2P问题的证明
3.33CNF可满足性问题
3.4最大团问题
3.5顶点覆盖问题
3.6最大公共子图
3.7哈密顿回路*
3.8本章小结
第4章近似算法
4.1基本概念
4.2旅行商问题
4.3子集和问题
4.4集合覆盖
4.4.1简单集合覆盖
4.4.2带权重的集合覆盖（广义集合覆盖）*
4.5集合覆盖-整数规划
4.6斯坦纳最小树
4.7近似算法在作业调度中的应用
4.8本章小结
第5章随机算法
5.1基本概念
5.2避免落入最坏情形
5.2.1随机快速排序
5.2.2随机快速选择（Random Quick Select）
5.2.3最小圆覆盖
5.3降低算法复杂度
5.3.1弗里瓦德算法（Frievald’s Algorithm）
5.3.2惰性选择（Lazy Select）*
5.3.3集合覆盖
5.3.4最小割
5.4随机游走及其应用
5.4.12CNF-SAT
5.4.2图嵌入和集卡问题
5.5本章小结
第6章在线算法
6.1基本概念
6.2确定性在线算法
6.2.1在线最小生成树
6.2.2在线装箱问题*
6.2.3时间序列搜索
6.3随机在线算法
6.3.1租买问题
6.3.2在线二分图最大匹配*
6.4在线算法在物流中的应用：装车问题
6.5本章小结
第7章启发式算法
7.1基本概念
7.2局部搜索
7.2.12-opt算法
7.2.23-opt算法
7.3模拟退火
7.4禁忌搜索（Tabu Search）
7.5蚁群算法
7.5.1基础蚁群算法
7.5.2蚁群系统
7.5.3最大-最小蚁群系统
7.6遗传算法
7.6.1遗传算法概念和流程
7.6.2求解函数的最大/最小值
7.6.3旅行商问题
7.6.4遗传算法变体*
7.7遗传算法在多目标优化中的应用
7.8本章小结
参考文献