算法论文分治法和分支限界.docx

算法论文分治法和分支限界.docx

《算法论文分治法和分支限界.docx》由会员分享，可在线阅读，更多相关《算法论文分治法和分支限界.docx（20页珍藏版）》请在冰点文库上搜索。

算法论文分治法和分支限界

成绩评定表

学生姓名

xx

班级学号

xx

专业

信息与计算科学

课程设计题目

1.分治法解决最近距离问题2.分支限界解决旅行商售货员问题

评

语

组长签字：

成绩

日期

20年月日

课程设计任务书

学院

理学院

专业

信息与计算科学

学生姓名

xx

班级学号

xx

课程设计题目

1.分治法解决最近距离问题2.分支限界解决旅行商售货员问题

实践教学要求与任务:

1、巩固和加深对计算机算法分析与设计基本知识的理解。

2、初步掌握简单软件的分析方法和设计方法。

3、了解与课程有关的工程技术规范，能正确解释和分析设计结果。

4、具体任务

（1）分治法解决最近距离问题

（2）分支限界解决旅行商售货员问题

工作计划与进度安排:

第一天查阅资相关料；第二、三天程序设计；

第四天程序调试；第五天答辩

指导教师：

201年月日

专业负责人：

201年月日

学院教学副院长：

201年月日

摘要

计算效率是一个古老的研究课题。

科学技术的发展使得计算日趋复杂，计算量越来越大，许多理论上可计算的问题，常常由于其计算量巨大布变成了现实不可计算的问题，这就产生了理论可计算而现实不可计算的矛盾，而算法设计与分析的任务就是对各类具体的问题设计高质量的算法，以及研究设计算法的一般规律和方法。

常用的算法设计方法主要有分治法、动态规划、贪婪法和回溯法等。

问题一：

运用分治法对多点最近距离问题进行算法设计，把问题分解为不是相互独立的子问题，计算保存子问题的答案，从而再求重复子问题时可以直接找到答案。

通过反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。

问题二：

运用分支限界对旅行商售货员问题进行算法设计，求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

）分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界；然后按照广度优先策略遍历问题的解空间树，在某一分支上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值（对最小化问题，估算结点的下界，对最大化问题，估算结点的上界）。

如果某孩子结点的目标函数值超出目标函数的界，则将其丢弃（从此结点生成的解不会比目前已得的更好），否则入待处理。

关键词：

算法设计与分析；分支限界法；分治法

1分治法解决最近距离问题

1.1问题描述

已知集合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），如图1.1：

图1.1

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

1.2算法设计

　　分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

　　分治策略是：

对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

这种算法设计策略叫做分治法。

　　如果原问题可分割成k个子问题，1

由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。

在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。

这自然导致递归过程的产生。

分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

分治法在每一层递归上都有三个步骤：

　　分解：

将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

　　解决：

若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；

　　合并：

将各个子问题的解合并为原问题的解。

分治法所能解决的问题一般具有以下几个特征：

　　1）该问题的规模缩小到一定的程度就可以容易地解决

　　2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

　　3）利用该问题分解出的子问题的解可以合并为该问题的解；

　　4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

算法的时间复杂度：

首先对点集S的点x坐标和y坐标进行升序排序，需要循环2nlogn次，复杂度为O（2nlogn）

接下来在分治过程中，对于每个S'yL中的点，都需要与S'yR中的6个点进行比较

O（n）=2O（n/2）+（n/2）*6（一个点集划分为左右两个点集，时间复杂度为左右两个点集加上中间区域运算之和）

其解为O（n）

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

1.3算法实现

#include

#include

structPoint{

doublex;

doubley;

};

doubleClosestPoints（PointS[],intn）

{

inti,j,a=0,b=0,c=0;

intp=0,q=0;

doubledmin,k=99999.0,d1,d2,d,r[25],m,sum=0;

Pointtemp,S1[5],S2[5],P1[5],P2[5];

if（n<2）

returnk;

for（i=0;i

for（j=n-1;j>=i;j--）{

if（S[j].x

temp=S[j];

S[j]=S[j-1];

S[j-1]=temp;

}

}

}

for（i=0;i

sum+=S[i].x;

}

m=sum/（float）n;

for（i=0;i

if（S[i].x

S1[a++]=S[i];

}

else

S2[b++]=S[i];

}

d1=ClosestPoints（S1,a）;

d2=ClosestPoints（S2,b）;

if（d1

d=d1;

else

d=d2;

for（i=0;i

if（abs（S1[i].x-m）

P1[p++]=S1[i];

}

for（i=0;i

if（abs（S2[i].x-m）

P2[q++]=S2[i];

}

for（i=0;i

for（j=p-1;j>=i;j--）{

if（P1[j].y

temp=P1[j];

P1[j]=P1[j-1];

P1[j-1]=temp;

}

}

}

for（i=0;i

for（j=q-1;j>=i;j--）{

if（P2[j].y

temp=P2[j];

P2[j]=P2[j-1];

P2[j-1]=temp;

}

}

}

dmin=abs（P2[0].y-P1[0].y）;

for（i=0;i

for（j=0;j

if（abs（P2[i].y-P1[j].y）

r[c++]=sqrt（（P1[i].x-P2[j].x）*（P1[i].x-P2[j].x）+（P1[i].y-P2[j].y）*（P1[i].y-P2[j].y））;

}

}

}

dmin=r[0];

for（i=0;i

if（r[i]

dmin=r[i];

}

if（d

returnd;

else

returndmin;

}

voidmain（）{

inti,n;

PointS[100];

cout<<"请输入点的个数（小于等于100的正整数）:

"<

cin>>n;

cout<<"请输入平面上的"<

"<

for（i=0;i

cin>>S[i].x>>S[i].y;

cout<<"平面上最近两个点间的距离为：

"<

}

1.4运行结果与分析

图1.2问题1运行结果

输入4个不同点的坐标分别为[4，5],[6，1],[2，10],[7，8],输出平面上最近两个点的距离为4.47214。

根据多组测试的数据来看，分治法解决该问题得效率比蛮力法要高效的多，但是如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

2分支限界解决旅行商售货员问题

2.1问题描述

某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。

他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程（或总旅费）最小。

路线是一个带权图。

如图1.3中各边的费用（权）为正数。

图1.3的一条周游路线是包括V中的每个顶点在内的一条回路。

周游路线的费用是这条路线上所有边的费用之和。

旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。

旅行售货员问题要在图1.3中找出费用最小的周游路线。

图1.3

2.2算法设计

分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。

但在一般情况下，分支限界法与回溯法的求解目标不同。

回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

针对本问题我们可以得出：

1.利用二维数组保存图信息City_Graph[MAX_SIZE][MAX_SIZE],其中City_Graph[i][j]的值代表的是城市i与城市j之间的路径费用,一旦一个城市没有通向另外城市的路，则不可能有回路，不用再找下去了

2.我们可以任意选择一个城市，作为出发点。

（因为最后都是一个回路，无所谓从哪出发）。

算法的基本思路：

首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。

如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。

当s

由于当前扩展结点所相应的路径是x[0:

s]，其可行儿子结点是从剩余顶点x[s+1:

n-1]中选取的顶点x[i]，且（x[s]，x[i]）是所给有向图G中的一条边。

对于当前扩展结点的每一个可行儿子结点，计算出其前缀（x[0:

s]，x[i]）的费用cc和相应的下界lcost。

当lcost

当s=n-1时，已找到的回路前缀是x[0:

n-1]，它已包含图G的所有n个顶点。

因此，当s=n-1时，相应的扩展结点表示一个叶结点，此时该叶结点所相应的回路的费用等于cc和lcost的值，剩余的活结点的lcost值不小于已找到的回路的费用，它们都不可能导致费用更小的回路。

因此已找到叶结点所相应的回路是一个最小费用旅行售货员回路，算法结束时返回找到的最小费用，相应的最优解由数组v给出。

2.3算法实现

#include

#include

usingnamespacestd;

//---------------------宏定义------------------------------------------

#defineMAX_CITY_NUMBER10//城市最大数目

#defineMAX_COST10000000//两个城市之间费用的最大值

//---------------------全局变量----------------------------------------

intCity_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER];

//表示城市间边权重的数组

intCity_Size;//表示实际输入的城市数目

intBest_Cost;//最小费用

intBest_Cost_Path[MAX_CITY_NUMBER];

//最小费用时的路径

//------------------------定义结点---------------------------------------

typedefstructNode{

intlcost;//优先级

intcc;//当前费用

intrcost;//剩余所有结点的最小出边费用的和

ints;//当前结点的深度，也就是它在解数组中的索引位置

intx[MAX_CITY_NUMBER];//当前结点对应的路径

structNode*pNext;//指向下一个结点

}Node;

//---------------------定义堆和相关对操作--------------------------------

typedefstructMiniHeap{

Node*pHead;//堆的头

}MiniHeap;

//初始化

voidInitMiniHeap（MiniHeap*pMiniHeap）{

pMiniHeap->pHead=newNode;

pMiniHeap->pHead->pNext=NULL;

}

//入堆

voidput（MiniHeap*pMiniHeap,Nodenode）{

Node*next;

Node*pre;

Node*pinnode=newNode;//将传进来的结点信息copy一份保存

//这样在函数外部对node的修改就不会影响到堆了

pinnode->cc=node.cc;

pinnode->lcost=node.lcost;

pinnode->pNext=node.pNext;

pinnode->rcost=node.rcost;

pinnode->s=node.s;

pinnode->pNext=NULL;

for（intk=0;k

pinnode->x[k]=node.x[k];

}

pre=pMiniHeap->pHead;

next=pMiniHeap->pHead->pNext;

if（next==NULL）{

pMiniHeap->pHead->pNext=pinnode;

}

else{

while（next!

=NULL）{

if（（next->lcost）>（pinnode->lcost））{//发现一个优先级大的，则置于其前面

pinnode->pNext=pre->pNext;

pre->pNext=pinnode;

break;//跳出

}

pre=next;

next=next->pNext;

}

pre->pNext=pinnode;//放在末尾

}

}

//出堆

Node*RemoveMiniHeap（MiniHeap*pMiniHeap）{

Node*pnode=NULL;

if（pMiniHeap->pHead->pNext!

=NULL）{

pnode=pMiniHeap->pHead->pNext;

pMiniHeap->pHead->pNext=pMiniHeap->pHead->pNext->pNext;

}

returnpnode;

}

//---------------------分支限界法找最优解--------------------------------

voidTraveler（）{

inti,j;

inttemp_x[MAX_CITY_NUMBER];

Node*pNode=NULL;

intminiSum;//所有结点最小出边的费用和

intminiOut[MAX_CITY_NUMBER];

//保存每个结点的最小出边的索引

MiniHeap*heap=newMiniHeap;//分配堆

InitMiniHeap（heap）;//初始化堆

miniSum=0;

for（i=0;i

miniOut[i]=MAX_COST;//初始化时每一个结点都不可达

for（j=0;j

if（City_Graph[i][j]>0&&City_Graph[i][j]

//从i到j可达，且更小

miniOut[i]=City_Graph[i][j];

}

}

if（miniOut[i]==MAX_COST）{//i城市没有出边

Best_Cost=-1;

return;

}

miniSum+=miniOut[i];

}

for（i=0;i

Best_Cost_Path[i]=i;

}

Best_Cost=MAX_COST;//初始化的最优费用是一个很大的数

pNode=newNode;//初始化第一个结点并入堆

pNode->lcost=0;//当前结点的优先权为0也就是最优

pNode->cc=0;//当前费用为0（还没有开始旅行）

pNode->rcost=miniSum;//剩余所有结点的最小出边费用和就是初始化的miniSum

pNode->s=0;//层次为0

pNode->pNext=NULL;

for（intk=0;k

pNode->x[k]=Best_Cost_Path[k];//第一个结点所保存的路径也就是初始化的路径

}

put（heap,*pNode）;//入堆

while（pNode!

=NULL&&（pNode->s）

//堆不空不是叶子

for（intk=0;k

Best_Cost_Path[k]=pNode->x[k];//将最优路径置换为当前结点本身所保存的

}

/*

**pNode结点保存的路径中的含有这条路径上所有结点的索引

**x路径中保存的这一层结点的编号就是x[City_Size-2]

**下一层结点的编号就是x[City_Size-1]

*/

if（（pNode->s）==City_Size-2）{//是叶子的父亲

intedge1=City_Graph[（pNode->x）[City_Size-2]][（pNode->x）[City_Size-1]];

intedge2=City_Graph[（pNode->x）[City_Size-1]][（pNode->x）[0]];

if（edge1>=0&&edge2>=0&&（pNode->cc+edge1+edge2）

//edge1-1表示不可达

//叶子可达起点费用更低

Best_Cost=pNode->cc+edge1+edge2;

pNode->cc=Best_Cost;

pNode->lcost=Best_Cost;//优先权为Best_Cost

pNode->s++;//到达叶子层

}

}

else{//内部结点

for（i=pNode->s;i

if（City_Graph[pNode->x[pNode->s]][pNode->x[i]]>=0）{//可达

//pNode的层数就是它在最优路径中的位置

inttemp_cc=pNode->cc+City_Graph[pNode->x[pNode->s]][pNode->x[i]];

inttemp_rcost=pNode->rcost-miniOut[pNode->x[pNode->s]];

//下一个结点的剩余最小出边费用和

//等于当前结点的rcost减去当前这个结点的最小出边费用

if（temp_cc+temp_rcost

for（j=0;j

temp_x[j]=Best_Cost_Path[j];

}

temp_x[pNode->x[pNode->s+1]]=Best_Cost_Path[i];

//将当前结点的编号放入路径的深度为s+1的地方

temp_x[i]=