算法201005-分治

《算法201005-分治》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1两个例子：棋盘覆盖与最接近点对问题2减治法3分治法小结第2章分治与递归算法（3）棋盘覆盖问题一个2k×2k的特殊棋盘是其中含有一个特殊方格的棋盘，如左下图为k=2的一个特殊棋盘。现在任意给定一个2k×2k的特殊棋盘，要用右下图所示的L型骨牌来无重叠的覆盖它。1112223334445在2k×2k的棋盘覆盖中要用到(4k–1)/3个L型骨牌。55棋盘覆盖问题分析当k>0时，将2k×2k的棋盘分割成4个2k–1×2k–1的子棋盘，如右下图所示：2k–1×2k–12k–1×2k–12k–1×2k–12k–1×2k–1然而，这样一来四个子棋盘的情形就不一致了。因为递

2、归求解是将问题归结到较小的规模的同一问题，所以就需要将三个正常子棋盘也转化成特殊棋盘。为此，可以用一个L型骨牌来覆盖其余三个子棋盘的会合处，如左图所示。这样原问题转化成了四个较小规模的子问题。递归地分割下去直至单格棋盘。特殊方格必定位于4个子棋盘之一中。棋盘覆盖算法设计棋盘覆盖(参数表){如果是单个格子，则返回；将棋盘划分成尺寸为一半的子棋盘；判断特殊方格在哪个子棋盘中，再用相应的骨牌覆盖相应结合部，并记下它们的位置；依次对左上角、右上角、左下角和右下角这四个子棋盘进行棋盘覆盖；}设T(k)是棋盘覆盖算法覆盖2k×2k的棋盘所需要的时间，则从算法的分治策略可知

3、，T(k)满足如下递归方程：棋盘覆盖算法的复杂性T(k)=O(1)k=04T(k–1)+O(1)k＞0解此递归方程可得T(k)=O(4k)。由于覆盖2k×2k的棋盘要用(4k–1)/3个L型骨牌，故此算法是一个在渐进意义下最优的算法。最接近点对问题给定平面上n个点，在n个点组成的所有点对中，找出其中相互距离最小的一对点。此问题的简单解法是，算出每个点与其它n–1个点之间的距离，再找出其中距离最小的一对点。这样做的时间复杂性为O(n2)。下面用分治法构造一个时间复杂性为O(nlogn)的算法。为此我们先考虑一维的情况：在应用中，常用诸如点、圆等简单的几何对象代表

4、现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制问题中，若将飞机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。一维最接近点对设S为x轴上n个点的集合，求S中最接近点对。假设用x轴上某个点m划分S为S1和S2，使得S1={x∈S

5、x≤m}，S2={x∈S

6、x＞m}。递归地在S1和S2中找出其最接近点对{p1，p2}和{q1，q2}，并设d=min{

7、p1，p2

8、，

9、q1，q2

10、}易知，S中最接近点对是{p1，p2}或{q1

11、，q2}，或{p3，q3}，这里p3=max{S1}，q3=min{S2}。mS1S2p1p2p3q3q1q2一维最接近点对算法boolCpair1(S,d){n=

12、S

13、;if(n<2){d=∞;returnfalse}m=S中各点的坐标的中位数；构造S1和S2;//S1={xS

14、xm},S2={xS

15、x>m}Cpair1(S1,d1);Cpair1(S2,d2);//分别求S1和S2的最接近点对p=max{S1};q=min{S2};d=mim{d1,d2,q–p};returntrue}一维最接近点对算法复杂性如果对S的分割不平衡的话，最坏的情况是S

16、1仅含一个点，这时算法的复杂性为O(n2)。所以要采用中位数m来分割S。该算法的分割步骤和合并步骤总共耗时O(n)，因此算法耗时满足递归方程T(n)=O(1)n＜02T(n/2)+O(n)n≥4解此递归方程可得T(n)=O(nlogn)。平面最接近点对做一条直线L：x=m，将S分割为S1和S2，其中m为所有点的x坐标的中位数。递归地求得S1和S2中的最小距离d1和d2，令d=min{d1，d2}。LS1S2d1d2但是S1和S2之间的最小距离却需要考察S1和S2在l两侧距离不超过d的区域P1和P2间的点对。dP1dP2P1和P2间的点对均为最近点对的候选，最坏

17、情况有n2/4个。而实际上，对P1中的任意一点，最多只需要考察P2中的6个点。最多只需要考察6个点考虑P1中的任意一点p，它若与P2中的点q构成最接近点对，则其距离必定小于d。这样的点必定落在一个d×2d的矩形R内：LP1P2pddR在矩形R中最多有6个点。不然的话，可以将矩形R分成6个(d/2)×(2d/3)个小矩形，每个小矩形对角线的长度为5d/6。(d/2)2+(2d/3)2=25d2/36若R中有6个以上的点，则必有两点u、v在同一小矩形内，于是

18、uv

19、＜5d/6。矛盾。（鸽舍原理）所以R中至多有6个点，即对P1中的每个点至多只需要考察P2中的6个点就

20、可以了。分别将P1和P2中的点按y坐标