分治法求点对问题_友谊点对

---

title: 分治法求点对问题
date: 2018-11-15 20:55:40
tags: 算法
categories: 十一月，2018

Divide and Conquer

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

分治法适用情景

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

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

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

最接近点对问题

问题描述

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

问题背景

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

问题分析

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

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

算法核心步骤 (子问题解合并)

- 如何合并两个集合找到最小点对距离
1

以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个点，就可以求出最近点对，节省了比较次数。

2.鸽舍原理
由δ的意义可知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
———————————————————————————————————————————————
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

源码描述

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

using namespace std;

// 分治法求解最近点对问题
// 2018年11月15日
// 参考 : https://www.jianshu.com/p/8bc681afbaff

#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++)
    	{
        	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(COORDINATE_RANGE * 200)) / 				COORDINATE_RANGE - COORDINATE_RANGE;
    	points[i].y = (rand() % int(COORDINATE_RANGE * 200)) / COORDINATE_RANGE - 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

算法分析

快速排序过程

对点集S的点坐标进行升序快速排序，复杂度为O(nlogn)
1

分治过程

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

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