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

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

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

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

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

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

5 算法理论：复杂性 时间复杂性（算法可行性与扩展性）：
算法运行时间的快慢； 与输入数据规模有关； 上界：函数 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 多项式与非多项式；

6 算法理论：复杂性 例：排序问题： 多项式时间与指数时间： 遍历排序 ：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！ 10158 4*102567

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

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

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

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

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

12 算法理论：复杂性 第一个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多个；

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

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

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

16 组合最优化问题：集合覆盖问题 例：有 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

17 组合最优化问题：集合覆盖问题 无权集合覆盖的贪婪算法 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 中删除；

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

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

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

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

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

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

24 THE END！