算法201005-分治.ppt

1 两个例子：棋盘覆盖与最接近点对问题 2 减治法 3 分治法小结 第2章 分治与递归算法（3） 棋盘覆盖问题 n一个2k2k的特殊棋盘是其中含有一个特殊方格的 棋盘，如左下图为k=2的一个特殊棋盘。 n现在任意给定一个2k2k的特殊棋盘，要用右下 图所示的L型骨牌来无重叠的覆盖它。 1 11 2 22 33 3 4 44 5 在2k2k的 棋盘覆盖 中要用到 (4k1)/3个 L型骨牌。55 棋盘覆盖问题分析 n当k0时，将2k2k的棋盘分割成4个2k12k1的子 棋盘，如右下图所示： 2k12k12k12k1 2k12k12k12k1 然而，这样一来四个子棋 盘的情形就不一致了。因 为递归求解是将问题归结 到较小的规模的同一问题 ，所以就需要将三个正常 子棋盘也转化成特殊棋盘 。 为此，可以用一个L型骨 牌来覆盖其余三个子棋盘 的会合处，如左图所示。 这样原问题转化成了四个 较小规模的子问题。递归 地分割下去直至单格棋盘 。 n特殊方格必定位于4个子棋盘之一中。 棋盘覆盖算法设计 n棋盘覆盖(参数表) n n 如果是单个格子，则返回； n 将棋盘划分成尺寸为一半的子棋盘； n 判断特殊方格在哪个子棋盘中，再用相应的骨 牌覆盖相应结合部，并记下它们的位置； n 依次对左上角、右上角、左下角和右下角这四 个子棋盘进行棋盘覆盖； n n设T(k)是棋盘覆盖算法覆盖2k2k的棋盘所需要的 时间，则从算法的分治策略可知， T(k)满足如下 递归方程： 棋盘覆盖算法的复杂性 T(k) = O(1) k = 0 4T(k1) + O(1) k0 n解此递归方程可得T(k) = O(4k)。 n由于覆盖2k2k的棋盘要用 (4k1)/3个L型骨牌 ，故此算法是一个在渐进意义下最优的算法。 最接近点对问题 n给定平面上n个点，在n个点组成的所有点对中，找出 其中相互距离最小的一对点。 n此问题的简单解法是，算出每个点与其它n1 个点之 间的距离，再找出其中距离最小的一对点。这样做的 时间复杂性为O(n2)。 n下面用分治法构造一个时间复杂性为O(nlogn)的算法 。 n为此我们先考虑一维的情况： 在应用中， 常用诸如点、圆等简单的几何对象代表现实世界中 的实体。 在涉及这些几何对象的问题中， 常需要了解其邻域中其他几何对象的信息。 例如，在空中交通控制问题中， 若将飞机作为空间中移动的一个点来看待， 则具有最大碰撞危险的2架飞机， 就是这个空间中最接近的一对点。 这类问题是计算几何学中研究的基本问题之一。 一维最接近点对 n设S为x轴上n个点的集合，求S中最接近点对。 n假设用x轴上某个点m划分S为S1和S2，使得S1=xS | xm，S2=xS | xm。 n递归地在S1和S2中找出其最接近点对p1，p2和q1， q2，并设d = min|p1，p2|， |q1，q2| n易知，S中最接近点对是p1，p2或q1，q2，或 p3 ，q3，这里p3=maxS1，q3 =minS2。 m S1S2 p1p2p3q3q1 q2 一维最接近点对算法 nbool Cpair1(S, d) n n n = |S|; n if (n m n Cpair1(S1, d1); n Cpair1(S2, d2); /分别求S1和S2的最接近点对 n p=maxS1; q =minS2; d = mimd1, d2, q p; n return true n 一维最接近点对算法复杂性 n如果对S的分割不平衡的话，最坏的情况是S1仅含 一个点，这时算法的复杂性为O(n2)。 n所以要采用中位数m来分割S。 n该算法的分割步骤和合并步骤总共耗时O(n)，因 此算法耗时满足递归方程 T(n) = O(1) n0 2T(n/2) + O(n) n4 n解此递归方程可得T(n) = O(nlogn)。 平面最接近点对 n做一条直线L：x=m，将S分割为S1和S2，其中m为 所有点的x坐标的中位数。递归地求得S1和S2中的 最小距离d1和d2，令d=mind1，d2。 L S1S2 d1 d2 n但是S1和S2之间的最小距离却需要考察S1和S2 在l两侧距离不超过d的区域P1和P2间的点对。 d P1 d P2 nP1和P2间的点对均为最近点对 的候选，最坏情况有n2/4个。 n而实际上，对P1中的任意一点 ，最多只需要考察P2中的6个 点。 最多只需要考察6个点 n考虑P1中的任意一点p，它若与P2中的点q构成最 接近点对，则其距离必定小于d。这样的点必定 落在一个d2d的矩形R内： L P1P2 p d d R 在矩形R中最多有6个点。 不然的话，可以将矩形R分成6 个(d/2)(2d/3)个小矩形， 每个小矩形对角线的长度为 5d/6。(d/2)2+(2d/3)2=25d2/36 若R中有6个以上的点，则必 有两点u、v在同一小矩形内 ， 于是|uv|5d/6。矛盾。 （鸽舍原理） 所以R中至多有6个点，即对 P1中的每个点至多只需要考 察P2中的6个点就可以了。 分别将P1和P2中的点按y坐标 排序；再对P1中的每个点p， 考察P2中y坐标在y(p)d范围 内的点(最多6个)。 平面最接近点对的算法 nbool Cpair2(S, d) n n = |S|; n if (n2) d = ; return false n m = S中各点x坐标的中位数；构造S1和S2； n Cpair2(S1, d1); Cpair2(S2, d2); dm=min(d1, d2) n 构造P1和P2； n /P1=p|mdmx(p)m, P2=q|mx(q)m+dm n 将P1和P2中的点按y坐标值排序； n 依次扫描P1中点u并计算u与P2中y坐标在y(u)dm范围内 的点(最多6个)；设dl是这样找到的最小距离； n d = min(dm, dl); n return true 最接近点对算法的复杂性 n则在算法中： n计算中位数和min需时为常数。 n将S分割为S1和S2需时为O(n)。 n在排序后的P1和P2中找最小距离dl需时为O(n)。 n对P1和P2排序在最坏情况下需时O(nlogn)，这 不符合要求。 n由此易知递归需时为O(nlogn)，预排序需时为 O(nlogn)，因而整个算法需时为O(nlogn)。 n若在整个算法开始之前对各点的y坐标进行一 次预排序，则在递归中就无须再排序，只要对 P1或P2进行线性扫描即可，需时仍为O(n)。 减治与递归 俄罗斯农夫法 假定需要求的乘积，显然有 以 作为算法的终止条件。 仅减小问题 规模 例如，要求39和79的乘积，算法的运行过程如下： 39 79 19 158 +79 9 316 +158 4 632 +316 2 1264 1 2528 对整数的乘法计算是很有实际意义 减治与递归 通过建立原问题实例的解和同样问题较小实例的解的关系， 并利用这种关系，从顶而下（递归地）或从底而上（非递归 地）解决问题。 规模逐步减小，但 问题不分解 (1) 消去一个常量：每次算法迭代总是从原问题规模中减 去一个规模相同的常量（一般为1）。插入排序属于该种 方法。 三种常见形式： (2) 减去一个常数因子：从原问题的规模中减去一个相同的 常数因子，该因子一般是2。如俄罗斯农夫法 (3) 减去可变规模：规模减小的模式都是不同的。如计算 最大公约数的辗转相除法。 分治法小结 1 分治法的特点 2 可利用分治法求解得问题的特点 3 分治法的算法设计 递归算法 4 分治法的时间复杂度分析 并行算法 替换法（分治1） 实验2（2.17 选择问题）对于任意给定的n个元素的数组，要 求从中找出第k小的元素，试用分治思想求解该问题。 要求： 1） 输入：输入任意一个数组及k的取值 2）输出：第k小元素的取值，计算所需的加法和乘法次 数 3）要求具有可视用户交互界面，通过该界面实现输入及输出 4） 使用语言不限 5）提交实验报告（纸质）+源程序（实验i+学号+姓名）到 ise_ 平板电脑是PC家族新增加的一名成员，其外观和笔记本电脑 相似，但不是单纯的笔记本电脑，它可以被称为笔记本电脑 的浓缩版。其外形介于笔记本和掌上电脑之间，但其处理能 力大于掌上电脑，比之笔记本电脑，它除了拥有其所有功能 外，还支持手写输入或者语音输入，移动性和便携性都更胜 一筹。 平板电脑有两种规格，一为专用手写板，可外接键 盘、屏幕等，当作一般PC用。另一种为笔记型手写板，可象 笔记本一般开合。 哈工大2003春季 1算法分析的目的是( ) A. 找出数据结构的合理性 B.研究算法的输入/输出关系 C.分析算法的效率以求改进 D.分析算法的易读性 6深度为5的二元树至多有( )个结点。 A.16 B.32 C 31 D.10 1. 算法的计算量的大小称为计算的（ ）。【北京邮电大学2000 二、3 （20/8 分）】 A效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（ ）【中科院计算所 1998 二、1 （2分）】 A问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2） 这三个特性。 (1) A计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1（2分） 【武汉交通科技大学 1996 一、1（ 4分）】 4一个算法应该是（ ）。【中山大学 1998 二、1（2分）】 A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C. 5. 下面关于算法说法错误的是（ ）【南京理工大学 2000 一、1（1.5分）】 A算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（ ）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的 算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 11在下面的程序段中，对x的赋值语句的频度为（ ）【北京工商大学 2001 一、10（3分）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A O(2n) BO(n) CO(n2) DO(log2n) 1. 算法的计算量的大小称为计算的（ ）。【北京邮电大学2000 二、3 （20/8 分）】 A效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（ ）【中科院计算所 1998 二、1 （2分）】 A问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2） 这三个特性。 (1) A计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1（2分） 【武汉交通科技大学 1996 一、1（ 4分）】 4一个算法应该是（ ）。【中山大学 1998 二、1（2分）】 A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C. 5. 下面关于算法说法错误的是（ ）【南京理工大学 2000 一、1（1.5分）】 A算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（ ）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需