Divide and Conquer

分而治之——分治算法学习笔记

分治法适用情景

  • 该问题的规模缩小到一定的程度就可以容易地解决
  • (前提) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质
  • (关键) 利用该问题分解出的子问题的解可以合并为该问题的解;
  • (效率) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题

使用分治法 (Divide and Conquer) 解题步骤

Step1:Devide——将要解决的问题划分成若干规模较小的同类问题
Step2:Conquer——当子问题划分得足够小时,用较简单的方法解决 (递归)
Step3:Combine——将子问题的解逐层合并构成原问题的解

最接近点对问题

问题描述

二维平面上的n个点中,找出最接近的一对点

问题背景

在应用中,常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中,常需要了解其邻域中其他几何对象(最接近)的信息。例如,在空中交通控制问题中,若将飞机作为空间中移动的一个点来看待,则具有最大碰撞危险的2架飞机,就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一

问题分析

已知集合S中有n个点,使用分治法的思想就是将S进行拆分,分为2部分求最近点对。算法每次选择一条垂线L,将S拆分左右两部分为SL和SR,( L一般取点集S中所有点的中间点的x坐标来划分,这样可以保证SL和SR中的点数目各为n/2 否则以其他方式划分S,有可能导致SL和SR中点数目一个为1,一个为n-1,不利于算法效率,要尽量保持树的平衡性 )

依次找出这两部分中的最小点对距离:δL和δR,记SL和SR中最小点对距离δ = min{δL,δR}

寻找每部分最小点对距离

算法核心步骤 (子问题解合并) 如何合并两个集合找到最小点对距离

以L为中心,δmin 为半径划分一个长带,最小点对还有可能存在于SL和SR的交界处,,p点和q点分别位于SL和SR的虚线范围内,只有在这个范围内,p点和q点之间的距离才会小于δ,最小点对计算才有意义。

子集合解合并

(子问题合并算法优化) 不选取2δmin 带中所有的点进行计算,而是对于SL虚框范围内的p点,只选取SR虚框范围内长2δ,宽为δ的中的点进行计算,由δ的意义可知SR中任何2个S中的点的距离都不小于δ。由此可以推出矩形R中最多只有6个SR中的点。
然后我们只知道对于SL中每个δ中的点p最多只需要检查SR中的6个点,但是我们并不确切地知道要检查哪6个点。为了解决这个问题,我们可以将p和SR中所有δ的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的δ中点一定在矩形R中,所以它们在直线l上的投影点距p在l上投影点的距离小于d。由上面的分析可知,这种投影点最多只有6个。因此,若将SL和SR中所有S的点按其y坐标排好序,则对SL中所有点p,对排好序的点列作一次扫描,就可以找出所有最接近点对的候选者,对SL中每一点最多只要检查SR中排好序的相继6个点。
( 否则的话,最坏情形下,在SR虚框中有可能会有n/2个点,对于SL虚框中的p点,每次要比较n/2次 )

合并过程优化

矩阵稀疏性证明

  1. 反证法
    如果右边这2个正方形内有7个点与p点距离小于δ,例如q点,则q点与下面正方形的四个顶点距离小于δ,则和δ为SL和SR中的最小点对距离相矛盾。因此对于SL虚框中的p点,不需求出p点和右边虚线框内所有点距离,只需计算SR中与p点y坐标距离最近的6个点,就可以求出最近点对,节省了比较次数。

矩阵稀疏性证明-反证法

  1. 鸽舍原理
    由δ的意义可知P2中任何2个S中的点的距离都不小于δ。由此可以推出矩形R中最多只有6个S中的点。事实上,我们可以将矩形R的长为2δ的边3等分,将它的长为δ的边2等分,由此导出6个(δ/2)×(2δ/3)的矩形

矩阵稀疏性证明-鸽舍原理

若矩形R中有多于6个S中的点,则由鸽舍原理易知至少有一个δ×2δ的小矩形中有2个以上S中的点。设u,v是这样2个点,它们位于同一小矩形中,则因此d(u,v)≤5δ/6<δ 。这与δ的意义相矛盾

算法设计与描述

伪码描述

分治法求解最近点对距离
———————————————————————————————————————————————
输入:点集合points
———————————————————————————————————————————————
输出:最近点对距离distance,最近点对point1,point2
———————————————————————————————————————————————
def Closest_pair(points)
BEGIN
	length=points.length // 获取数组长度
	qsort(points,points+length,x) // 以x为标准对点集合points进行快速排序
	ClosestPair(Point points[], int length, Point &a, Point &b) // 求最近点对及最近点对距离
END

def ClosestPair(Point points[], int length, Point &a, Point &b)
BEGIN
	if length< 2
	then 
		return infinite // 如果数组长度小于2 返回无穷大
	
	else if length = 2
	then 
		return distance(points[0],points[1] // 如果数组长度等于2 返回该两点的距离
 
	else // 数组长度大于3
	then
		mid = points.mid // 获取中线
		pts1 = points(<=mid) // 存储两个集合点
		pts2 = points(>mid)
		d1 = ClosestPair(pts1, length / 2, a1, b1);             //分治求解左半部分子集的最近点  
		d2 = ClosestPair(pts2, length - length / 2, a2, b2);    //分治求解右半部分子集的最近点 
		d = min(d1,d2)
		
		// merge 合并子集解
		pts3 = points(abs(x-mid<d)  // 存储在2d之前的点
		for(each points : pits3)
		    找到points在对侧相邻的6个点 依次计算距离
			判断是否更新距离distance 和 点a,b		    

END
———————————————————————————————————————————————

源码描述

#include <ctime>
#include <cmath>
#include <iostream>  
#include <algorithm>

using namespace std;

// 分治法求解最近点对问题
// @`13
// 2017年4月21日
// 参考 : http://blog.csdn.net/to_baidu/article/details/50315607
// 参考 : http://www.cnblogs.com/king1302217/archive/2010/07/08/1773413.html

#define INFINITE_DISTANCE 65535    // 无限大距离
#define COORDINATE_RANGE 100.0    // 横纵坐标范围为[-100,100]

#ifndef Closest_pair

typedef struct Point
{// 二维坐标上的点Point
	double x;
	double y;
}Point;

double Distance(Point a, Point b)
{//平面上任意两点对之间的距离公式计算
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

bool compareX(Point a, Point b)
{//自定义排序规则:依照结构体中的x成员变量升序排序
	return a.x < b.x;
}

bool compareY(Point a, Point b)
{//自定义排序规则:依照结构体中的x成员变量升序排序
	return a.y < b.y;
}

float ClosestPair(Point points[], int length, Point &a, Point &b)
{// 求出最近点对记录,并将两点记录再a、b中
	double distance;                   //记录集合points中最近两点距离 
	double d1, d2;                     //记录分割后两个子集中各自最小点对距离
	int i = 0, j = 0, k = 0, x = 0;    //用于控制for循环的循环变量
	Point a1, b1, a2, b2;              //保存分割后两个子集中最小点对

	if (length < 2)
		return INFINITE_DISTANCE;    //若子集长度小于2,定义为最大距离,表示不可达
	else if (length == 2)
	{//若子集长度等于2,直接返回该两点的距离
		a = points[0];
		b = points[1];
		distance = Distance(points[0], points[1]);
	}
	else
	{//子集长度大于3,进行分治求解
		Point *pts1 = new Point[length];     //开辟两个子集
		Point *pts2 = new Point[length];

		sort(points, points + length, compareX);    //调用algorithm库中的sort函数对points进行排序,compareX为自定义的排序规则
		double mid = points[(length - 1) / 2].x;    //排完序后的中间下标值,即中位数

		for (i = 0; i < length / 2; i++)
			pts1[i] = points[i];
		for (int j = 0, i = length / 2; i < length; i++)
			pts2[j++] = points[i];

		d1 = ClosestPair(pts1, length / 2, a1, b1);             //分治求解左半部分子集的最近点  
		d2 = ClosestPair(pts2, length - length / 2, a2, b2);    //分治求解右半部分子集的最近点  

		if (d1 < d2) { distance = d1; a = a1; b = b1; }            //记录最近点,最近距离
		else { distance = d2; a = a2; b = b2; }

		//merge - 进行子集合解合并
		//求解跨分割线并在δ×2δ区间内的最近点对
		Point *pts3 = new Point[length];

		for (i = 0, k = 0; i < length; i++)                        //取得中线2δ宽度的所有点对共k个    
			if (abs(points[i].x - mid) <= distance)
				pts3[k++] = points[i];

		sort(pts3, pts3 + k, compareY);                                       // 以y排序矩形阵内的点集合

		for (i = 0; i < k; i++)
		{
			if (pts3[j].x - mid >= 0)                                             // 只判断左侧部分的点
				continue;
			x = 0;
			for (j = i + 1; j <= i + 6 + x && j < k; j++)            //只需与有序的领接的的6个点进行比较
			{
				if (pts3[j].x - mid < 0)
				{//  假如i点是位于mid左边则只需判断在mid右边的j点即可
					x++;
					continue;
				}
				if (Distance(pts3[i], pts3[j]) < distance)
				{//如果跨分割线的两点距离小于已知最小距离,则记录该距离和两点
					distance = Distance(pts3[i], pts3[j]);
					a = pts3[i];
					b = pts3[j];
				}
			}
		}
	}
	return distance;
}

void SetPoints(Point *points, int length)
{//随机函数对点数组points中的二维点进行初始化
	srand(unsigned(time(NULL)));
	for (int i = 0; i < length; i++)
	{
		points[i].x = (rand() % int(COORDINATERANGE * 200)) / COORDINATERANGE - COORDINATE_RANGE;
		points[i].y = (rand() % int(COORDINATERANGE * 200)) / COORDINATERANGE - COORDINATE_RANGE;
	}
}

int main()
{
	int num;            //随机生成的点对个数
	Point a, b;            //最近点对
	double diatance;    //点对距离

	cout << "请输入二维点对个数:";
	cin >> num;
	if (num < 2)
		cout << "请输入大于等于2的点个数!!" << endl;
	else
	{
		cout << endl << "随机生成的" << num << "个二维点对如下:" << endl;
		Point *points = new Point[num];

		SetPoints(points, num);
		for (int i = 0; i < num; i++)
			cout << "(" << points[i].x << "," << points[i].y << ")" << endl;
		diatance = ClosestPair(points, num, a, b);
		cout << endl << endl << "按横坐标排序后的点对:" << endl;
		for (int i = 0; i < num; i++)
			cout << "(" << points[i].x << "," << points[i].y << ")" << endl;

		cout << endl << "最近点对为:" << "(" << a.x << "," << a.y << ")和" << "(" << b.x << "," << b.y << ")" << endl << "最近点对距离为:" << diatance << endl;
	}
	system("pause");
}

#endif // !Closest_pair

算法分析

  • 快速排序过程
    对点集S的点坐标进行升序快速排序,复杂度为O(nlogn)

  • 分治过程
    接下来在分治过程中,对于每个S’yL中的点,都需要与S’yR中的6个点进行比较
    O(n)= 2O(n/2) + (n/2)*6 (一个点集划分为左右两个点集,时间复杂度为左右两个点集加上中间区域运算之和)
    带入主定理求解即可得到世界复杂度

因此总的时间复杂度为O(3nlogn),比蛮力法的O(n2)要高效

实验环境

Windows 10
Visual Studio Code 2015/Clion 2017.1

About



处身寒夜,把握星光。