计算机算法基础2.pdf

计算机算法基础 (2014.9) 何琨 brooklet60@ 华中科技大学计算机学院 2014/10/23 算法：求解问题的一组规则 检索问题 分治策略 排序问题 发现 贪心策略 路径问题 规则的设计 设计策略 动态规划 最优化问题 指导 检索与周游 遍历问题 回溯与分支限界 … …. 形成算法 产生算法设计的指 导思想和基本规律 第二章 分治法（Divide and Conquer) —— “分”而治之  2.1 一般方法  2.2 二分检索  2.3 找最大最小元素  2.6 选择问题  2.7 Strassen矩阵乘法 注： 2.4 归并分类 2.5 快速分类 不讲 第二章 分治法（Divide and Conquer) —— “分”而治之  2.1 一般方法  2.2 二分检索  2.3 找最大最小元素  2.6 选择问题  2.7 Strassen矩阵乘法 1. 基本思想 一个难以直接解决的、规模较大问题  若干个规模较小、较容易解决的、性质相同的子问题  分别解决这些子问题  合并子问题的解从而得到原问题的解 注意：子问题是相互独立的，否则存在重复计算 常见的二分法 规模为n 的问题 规模为 n/2 的子问题1 规模为 n/2 的子问题2 子问题1的解 子问题2 的解 原始问题的解 2. 分治策略的抽象化控制过程——二分策略 算法2.1 分治策略的抽象化控制 注： procedure DANDC(p,q)  k=2: 二分是最常用的分解策略； global n,A(1:n);  SMALL(p,q)：布尔函数，判断输 入规模q-p+1是否足够小而无需再 integer m,p,q; //1≤p≤q≤n// 进一步分就可求解； if SMALL(p,q)  G(p,q)： 当SMALL(p,q)为真时， then return(G(p,q)) 对输入规模为q-p+1的子问题求解； else  DIVIDE(p.q)：当规模q-p+1还较 m←DIVIDE(p,q) //p≤m＜q// 大时，对规模为q-p+1的子问题进 return(COMBINE(DANDC(p,m), 一步分解，返回值为[p,q]区间进