0007算法笔记分治法最接近点对问题Word文件下载.docx
- 文档编号:4163323
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:23
- 大小:112.72KB
0007算法笔记分治法最接近点对问题Word文件下载.docx
《0007算法笔记分治法最接近点对问题Word文件下载.docx》由会员分享,可在线阅读,更多相关《0007算法笔记分治法最接近点对问题Word文件下载.docx(23页珍藏版)》请在冰点文库上搜索。
"
stdafx。
h”
3.#include
〈ctime〉
4.#include
〈iostream〉
5.using
namespace
std;
6.
7.const
int
L=100;
8.//点对结构体
9.struct
Pair
10.{
11.
float
d;
//点对距离
12.
d1,d2;
//点对坐标
13.};
14.float
Random();
15.int
input(float
s[]);
//构造S
16.float
Max(float
s[],int
p,int
q);
17.float
Min(float
s[],int
p,int
q);
18.template
<
class
Type〉
19.void
Swap(Type
&x,Type
&
y);
20.template
21.int
Partition(Type
s[],Type
x,int
l,int
r);
22.Pair
Cpair(float
23.
24.int
main()
25.{
26.
srand((unsigned)time(NULL));
27.
m;
28.
s[L];
29.
30.
m=input(s);
31.
d=Cpair(s,0,m—1);
32.
cout〈〈endl〈〈”最近点对坐标为:
(d1:
”〈<
d.d1〈<
”,d2:
d.d2〈〈”)"
;
33.
cout<
endl〈<
这两点距离为:
〈〈d。
d<
endl;
34.
return
0;
35.}
36.
37.
38.float
Random()
39.{
40.
result=rand()%10000;
41.
result*0。
01;
42.}
43.
44.int
s[])
45.{
46.
length;
47.
cout〈〈”输入点的数目:
”;
48.
cin〉〉length;
49.
〈"
点集在X轴上坐标为:
50.
for(int
i=0;
i〈length;
i++)
51.
{
52.
s[i]=Random();
53.
s[i]<
54.
}
55.
56.
length;
57.}
58.
59.
60.float
r)//返回s[]中的最大值
61.{
62.
s_max=s[l];
63.
i=l+1;
i〈=r;
64.
if(s_max〈s[i])
65.
s_max=s[i];
66.
s_max;
67.}
68.
69.float
s[],int
r)//返回s[]中的最小值
70.{
71.
s_min=s[l];
72.
i=l+1;
i<
=r;
73.
if(s_min〉s[i])
74.
s_min=s[i];
75.
s_min;
76.}
77.
78.template
〈class
79.void
x,Type
&y)
80.{
81.
Type
temp
=
x;
82.
x
y;
83.
y
temp;
84.}
85.
86.template
87.int
r)
88.{
89.
i
l
-
1,j
r
+
1;
90.
91.
while(true)
92.
93.
while(s[++i]〈x
&&
r);
94.
while(s[--j]>
x);
95.
if(i>
=j)
96.
97.
break;
98.
}
99.
Swap(s[i],s[j]);
100.
101.
j;
102.}
103.
104.//返回s[]中的具有最近距离的点对及其距离
105.Pair
s[],int
106.{
107.
min_d={99999,0,0};
//最短距离
108.
109.
if(r—l〈1)
min_d;
110.
m1=Max(s,l,r),m2=Min(s,l,r);
111.
112.
m=(m1+m2)/2;
//找出点集中的中位数
113.
114.
//将点集中的各元素按与m的大小关系分组
115.
j
Partition(s,m,l,r);
116.
117.
d1=Cpair(s,l,j),d2=Cpair(s,j+1,r);
//递归
118.
p=Max(s,l,j),q=Min(s,j+1,r);
119.
120.
//返回s[]中的具有最近距离的点对及其距离
121.
if(d1。
d〈d2.d)
122.
123.
if((q-p)〈d1。
d)
124.
125.
min_d。
d=(q-p);
126.
d1=q;
127.
d2=p;
128.
129.
130.
else
d1;
131.
132.
133.
{
134.
if((q-p)〈d2。
135.
136.
d=(q—p);
137.
min_d.d1=q;
138.
139.
140.
141.
d2;
142.
143.}
程序运行结果如下:
该算法的分割步骤和合并步骤总共耗时O(n)。
因此,算法耗费的计算时间T(n)满足递归方程:
解此递归方程可得T(n)=O(nlogn).
2、二维最接近点对问题
将以上过程推广到二维最接近点对问题,设S中的点为平面上的点,它们都有2个坐标值x和y。
为了将平面上点集S线性分割为大小大致相等的2个子集S1和S2,我们选取一垂直线l:
x=m来作为分割直线。
其中m为S中各点x坐标的中位数。
由此将S分割为S1={p∈S|px≤m}和S2={p∈S|px〉m}.从而使S1和S2分别位于直线l的左侧和右侧,且S=S1∪S2.由于m是S中各点x坐标值的中位数,因此S1和S2中的点数大致相等。
递归地在S1和S2上解最接近点对问题,我们分别得到S1和S2中的最小距离d1和d2.现设d=min(d1,d2).若S的最接近点对(p,q)之间的距离d(p,q)〈d则p和q必分属于S1和S2。
不妨设p∈S1,q∈S2.那么p和q距直线l的距离均小于d。
因此,我们若用P1和P2分别表示直线l的左边和右边的宽为d的2个垂直长条,则p∈S1,q∈S2,如图所示:
距直线l的距离小于d的所有点
在一维的情形,距分割点距离为d的2个区间(m—d,m](m,m+d]中最多各有S中一个点。
因而这2点成为唯一的末检查过的最接近点对候选者。
二维的情形则要复杂些,此时,P1中所有点与P2中所有点构成的点对均为最接近点对的候选者。
在最坏情况下有n2/4对这样的候选者。
但是P1和P2中的点具有以下的稀疏性质,它使我们不必检查所有这n^2/4对候选者.考虑P1中任意一点p,它若与P2中的点q构成最接近点对的候选者,则必有d(p,q)〈d.满足这个条件的P2中的点有多少个呢?
容易看出这样的点一定落在一个d×
2d的矩形R中,如下图所示:
包含点q的dX2d矩形R
由d的意义可知P2中任何2个S中的点的距离都不小于d。
由此可以推出矩形R中最多只有6个S中的点。
事实上,我们可以将矩形R的长为2d的边3等分,将它的长为d的边2等分,由此导出6个(d/2)×
(2d/3)的矩形。
如左图所示:
矩阵R中点的稀疏性
若矩形R中有多于6个S中的点,则由鸽舍原理易知至少有一个δ×
2δ的小矩形中有2个以上S中的点。
设u,v是这样2个点,它们位于同一小矩形中,则:
因此d(u,v)≤5d/6〈d.这与d的意义相矛盾.也就是说矩形R中最多只有6个S中的点。
图4(b)是矩形R中含有S中的6个点的极端情形。
由于这种稀疏性质,对于P1中任一点p,P2中最多只有6个点与它构成最接近点对的候选者。
因此,在分治法的合并步骤中,我们最多只需要检查6×
n/2=3n对候选者,而不是n^2/4对候选者。
这是否就意味着我们可以在O(n)时间内完成分治法的合并步骤呢?
现在还不能作出这个结论,因为我们只知道对于P1中每个S1中的点p最多只需要检查P2中的6个点,但是我们并不确切地知道要检查哪6个点。
为了解决这个问题,我们可以将p和P2中所有S2的点投影到垂直线l上。
由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中,所以它们在直线l上的投影点距p在l上投影点的距离小于d。
由上面的分析可知,这种投影点最多只有6个。
因此,若将P1和P2中所有S的点按其y坐标排好序,则对P1中所有点p,对排好序的点列作一次扫描,就可以找出所有最接近点对的候选者,对P1中每一点最多只要检查P2中排好序的相继6个点.
程序清单如下:
[cpp]
1.//2d10—2
二维最邻近点对问题
2.#include
h"
3.#include〈time.h〉
4.#include<
iostream〉
5.#include<
cmath〉
7.using
8.const
M=50;
9.
10.//用类PointX和PointY表示依x坐标和y坐标排好序的点
11.class
PointX
public:
13.
operator〈=(PointX
a)const
14.
(x<
=a。
x);
15.
ID;
//点编号
16.
x,y;
//点坐标
17.};
18.
19.class
PointY
20.
public:
21.
operator〈=(PointY
22.
return(y〈=a.y);
p;
//同一点在数组x中的坐标
24.
x,y;
25.};
27.float
Random();
28.template
29.float
dis(const
Type&
u,const
v);
31.bool
Cpair2(PointX
X[],
n,PointX&
a,PointX&
b,
float&
d);
32.void
closest(PointX
X[],PointY
Y[],PointY
Z[],
l,
r,PointX&
a,PointX&
b,float&
d);
34.template
〈typename
Type>
35.void
Copy(Type
a[],Type
b[],
left,int
right);
37.template
38.void
Merge(Type
c[],Type
d[],int
l,int
m,int
39.
40.template
41.void
MergeSort(Type
a[],Type
b[],int
left,int
42.
43.int
44.{
45.
srand((unsigned)time(NULL));
cout〈<
请输入点对数:
cin〉〉length;
X[M];
”随机生成的二维点对为:
〈<
X[i]。
ID=i;
57.
X[i].x=Random();
X[i].y=Random();
cout〈〈”("
〈〈X[i]。
x〈〈”,”〈〈X[i].y<
〈”)
60.
61.
a;
b;
d;
Cpair2(X,length,a,b,d);
67.
cout〈〈endl;
69.
cout〈〈”最邻近点对为:
(”<
a。
x<
”〈<
a.y〈<
”)和(”<
b。
x〈<
”〈〈b.y〈〈"
)
”<
〈endl;
70.
”最邻近距离为:
”〈〈d〈〈endl;
0;
73.}
75.float
76.{
result=rand()%10000;
78.
79.}
80.
81.//平面上任意两点u和v之间的距离可计算如下
82.template
83.inline
u,const
Type&
v)
84.{
dx=u。
x—v.x;
86.
dy=u。
y—v。
y;
87.
sqrt(dx*dx+dy*dy);
88.}
90.bool
X[],
a,PointX&
b,float&
91.{
if(n<
2)
false;
PointX*
tmpX
new
PointX[n];
MergeSort(X,tmpX,0,n-1);
PointY*
Y=new
PointY[n];
i〈n;
//将数组X中的点复制到数组Y中
Y[i]。
p=i;
Y[i].x=X[i].x;
102.
y=X[i].y;
104.
105.
PointY*
tmpY
PointY[n];
106.
MergeSort(Y,tmpY,0,n—1);
Z=new
closest(X,Y,Z,0,n-1,a,b,d);
delete
[]Y;
[]Z;
[]tmpX;
del
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 0007 算法 笔记 分治 最接近 问题