高级算法

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

林海，现任武汉大学-国家网络安全学院副教授，先后毕业于法国巴黎第六大学(硕士)和法国国立高等通信学校(博士)，并取得了计算机网络博士学位，是武汉大学作为人才引进的优秀青年学术骨干。在加入武汉大学之前，曾经先后在法国电信 Orange 研究院从事博士后研究和在中兴通讯欧洲研究所(巴黎)从事系统工程师工作。本书作者一直从事算法方面的教学和研究，有着多年本科生《算法设计与分析》和研究生《高级算法》教学经验。发表SCI论文20余篇，发明专利5项，软著1项；主持和参与国家和省级项目6项。

前言 第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本章小结 参考文献