高级算法电子书

前言

第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.2 0-1整数规划

1.6 原始-对偶算法（Primal-Dual Algorithm）

1.7 原始-对偶算法的应用：顶点覆盖

1.8 本章小结

第2章 高级图算法

2.1 最大流问题

2.1.1 Ford-Fulkerson算法

2.1.2 最大流最小割定理

2.1.3 Edmonds-Karp算法

2.1.4 对偶性质∗

2.2 图的中心性算法

2.2.1 度中心性

2.2.2 紧密中心性

2.2.3 中介中心性∗

2.2.4 特征向量中心性

2.2.5 PageRank

2.3 社群发现算法（Community Detection Algorithms）

2.3.1 基于模块度的算法

2.3.2 基于标签传播的算法

2.3.3 基于团的算法

2.4 社群发现在物流仓储中的应用

2.5 本章小结

第3章 NP问题

3.1 基本概念

3.1.1 P问题、NP问题、NP难问题和NPC问题

3.1.2 归约性

3.2 P问题的证明

3.3 3CNF可满足性问题

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.1 2CNF-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.1 2-opt算法

7.2.2 3-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 本章小结

参考文献