下载文档原格式
分治法解决问题的步骤一、基础概念类题目（1 - 5题）题目1：简述分治法解决问题的基本步骤。
解析：分治法解决问题主要有三个步骤：1. 分解（Divide）：将原问题分解为若干个规模较小、相互独立且与原问题形式相同的子问题。
例如，对于排序问题，可将一个大的数组分成两个较小的子数组。
2. 求解（Conquer）：递归地求解这些子问题。
如果子问题规模足够小，则直接求解（通常是一些简单的基础情况）。
对于小到只有一个元素的子数组，它本身就是有序的。
3. 合并（Combine）：将各个子问题的解合并为原问题的解。
在排序中，将两个已排序的子数组合并成一个大的有序数组。
题目2：在分治法中，分解原问题时需要遵循哪些原则？解析：1. 子问题规模更小：分解后的子问题规模要比原问题小，这样才能逐步简化问题。
例如在归并排序中，不断将数组对半分，子数组的长度不断减小。
2. 子问题相互独立：子问题之间应该尽量没有相互依赖关系。
以矩阵乘法的分治算法为例，划分后的子矩阵乘法之间相互独立进行计算。
3. 子问题与原问题形式相同：方便递归求解。
如二分查找中，每次查找的子区间仍然是一个有序区间，和原始的有序区间查找问题形式相同。
题目3：分治法中的“求解”步骤，如果子问题规模小到什么程度可以直接求解？解析：当子问题规模小到可以用简单的、直接的方法（如常量时间或线性时间复杂度的方法）解决时，就可以直接求解。
例如，在求数组中的最大最小值问题中，当子数组只有一个元素时，这个元素既是最大值也是最小值，可以直接得出结果。
题目4：分治法的“合并”步骤有什么重要性？解析：1. 构建完整解：它将各个子问题的解组合起来形成原问题的解。
例如在归并排序中，单独的两个子数组排序好后，只有通过合并操作才能得到整个数组的有序排列。
2. 保证算法正确性：如果合并步骤不正确，即使子问题求解正确，也无法得到原问题的正确答案。
例如在分治算法计算斐波那契数列时，合并不同子问题的结果来得到正确的斐波那契数是很关键的。
蛮力法与分治法求解最近对问题1、蛮力法蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义，来求解问题。
虽然巧妙和高效的算法很少来自于蛮力法，但它仍是一种重要的算法设计策略：（1）适用泛围广，是能解决几乎所有问题的一般性方法；（2）常用于一些非常基本、但又十分重要的算法（排序、查找、矩阵乘法和字符串匹配等）；（3）解决一些规模小或价值低的问题；（4）可以做为同样问题的更高效算法的一个标准；（5）可以通过对蛮力法的改进来得到更好的算法。
2、分治法分治法，就是分而治之即把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到问题解决。
分治法在求解问题时，效率比较高，也是一种重要的算法策略：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
算法的基本思想及复杂度分析1．蛮力法（1）基本思想蛮力法求解最近对问题的过程是：分别计算每一对点之间的距离，然后通过排序找出距离最小的一对，为了避免对同一对点计算两次距离，只考虑i<j的那些点对（P i，P j）。
（2）复杂度分析算法的基本操作是计算两个点的欧几里得距离。
在求欧几里得距离时，我们要避免求平方根操作，因为求平方根时要浪费时间，而在求解此问题时，求解平方根并没什么更大的意义。
如果被开方的数越小，则它的平方根也越小。
因此，算法的基本操作就是求平方即可，其执行次数为：T(n)=∑-=11n i ∑+=n i j 12 =2∑-=-11)(n i i n =n （n-1）=O （n2）2.分治法（1）基本思想用分治法解决最近对问题，就是将集合S 分成两个子集S1和S2，每个子集中有n/2个点。
![计算机算法设计与分析(第4版)[王晓东][电子教案]第2章](https://img.taocdn.com/s1/m/6ef58047f7ec4afe04a1df38.png)
最近点对问题I.一维问题：一、问题描述和分析最近点对问题的提法是：给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。
严格的讲，最接近点对可能多于1对，为简单起见，只找其中的1对作为问题的解。
简单的说，只要将每一点与其它n-1个点的距离算出，找出达到最小距离的2点即可。
但这样效率太低，故想到分治法来解决这个问题。
也就是说，将所给的平面上n个点的集合S 分成2个子集S1和S2，每个子集中约有n/2个点。
然后在每个子集中递归的求其最接近的点对。
这里，关键问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对。
如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决，但如果这2个点分别在S1和S2中，问题就不那么简单了。
下面的基本算法中，将对其作具体分析。
二、基本算法假设用x轴上某个点m将S划分为2个集合S1和S2，使得S1={x∈S|x<=m}；S2={x ∈S|x>m}。
因此，对于所有p∈S1和q∈S2有p<q。
递归的在S1和S2上找出其最接近点对{p1，p2}和{q1，q2}，并设d=min{|p1-p2|,|q1-q2|}。
由此易知，S中的最接近点对或者是{p1，p2}，或者是{q1，q2}，或者是某个{p3，q3}，其中p3∈S1且q3∈S2。
如下图所示：S1 S2p1 p2 p3 q1 q2 q3图1 一维情形的分治法注意到，如果S的最接近点对是{p3，q3}，即|p3-q3|<d，则p3和q3两者与m的距离不超过d，即|p3-m|<d，|q3-m|<d。
也就是说，p3∈(m-d，m],q3∈(m，m+d]。
由于每个长度为d的半闭区间至多包含S1中的一个点，并且m是S1和S2的分割点，因此(m-d，m]中至少包含一个S中的点。
同理，(m，m+d]中也至少包含一个S中的点。
最近点对算法1. 简介最近点对算法（Closest Pair Algorithm）是一种用于找到平面上最近的两个点的算法。
该算法可以在给定一组点的情况下，找到距离最近的两个点，并计算出它们之间的距离。
最近点对问题在计算几何学、图像处理、数据挖掘等领域中具有广泛应用。
例如，在地理信息系统中，可以使用最近点对算法来查找距离最近的两个地理位置；在机器视觉中，可以使用该算法来寻找图像中距离最接近的两个特征点。
2. 算法思想最近点对算法采用分治策略，将问题划分为多个子问题，并通过递归求解子问题来得到整体解。
其基本思想可以概括为以下步骤：1.将所有点按照横坐标进行排序。
2.将排序后的点集平均划分为左右两部分，分别称为P_left和P_right。
3.分别在P_left和P_right中递归求解最近点对。
4.在左右两部分求得的最近点对中，选择距离更小的那一对作为候选解。
5.在区间[P_left[-1].x, P_right[0].x]内，查找可能的更近点对。
6.比较候选解与新找到的更近点对，选择距离更小的那一对作为最终解。
3. 算法实现3.1 数据结构在实现最近点对算法时，需要定义合适的数据结构来表示点。
常见的表示方法是使用二维数组或类对象。
以下是使用类对象来表示点的示例代码：class Point:def __init__(self, x, y):self.x = xself.y = y3.2 算法步骤3.2.1 排序首先，将所有点按照横坐标进行排序。
可以使用快速排序或归并排序等算法来实现排序功能。
def sort_points(points):# 使用快速排序按照横坐标进行排序# ...3.2.2 分治求解将排序后的点集平均划分为左右两部分，并递归求解最近点对。
def closest_pair(points):n = len(points)# 如果点集中只有两个点，则直接返回这两个点和它们之间的距离if n == 2:return points, distance(points[0], points[1])# 如果点集中只有三个点，则直接计算出最近点对if n == 3:d1 = distance(points[0], points[1])d2 = distance(points[0], points[2])d3 = distance(points[1], points[2])if d1 <= d2 and d1 <= d3:return [points[0], points[1]], d1elif d2 <= d1 and d2 <= d3:return [points[0], points[2]], d2else:return [points[1], points[2]], d3# 将点集平均划分为左右两部分mid = n // 2P_left = points[:mid]P_right = points[mid:]# 分别在左右两部分递归求解最近点对closest_pair_left = closest_pair(P_left)closest_pair_right = closest_pair(P_right)# 在左右两部分求得的最近点对中，选择距离更小的那一对作为候选解if closest_pair_left[1] < closest_pair_right[1]:min_pair, min_distance = closest_pair_leftelse:min_pair, min_distance = closest_pair_right3.2.3 查找更近点对在区间[P_left[-1].x, P_right[0].x]内，查找可能的更近点对。
最接近点对问题_分治法⼀、问题描述给定平⾯上的n个点，找其中的⼀对点，使得在n个点组成的所有点对中该点对间的距离最⼩。
⼆、解题思路及所选算法策略的可⾏性分析思路：利⽤分治法来解决问题。
递归⼦结构求最接近点对总体可分为⼏个步骤：1、当问题规模⼩于20，直接求解最⼩点对2、将n个点组成的集合S分成2个⼦集S1和S23、递归求出两个⼦集中的最接近点对并⽐较出最⼩点对，记录距离dmin4、以X坐标为基准找到所有点中线，在中线附近找出相距可能⼩于dmin的点对点，记录于S3和S45、求S3和S4每点对距离，和dmin进⾏⽐较，求解最接近点对策略可⾏性分析：设直线l上有2m个点，以m为中点将l分割成两条线段dl,dr，然后求出dl和dr这两点条线段中的最⼩点距d1,d2，此时d=min{d1,d2}，再通过计算出dl线段的中最⼤点与dr线段中的最⼩点之间的距离D，最⼩距离则为min{d,D}.⼆维情况与此相似，最⼤的区别只是对于中线位置的点，⼆维情况只是针对中线旁好多可能点，再在Y轴⽅向上进⾏点的筛选，以减少平⽅计算次数。
三、伪代码描述及复杂度分析Public static double closestPoint(S){1、⾸先，递归结束条件，当数组长度在⼀定范围内时直接求出最近点，蛮⼒求解2、求所有点在X坐标中的中位数midX3、以midX为界将所有点分成两组分别存放在两个表中4、将两张表转化为数组类型，并分别按X坐标升序排列5、求S1中的最近距离的两个点6、求S2中的最近距离的两个点7、求两最近距离的最⼩值8、在S1、S2中收集距离中线⼩于d1的点，分别存放于两个表中9、分别将表T3、T4转换为数组类型的S3、S4，并将其分别按Y坐标升序排列10、求解S3、S4两者之间可能的更近（相⽐于d1）距离 , 以及构成该距离的点}复杂度分析：设算法耗时T(n)。
算法第1步、第2步、第3步和第8步⽤了O(n)时间。
一、最接近点对问题（一维）1、最接近点对问题（一维）最接近点对问题:给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。
此时S中的n个点退化为x轴上的n个实数x1,x2,..,x n。
最接近点对即为这n 个实数中相差最小的2个实数。
2、分析将所给的平面上n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，·然后在每个子集中递归地求其最接近的点对。
S1和S2的最接近点对未必就是S的最接近点对，如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。
但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n2/4次计算和比较才能确定S的最接近点对。
因此，依此思路，合并步骤耗时为O(n2)。
整个算法所需计算时间T(n)应满足:T(n)=2T(n/2)+O(n2)它的解为T(n)=O(n2)3、伪代码随机Randomfloat Random(){float result=rand()%10000;return result*0.01;}返回最大、最小float Max OR Min(float s[],int p,int q)//返回s[]中的最大值{float s_max（s_min）=s[p];for(int i=p+1;i<=q;i++)if(s_max<s[i])s_max=s[i]; ORif(s_min>s[i])s_min=s[i];return s_max（s_min）}主要函数Cpair Cpair1(float s[],int n){Cpair out_p_d={99999,0,0};if(n<2) return out_p_d;float m1=Max(s,0,n-1),m2=Min(s,0,n-1);float m=(m1+m2)/2;//找出点集中的中位数int j=0,k=0;//将点集中的各元素按与m的大小关系分组float s1[M],s2[M];for(int i=0;i<n;i++){if(s[i]<=m) {s1[j]=s[i];j++;}else {s2[k]=s[i];k++;}}Cpair d1=Cpair1(s1,j),d2=Cpair1(s2,k);//递归float p=Max(s1,0,j-1),q=Min(s2,0,k-1);//返回s[]中的具有最近距离的点对及其距离if(d1.d<d2.d){if((q-p)<d1.d){out_p_d.d=(q-p);out_p_d.d1=q;out_p_d.d2=p;return out_p_d;}else return d1;}else{if((q-p)<d2.d){out_p_d.d=(q-p);out_p_d.d1=q;out_p_d.d2=p;return out_p_d;}else return d2;}}4、程序实现#include<time.h>#include <iostream>using namespace std;const int M=50;struct Cpair{float d;float d1,d2;};float Random();int input(float s[],int number_used);float Max(float s[],int p,int q);float Min(float s[],int p,int q);Cpair Cpair1(float s[],int n);void main(){srand((unsigned)time(NULL));int number_used,m;float s[M];Cpair d;m=input(s,number_used);d=Cpair1(s,m);cout<<endl<<"the closest pair is ("<<d.d1<<","<<d.d2<<")";cout<<endl<<"the min distance is "<<d.d<<endl;}float Random(){float result=rand()%10000;return result*0.01;}int input(float s[],int number_used){cout<<"input the number ";cin>>number_used;cout<<"the random number are ";for(int i=1;i<=number_used;i++){s[i]=Random();cout<<s[i]<<" ";}return number_used;}float Max(float s[],int p,int q)//返回s[]中的最大值{float s_max=s[p];for(int i=p+1;i<=q;i++)if(s_max<s[i])s_max=s[i];return s_max;}float Min(float s[],int p,int q)//返回s[]中的最小值{float s_min=s[p];for(int i=p+1;i<=q;i++)if(s_min>s[i])s_min=s[i];return s_min;}//返回s[]中的具有最近距离的点对及其距离Cpair Cpair1(float s[],int n){Cpair out_p_d={99999,0,0};if(n<2) return out_p_d;float m1=Max(s,0,n-1),m2=Min(s,0,n-1);float m=(m1+m2)/2;//找出点集中的中位数int j=0,k=0;//将点集中的各元素按与m的大小关系分组float s1[M],s2[M];for(int i=0;i<n;i++){if(s[i]<=m) {s1[j]=s[i];j++;}else {s2[k]=s[i];k++;}}Cpair d1=Cpair1(s1,j),d2=Cpair1(s2,k);//递归float p=Max(s1,0,j-1),q=Min(s2,0,k-1);//返回s[]中的具有最近距离的点对及其距离if(d1.d<d2.d){if((q-p)<d1.d){out_p_d.d=(q-p);out_p_d.d1=q;out_p_d.d2=p;return out_p_d;}else return d1;}{if((q-p)<d2.d){out_p_d.d=(q-p);out_p_d.d1=q;out_p_d.d2=p;return out_p_d;}else return d2;}}运行情况：二、最接近点对问题（二维）1、最接近点对问题（二维）二维时S中的点为平面上的点，它们都有2个坐标值x和y。
给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。
2、分析设对于n个点的平面点集S，算法耗时T(n)。
算法的求中位数和合并用了O(n)时间，求最小距离用了常数时间，递归用了2T(n/2)时间。
我们采用设计算法时常用的预排序技术，即在使用分治法之前，预先将S中n个点依其y坐标值排好序，设排好序的点列为P*。
在执行的两遍扫描合在一起只要用O(n)时间。
这样一来，经过预排序处理后的算法CPAIR2所需的计算时间T(n)满足递归方程：显而易见T(n)=O(n log n)，预排序所需的计算时间为O(n1og n)。
因此，整个算法所需的计算时间为O(n log n)。
用类PointX和PointY表示依x坐标和y坐标排好序的点class PointX {public:int operator<=(PointX a)const{ return (x<=a.x); }int ID; //点编号float x,y; //点坐标};class PointY {public:int operator<=(PointY a)const{ return(y<=a.y); }求距离Dis=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)假设我们用x轴上某个点m将S划分为2个子集S1和S2 ，基于平衡子问题的思想，用S中各点坐标的中位数来作分割点。
递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}，并设d=min{|p1-p2|,|q1-q2|}，S中的最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{p3,q3}，其中p3∈S1且q3∈S2。
如果S的最接近点对是{p3,q3}，即|p3-q3|小于d，则p3和q3两者与m的距离不超过d，即p3∈(m-d,m]，q3∈(m,m+d]。
由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m]中至多包含S中的一个点。
由图可以看出，如果(m-d,m]中有S中的点，则此点就是S1中最大点。
因此，我们用线性时间就能找到区间(m-d,m]和(m,m+d]中所有点，即p3和q3。
从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。
选取一垂直线l:x=m来作为分割直线。
其中m为S中各点x坐标的中位数。
由此将S分割为S1和S2。
递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d2}，S中的最接近点对或者是d，或者是某个{p,q}，其中p∈P1且q∈P2。
再考虑合并时{p,q}的情况，如下图：P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)小于d。
满足这个条件的P2中的点一定落在一个d×2d的矩形R 中。
由d的意义可知，P2中任何2个S中的点的距离都不小于d。
由此可以推出矩形R中最多只有6个S中的点。
因此，在分治法的合并步骤中最多只需要检查6×n/2=3n个候选者。
为了确切地知道要检查哪6个点，可以将p和P2中所有S2的点投影到垂直线l 上。
