蛮力法分治法求最近对Word下载.doc

蛮力法分治法求最近对Word下载.doc

《蛮力法分治法求最近对Word下载.doc》由会员分享，可在线阅读，更多相关《蛮力法分治法求最近对Word下载.doc（7页珍藏版）》请在冰点文库上搜索。

typedefstructCloseNode

{//用于保存最近两个点以及这两个点之间的距离

Nodea;

Nodeb;

doublespace;

}CloseNode;

intmax;

voidcreate（NList&

L）

{

cout<

<

"

请输入平面上点的数目:

\n"

;

cin>

>

max;

L.count=max;

L.data=newNode[L.count];

//====================动态空间分配

输入"

L.count<

个点坐标X,Y,以空格隔开:

endl;

for（inti=0;

i<

L.count;

i++）

cin>

L.data[i].x>

L.data[i].y;

}

//求距离平方的函数

doubleDistinguish2（Nodea,Nodeb）

return（（a.x-b.x）*（a.x-b.x））+（（a.y-b.y）*（a.y-b.y））;

//蛮力法求最近对

voidBruteForce（constNList&

L,CloseNode&

cnode,intbegin,intend）

for（inti=begin;

=end;

for（intj=i+1;

j<

j++）

{

doublespace=Distinguish2（L.data[i],L.data[j]）;

if（space<

cnode.space）

{

cnode.a=L.data[i];

cnode.b=L.data[j];

cnode.space=space;

}

}

//归并排序

voidMerge（NodeSR[],NodeTR[],inti,intm,intn）

{//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]

intj,k;

for（j=m+1,k=i;

=m&

&

=n;

k++）

if（SR[i].x<

=SR[j].x）TR[k]=SR[i++];

elseTR[k]=SR[j++];

while（i<

=m）TR[k++]=SR[i++];

while（j<

=n）TR[k++]=SR[j++];

voidMsort（NodeSR[],NodeTR1[],ints,intt）

{//将SR[s..t]归并排序为TR1[s..t]

if（s==t）TR1[s]=SR[s];

else

{

intm=（s+t）/2;

Node*TR2=newNode[max];

//newNode[t-s+1];

//这个空间挂挂的,从s到t，这里是从0到t-s

Msort（SR,TR2,s,m）;

Msort（SR,TR2,m+1,t）;

Merge（TR2,TR1,s,m,t）;

}

voidMergeSort（NListL）

Msort（L.data,L.data,0,L.count-1）;

//分治法求最近对中间2d对称区的算法

voidMiddle（constNList&

cnode,intmid,intmidX）

inti,j;

intd=sqrt（cnode.space）;

i=mid;

while（i>

=0&

=（midX-d））

j=mid;

while（L.data[++j].x<

=（midX+d）&

=L.count）

{//1,j++2<

=,>

=

if（L.data[j].y<

（L.data[i].y-d）||L.data[j].y>

（L.data[i].y+d））

continue;

doublespace=Distinguish2（L.data[i],L.data[j]）;

if（cnode.space>

space）

cnode.a=L.data[i];

cnode.b=L.data[j];

cnode.space=space;

i--;

//----------------------------------------------

//分治法求最近对

voidDivideAndConquer（constNList&

L,CloseNode&

closenode,intbegin,intend）

if（（end-begin+1）<

4）BruteForce（L,closenode,begin,end）;

intmid=（begin+end）/2;

intmidX=L.data[mid].x;

DivideAndConquer（L,closenode,begin,mid）;

DivideAndConquer（L,closenode,mid+1,end）;

Middle（L,closenode,mid,midX）;

intmain（）

{

SYSTEMTIMEsys;

GetLocalTime（&

sys）;

NListlist;

CloseNodeclosenode;

closenode.space=10000;

create（list）;

各点坐标为:

list.count;

cout<

X="

list.data[i].x<

Y="

list.data[i].y<

BruteForce（list,closenode,0,list.count-1）;

用蛮力法求最近对:

sys.wHour<

:

sys.wMinute<

sys.wMilliseconds;

最近对为点（"

closenode.a.x<

"

closenode.a.y<

）和点（"

closenode.b.x<

closenode.b.y<

）\n"

最近距离为:

"

sqrt（closenode.space）<

===================================================================="

用分治法求最近对:

MergeSort（list）;

经过归并排序后的各点:

for（intj=0;

++j）

list.data[j].x<

list.data[j].y<

DivideAndConquer（list,closenode,0,list.count-1）;

return0;

实验结果分析

第1组数据:

24592673

第2组数据:

-118534-4517568574824851-15-24-41273516

执行前

的时间

执行后

所用时间

蛮力法

16:

01:

29:

43

30:

00

00:

57

09

分治法

15:

59:

28:

68

18

50

26

35

由以上数据可知，分治法效率比蛮力法效率高。

蛮力法求解最近对问题的过程是：

分别计算每一对点之间的距离，然后找出距离最小的那一对，为了避免对同一对点计算两次距离，只考虑i＜j的那些点对（Pi,Pj）。

其实也就是组合的问题，即从n个点中选取两个点的所有组合情况的问题，共有（n*（n-1））种情况。

因此时间复杂度为：

治法求解含有n个点的最近对问题，其时间复杂性可由下面的递推式表示：

合并子问题的解的时间f（n）＝O（n），根据通用分治递推式可得T（n）=O（nlog2n）。

体会:

该实验让我学到了分治法的求解过程一般有三个阶段组成：

（1）划分；

（2）求解子问题；

（3）合并。

其中求解子问题大多数采取递归的方法求解。

对于同一个问题可以有多种求解方法，每一种方法的效率各不相同，求解难度也各不相同；

就拿这个实验来说，运用蛮力法求解的算法难度比较低，但是时间复杂度却高；

而运用分治法求解的算法难度较高，而且耗费一定的空间开销，但是效率提高了。

每一种算法各有其优缺点。