最短距离计算文档Word格式.docx

1、寻找满足条件的子序列 （之二）：将一个集合拆分为和相同/最接近的两个子集（1）上面我们谈到的问题“从一个数组中取得和为C的两个数”，数组可以理解为一个集合，集合也可以理解为一个数组，我们引入下面一个问题：有一个包含n个正整数元素的集合，能否将其拆分为两个子集A,B，使A中元素之和与B中元素之和相等？ 其实该问题只要找出一个集合即可，可以变换为： 有一个包含n个整数元素的集合U，存不存在一个子集A，是自己A的元素之和为U中元素之和的一半？ 用数组arrayn来表示集合U，则U元素之和sum = array0+array1+arrayn-1。 那么只要判定是否存在子集A，A中元素之和为sum/2。

2、 这个问题类似于背包问题，先让我们回顾一下背包问题，背包问题可以表述为：有n个宝物，每个宝物有容积v和价值e属性，现有一个背包容积为V，问如何取宝物才可以保证背包中宝物价值最大。 背包问题动态规划方法： Siv表示对于前k个元素，背包总空间为v的情况下可以存放宝物的最大价值。 vi表示元素i的体积，ei表示元素i的价值，元素下表设为从0开始。 Siv = maxSi-1v, Si-1v-vi+ei i=1 and vvi S0v=0 if v=v0 当前问题可以表述成，一个背包容积为sum/2，可否用宝物将其装满？其实问题比背包问题还要简单许多： 设isOkiv：前i个元素可否将空间v装满，t

3、rue?false。 问题可以表述为： if i=1 and i=vi isOkiv=isOki-1v | isOki-1v-vi else isOkiv=isOki-1v isOk0v=false if v! isOk0v0=true isOk00=true 蕴含着isOkk0的意思代码如下：bool exist（int* v, int len） /*初始化*/ int sum=0; for（int i=0; ilen; i+） sum += vi; int half =sum/2; int* isOk=new intlenhalf+1; for（int k=0; k=vi） isOkik=

4、isOki-1k|isOki-1k-vi; else isOkik=isOki-1k; return isOklen-1half;如果我们要找和最接近中位数的集合元素之和，这一表述与两个子集合元素和之差最小其实一致，我们需要怎么做呢？先来证明上述表述：假设集合U被分为子集A，B，那么： half=sum（U）/2 sum（A） + sum（B） =sum（U）=2*half 假设sum（A）m。这样一来，对于所有pS1和qS2有pq。 递归地在S1和S2上找出其最接近点对p1,p2和q1,q2，并设=min|p1-p2|,|q1-q2|，S中的最接近点对或者是p1,p2，或者是q1,q2，或者

5、是某个p3,q3，其中p3S1且q3S2。如图1所示。图1 一维情形的分治法我们注意到，如果S的最接近点对是p3,q3，即|p3-q3|，则p3和q3两者与m的距离不超过，即|p3-m|，|q3-m|容易看出，如果选取m=max（S）+min（S）/2，可以满足线性分割的要求。选取分割点后，再用O（n）时间即可将S划分成S1=xS|xm和S2=xS|x然而，这样选取分割点m，有可能造成划分出的子集S1和S2的不平衡。例如在最坏情况下，|S1|=1，|S2|=n-1，由此产生的分治法在最坏情况下所需的计算时间T（n）应满足递归方程: T（n）=T（n-1）+O（n） 它的解是T（n）=O（n2）

6、。这种效率降低的现象可以通过分治法中“平衡子问题”的方法加以解决。也就是说，我们可以通过适当选择分割点m，使S1和S2中有大致相等个数的点。自然地，我们会想到用S的n个点的坐标的中位数来作分割点。在选择算法中介绍的选取中位数的线性时间算法使我们可以在O（n）时间内确定一个平衡的分割点m。 至此，我们可以设计出一个求一维点集S中最接近点对的距离的算法CPAIR1如下。function CPAIR1（S）;begin if |S|=2 then =|x2-x1| / x1.n存放的是S中n个点的坐标 else if （|S|=1） then := else begin m:=S中各点的坐标值的中位

7、数; 构造S1和S2,使S1=xS|xm，S2=xS|xm; 1:=CPAIRI（S1）;2:=CPAIRI（S2）; p:=max（S1）; q:=min（S2）; :=min（1,2,q-p）; end; return（）;end; 由以上的分析可知，该算法的分割步骤和合并步骤总共耗时O（n）。因此，算法耗费的计算时间T（n）满足递归方程：解此递归方程可得T（n）=O（nlogn）。 这个算法看上去比用排序加扫描的算法复杂，然而这个算法可以向二维推广。 下面我们来考虑二维的情形。此时S中的点为平面上的点，它们都有2个坐标值x和y。为了将平面上点集S线性分割为大小大致相等的2个子集S1和S2

8、，我们选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1=pS|pxm和S2=pS|px从而使S1和S2分别位于直线l的左侧和右侧，且S=S1S2 。由于m是S中各点x坐标值的中位数，因此S1和S2中的点数大致相等。递归地在S1和S2上解最接近点对问题，我们分别得到S1和S2中的最小距离1和2。现设=min（1,1）。若S的最接近点对（p,q）之间的距离d（p,q）则p和q必分属于S1和S2。不妨设pS1，qS2。那么p和q距直线l的距离均小于。因此，我们若用P1和P2分别表示直线l的左边和右边的宽为的2个垂直长条，则pS1，qS2，如图2所示。图2 距直

9、线l的距离小于的所有点 在一维的情形，距分割点距离为的2个区间（m-,m（m,m+中最多各有S中一个点。因而这2点成为唯一的末检查过的最接近点对候选者。二维的情形则要复杂些，此时，P1中所有点与P2中所有点构成的点对均为最接近点对的候选者。在最坏情况下有n2/4对这样的候选者。但是P1和P2中的点具有以下的稀疏性质，它使我们不必检查所有这n2/4对候选者。考虑P1中任意一点p,它若与P2中的点q构成最接近点对的候选者，则必有d（p,q）。满足这个条件的P2中的点有多少个呢？容易看出这样的点一定落在一个2的矩形R中，如图3所示。图3 包含点q的2的矩形R由的意义可知P2中任何2个S中的点的距离都

10、不小于。由此可以推出矩形R中最多只有6个S中的点。事实上，我们可以将矩形R的长为2的边3等分，将它的长为的边2等分，由此导出6个（/2）（2/3）的矩形。如图4（a）所示。图4 矩形R中点的稀疏性 若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个2的小矩形中有2个以上S中的点。设u,v是这样2个点，它们位于同一小矩形中，则因此d（u,v）5/6m 2.=CPAIR2（S1）;=CPAIR2（S2）; 3. m:=min（1,2）; 4. 设P1是S1中距垂直分割线l的距离在m之内的所有点组成的集合，P2是S2中距分割线l的距离在m之内所有点组成的集合。将P1和 P2中的点依其y坐标值从

11、小到大排序，并设P1*和P2*是相应的已排好序的点列;5. 通过扫描P1*以及对于P1*中每个点检查P2*中与其距离在m之内的所有点（最多6个）可以完成合并。当P1*中的扫描指针逐次向上移动时，P2*中的扫描指针可在宽为2m的一个区间内移动。设l是按这种扫描方式找到的点对间的最小距离; 6. =min（m,l）;下面分析一下算法CPAIR2的计算复杂性。设对于n个点的平面点集S，算法耗时T（n）。算法的第1步和第5步用了O（n）时间，第3步和第6步用了常数时间，第2步用了2T（n/2）时间。若在每次执行第4步时进行排序，则在最坏情况下第4步要用O（nlogn）时间。这不符合我们的要求。因此，在

12、这里我们要作一个技术上的处理。我们采用设计算法时常用的预排序技术，即在使用分治法之前，预先将S中n个点依其y坐标值排好序，设排好序的点列为P*。在执行分治法的第4步时，只要对P*作一次线性扫描，即可抽取出我们所需要的排好序的点列P1*和P2*。然后，在第5步中再对P1*作一次线性扫描，即可求得l。因此，第4步和第5步的两遍扫描合在一起只要用O（n）时间。这样一来，经过预排序处理后的算法CPAIR2所需的计算时间T（n）满足递归方程： 显而易见T（n）=O（nlogn），预排序所需的计算时间为O（n1ogn）。因此，整个算法所需的计算时间为O（nlogn）。在渐近的意义下，此算法已是最优的了。二

13、再讨论二个集合间最接近点对的情况对于求二个集合间的最接近点对的算法，其实和普通一个集合的最近点对一样，分治，复杂度O（nlogn）,只不过在合并的时候只有两个点属于不同的集合才会更新。这么做已经证明是对的，因为递归到2个点的时候最近的点对一定是合并的时候产生的，所以其实在整个算法过程中不断更新的答案一定是在合并的时候产生的，因此只需在合并的时候注意两个点属于不同集合就好了。因此在S1与S2集合中的每个点增加一个标记域，表示此点属于哪一个集合。时间复杂度与一个集合的是一样，为O（nlogn）。if |S1|=0 | |S2|=0: return ;else先给S1中的每一个点增加一个标识1，表示属于集合S1。给S2中的每一个点增加一个标识2，表示属于集合S2。合并S1，S2为S，并对S按照横坐标值快速排序（也可以利用随机化快速排序，从而减小排序平均复杂度）。if |S|=2 if 这二个点属于不同集合else if |S|=01. 构造S1*和S2*，使S1*=pS|pxm和S2*=pS|px=CPAIR2（S1*）;=CPAIR2（S2*）;3. 设P1是S1*中距垂直分割线l的距离在m之内的所有 点组成的集合， P2是S2*中距分割线l的距离在m之内所有点组成的集合。将P1和P2中