运筹学2.ppt.ppt

数学文化之运筹学 刘丙强 山东大学数学学院 知新楼B835;bingqiangsdu@ 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 10 100 1000 nlogn 33 664 9966 n3 103 106 109 2n 1024 1.27*1030 1.05*10301 n！ 3628800 10158 4*102567 算法理论 图灵（Alan Mathison Turing，1912-1954） 数学家、逻辑学家、密码学家，被称为计算机科学之父、人工智能之父； 师从数学家哈代； 二战中有巨大贡献； 图灵机； 图灵奖： 姚期智（2000） * 算法理论：复杂性 图灵机与判定性问题： 判定性问题：用“是”和“否”回答的问题。 确定性图灵机； 非确定性图灵机；（带神谕的图灵机） * 有限状态控制器 1 1 1 1 1 1 0 0 0 0 0 0 0 B B B 1 …… …… 算法理论：复杂性 P 与 NP 问题： P：所有可以用确定性图灵机在多项式时间内求解的判定问题。 NP：所有可以用非确定性图灵机在多项式时间内求解的判定问题。 通俗定义： P：存在多项式时间算法的判定问题。 NP：多项式时间内可以验证的判定问题。 P 属于 NP； P =？NP 2000年巴黎法兰西学院宣布：对七个“千僖年数学难题”每一个悬赏一百万美元。P =？NP为第一个难题。 * 算法理论：复杂性 如何比较难易？ Karp归约（1972）：问题 A 多项式时间内转化为问题 B 的特殊情况，则称 A 可多项式归约于 B，记为 转化时间为多项式； 对于 A 的输入 I 的回答与其对应的 B 的输入 f(I) 一致； 例：TSP 归约为整数规划 * 算法理论：复杂性 NPC（NP完全）问题：NP 中最难的问题； ； 可满足问题 (Satisfiability Problem,SAT)； Cook（1971）证明了SAT问题为 NPC 问题。 SAT： 布尔变量集合： 布尔式： ，形如 问是否存在 的赋值使得 f = 1； 计算复杂度：O(2n)； NP-hard 问题：与NPC一样难或者更难的问题； * 算法理论：复杂性 第一个NP完全问题（Cook定理 1971） 可满足问题 （SAT）是NP完全问题 六个NP完全问题（Karp 19