刘丙强 山东大学数学学院 知新楼B835; 88363455 bingqiangsdu@gmail.com 2013-11-13 (2) 数学文化之运筹学 刘丙强 山东大学数学学院 知新楼B835; 88363455 bingqiangsdu@gmail.com 2013-11-13 (2)

运筹学理论内容： 数 学 规 划 线性规划 整数规划 非线性规划 内 容 组 合 优 化 图与网络 网络优化 算法分析 算法复杂性 近似算法

组合优化综述 组合最优化：解决离散结构上的优化问题； 主要包括： 本节内容： 组合数学； 数学规划（线性规划）； 算法理论与方法； 图论中的优化问题； 本节内容： 组合优化化问题与算法； 算法复杂性； 近似算法

算法理论 算法：解决问题的步骤； 计算机与算法； 算法思想： 输入与输出； 流程与语言； 复杂性：时间、空间复杂性； 准确性的衡量； 精确算法； 贪婪算法； 启发式算法； 近似算法； 确定性算法、非确定性算法；

算法理论：复杂性 时间复杂性（算法可行性与扩展性）： 算法运行时间的快慢； 与输入数据规模有关； 上界：函数 f(n) 和 g(n) 都是整数到正实数的函数，如果存在正 整数 n0 和正常数 c，使得对所有 n ≥ n0 ，都有 f(n) ≤ cg(n)，就 称 f(n) 的阶至多是 O(g(n))。 下界：函数 f(n) 和 g(n) 都是整数到正实数的函数，如果存在正 整数 n0 和正常数 c，使得对所有 n ≥ n0 ，都有 f(n) > cg(n)，就 称 f(n) 的阶至少是 Ω (g(n))。 准确界：函数 f(n) 和 g(n) 都是整数到正实数的函数，如果存在 正整数 n0 和正常数 c1 和 c2 ( c1 ≤ c2 )，使得对所有 n ≥ n0 ，都有 c1 g(n) ≤ f(n) ≤ c2 g(n)，就称 f(n) 的阶至多是 Θ (g(n))。 1 ≺ loglogn ≺ logn ≺ n1/2 ≺ n3/4 ≺n ≺ nlogn ≺ n2 ≺ 2n ≺ n!≺ 2n^2 多项式与非多项式；

算法理论：复杂性 例：排序问题： 多项式时间与指数时间： 遍历排序 ：O(n2)； 分组排序：O(nlogn)； 计算量 规模 n 的近似值 10 100 1000 n nlogn 33 664 9966 n3 103 106 109 2n 1024 1.27*1030 1.05*10301 n！ 3628800 10158 4*102567

It isn‘t true, but God, we wish it was！ 算法理论 图灵（Alan Mathison Turing，1912-1954） 数学家、逻辑学家、密码学家，被称为计算机科学之父、人工智能之父； 师从数学家哈代； 二战中有巨大贡献； 图灵机； 图灵奖： 姚期智（2000） It isn‘t true, but God, we wish it was！

算法理论：复杂性 图灵机与判定性问题： 判定性问题：用“是”和“否”回答的问题。 确定性图灵机； 非确定性图灵机；（带神谕的图灵机） 有限状态控制器 1 B ……

算法理论：复杂性 P 与 NP 问题： 通俗定义： P 属于 NP； P =？NP P：所有可以用确定性图灵机在多项式时间内求解的判定问题。

算法理论：复杂性 如何比较难易？ Karp归约（1972）：问题 A 多项式时间内转化为问 题 B 的特殊情况，则称 A 可多项式归约于 B，记为 转化时间为多项式； 对于 A 的输入 I 的回答与其对应的 B 的输入 f(I) 一致； 例：TSP 归约为整数规划

算法理论：复杂性 NPC（NP完全）问题：NP 中最难的问题； SAT： NP-hard 问题：与NPC一样难或者更难的问题； ； 可满足问题 (Satisfiability Problem,SAT)； Cook（1971）证明了SAT问题为 NPC 问题。 SAT： 布尔变量集合： 布尔式： ，形如 问是否存在 的赋值使得 f = 1； 计算复杂度：O(2n)； NP-hard 问题：与NPC一样难或者更难的问题；

算法理论：复杂性 第一个NP完全问题（Cook定理 1971） 六个NP完全问题（Karp 1972) 更多的NP完全问题 可满足问题 （SAT）是NP完全问题 六个NP完全问题（Karp 1972) 3可满足问题：3SAT； 图的点覆盖问题：VC； 图的 k 点团存在性问题：Clique； 图的哈密尔顿圈问题：HC；TSP简化版； 正整数集合的划分问题；背包问题简化版； 三维匹配问题： 3DM； 更多的NP完全问题 1979年：300多个； 1998年：2000多个；

P=NP 算法理论：复杂性 P=?NP （P-NP问题）； 如果 ，则指数灾难无法避免； P 与 NPC 之外的 NP 问题，曾经的希望： 如果 ，则指数灾难无法避免； P 与 NPC 之外的 NP 问题，曾经的希望： 线性规划问题；图的同构问题；素数判定问题； P=NP NP NP NPC P

算法理论：复杂性 如何处理 NP 难问题？ 并行计算：以硬件设备换取时间 随机算法： 存在着很多种并行计算模型 理想模型 PRAM 可多项式时间解NP完全问题 实际中效果不好：处理器数目是受限的，现实的代价：通讯，同步，等； 随机算法： 判定问题： 以较大概率得到正确输出； 输出正确，但计算时间不定； 优化问题：输出解的性能不稳定； 以较大概率得到性能好的解；

算法理论：复杂性 近似算法： 启发式算法： 模拟退火、遗传算法、人工神经网络、蚁群算法等； 不要最优，只求较优； 时间复杂度较低； 结果符合某种保证； 启发式算法： 基于直观或经验构造的算法，在可接受的代价下给出待解决问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计 ； 通常利用邻域进行局部优化：邻域搜索； 贪婪策略通常也属于启发式算法； 模拟退火、遗传算法、人工神经网络、蚁群算法等；

组合最优化问题：集合覆盖问题 例：有 n 个菌株 V = {v1, v2, …, vn }，m 种药物每种可以 抑制菌株集合为 S1, S2, …, Sm，成本分别为 w1, w2, …, wm ， 求可以抑制所有菌株的成本最小的药物组合。 集合覆盖（Set Cover）： 输入： 集合 V = {v1, v2, …, vn }; 子集 S1, S2, …, Sm 属于 V； 权重 w1, w2, …, wm 、或无权； 目标： 选出 {1, 2, …, m}的子集 I， 需要满足 ；同时 最小化 或 |I |； V = {v1, v2, …, vn }; Sj

组合最优化问题：集合覆盖问题 无权集合覆盖的贪婪算法 1： 算法 1为 f 近似算法（f 为 vi 所属子集的个数的最大值）； 2. 当 V 非空的时候，任选 vi，将所有包含 vi 的集合 Sj 的序号并入 I；然后将所有涉及到的 vi 从 V 中删除； 3. 如果 V 为空集，则停止，输出 I。 算法 1为 f 近似算法（f 为 vi 所属子集的个数的最大值）； f 较小时效果尚可：每个菌株被少数药物抑制； 无权集合覆盖的贪婪算法 2： 2. 当 V 非空的时候，将包含未覆盖的 vi 最多的集合 Sj 的序号并入 I；然后将新覆盖到的 vi 从 V 中删除；

组合最优化问题：集合覆盖问题 利用线性规划的凑整算法（Rounding） 凑整算法为 f 近似算法： xj = 0, 1 代表是否选取 Sj； xj 松弛问题的解 ； 对 j =1, …, m 执行： 输出 凑整算法为 f 近似算法：

组合最优化问题：集合覆盖问题 贪婪算法； 线性规划取整算法； 对偶规划算法； 原对偶规划算法； 加权集合覆盖的贪婪算法； 问题推广： 抑制关系的强弱（元素与集合从属关系加权）； 药物拮抗性（集合选择时考虑互斥）； 放松要求（尽可能多的抑制细菌，不要求全部）；

组合最优化问题：背包问题 背包问题（Knapsake）： 物体集合 U={u1, u2, …, un}, 其体积分别为整数s1, s2, …, sn , 价值分别为整数 v1, v2, …, vn , 背包容量为整数 C，求U的一个子集 S（装背包的方案）使得： 同为 NP-hard问题； 考虑近似算法等； 松弛为 LP 分数形式；

组合最优化问题：背包问题 背包问题的贪婪算法1： 贪婪算法2： 首先将物品按单位价值 (vi /si) 降序排列，然后按这个顺序将物品装包，直到包满或所有物品已经装完。 这个算法不能得到有界近似比： 贪婪算法2： 1/2近似算法

组合最优化问题：背包问题 贪婪算法 + 局部优化： 首先将物品按单位价值 (vi /si) 降序排列，然后按这个顺序将物品装包，直到包满或所有物品已经装完。 在上述结果基础上进行邻域优化？

组合最优化问题：装箱问题 装箱问题（Bin-packing）： 有 n 个大小分别为 s1, s2, …, sn 的物体 ui （其中每个 sj 都在 0 和 1 之间）, 要求将它们装入到最少数目的单位容积的箱子中（不考虑物体形状）。 划分问题 （Partition）： 一组正整数 (s1, s2, …, sn )，是否可以将其划分为两个集合，使得两个集合里面的数的和相等； NPC 问题； 不存在近似度 < 3/2 的近似算法； 可以直接归结为装箱问题； 装箱问题不存在近似度 < 3/2 的近似算法

THE END！