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

1、成绩评定表学生XX班级学号XX专业信息与计算科学课程设计题目1.分治法解决最近 距离问题2.分支限 界解决旅行商售货 员问题评语组长签字：成绩日期20 年 月曰课程设计任务书学院理学院专业信息与计算科学学生XX班级学号XX课程设计题目1.分治法解决最近距离问题2.分支限界解决旅行商售货员问题实践教学要求与任务：1、巩固和加深对计算机算法分析与设计基本知识的理解。2、初步掌握简单软件的分析方法和设计方法。3、了解与课程有关的工程技术规，能正确解释和分析设计结果。4、具体任务（1）分治法解决最近距离问题（2）分支限界解决旅行商售货员问题工作计划与进度安排：第 天 查阅资相关料；第二、三天 程序设计

2、；第四天程序调试；第五天答辩指导教师：201年 月曰专业负责人：201 年 月曰学院教学副院长：201 年 月曰计算效率是一个古老的研究课题。科学技术的发展使得计算日趋复杂， 计算 量越来越大，许多理论上可计算的问题，常常由于其计算量巨大布变成了现实不 可计算的问题，这就产生了理论可计算而现实不可计算的矛盾， 而算法设计与分 析的任务就是对各类具体的问题设计高质量的算法， 以及研究设计算法的一般规 律和方法。常用的算法设计方法主要有分治法、动态规划、贪婪法和回溯法等。问题一：运用分治法对多点最近距离问题进行算法设计， 把问题分解为不是 相互独立的子问题，计算保存子问题的答案，从而再求重复子问题

3、时可以直接找 到答案。通过反复应用分治手段，可以使子问题与原问题类型一致而其规模却不 断缩小，最终使子问题缩小到很容易直接求出其解。问题二：运用分支限界对旅行商售货员问题进行算法设计， 求解目标则是找 出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优 解。）分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数 的界；然后按照广度优先策略遍历问题的解空间树， 在某一分支上，依次搜索该 结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值 （对最小化 问题，估算结点的下界，对最大化问题，估算结点的上界）。如果某孩子结点的 目标函数值超出目标函数的界，则将其

4、丢弃（从此结点生成的解不会比目前已得 的更好），否则入待处理。关键词：算法设计与分析；分支限界法；分治法.专业整理 .目录1 分治法解决最近距离问题 11.1 问题描述 11.2 算法设计 21.3 算法实现 31.4 运行结果与分析 62 分支限界解决旅行商售货员问题 72.1 问题描述 72.2 算法设计 82.3 算法实现 92.4 运行结果与分析 14总结 15参考文献 161分治法解决最近距离问题1.1问题描述已知集合S中有n个点，分治法的思想就是将S进行拆分，分为2部分求最近点 对。算法每次选择一条垂线L，将S拆分左右两部分为SL和SR L一般取点集S 中所有点的中间点的x坐标来划

5、分，这样可以保证SL和SR中的点数目各为n/2，（否则以其他方式划分S,有可能导致SL和SR中点数目一个为1, 一个为n-1， 不利于算法效率，要尽量保持树的平衡性）依次找出这两部分中的最小点对距离：SL 和S R,记SL和SR中最小点对距离S = min （S L，S R），如图 1.1 :以L为中心，S为半径划分一个长带，最小点对还有可能存在于 SL和SR 的交界处，如图1.1中的虚线带，p点和q点分别位于SL和SR的虚线围，在这 个围，p点和q点之间的距离才会小于 S，最小点对计算才有意义。1.2算法设计分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小 的相同问题，以便

6、各个击破，分而治之。分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说 规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题 互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并 得到原问题的解。这种算法设计策略叫做分治法。如果原问题可分割成k个子问题，1<k< n，且这些子问题都可解并可利用 这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的 子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况 下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小， 最终使子问题缩小到很容易

7、直接求出其解。这自然导致递归过程的产生。分治与 递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。分治法在每一层递归上都有三个步骤：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子 问题；解决：若子问题规模较小而容易被解决则直接解， 否则递归地解各个子问题； 合并：将各个子问题的解合并为原问题的解。分治法所能解决的问题一般具有以下几个特征：1）该问题的规模缩小到一定的程度就可以容易地解决2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结 构性质。3）禾U用该问题分解出的子问题的解可以合并为该问题的解；4）该问题所分解出的各个子问题是相互独

8、立的，即子问题之间不包含公共 的子子问题。第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随 着问题规模的增加而增加；第二条特征是应用分治法的前提它也是大多数问题可 以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法 完全取决于问题是否具有第三条特征， 如果具备了第一条和第二条特征，而不具 备第三条特征，则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的 效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共 的子问题，此时虽然可用分治法，但一般用动态规划法较好。算法的时间复杂度：首先对点集S的点x坐标和y坐标进行升序排序，需要循环2n

9、logn次，复 杂度为0(2nlogn)接下来在分治过程中，对于每个 S'yL中的点，都需要与S'yR中的6个点进 行比较0( n)= 20( n/2) + (n /2)*6(一个点集划分为左右两个点集，时间复杂度为左右两个点集加上中间区域运算之和)其解为 0(n)< 0(3nlogn)因此总的时间复杂度为0(3nlogn)，比蛮力法的0(n2)要高效。1.3算法实现#in clude<iostream.h>#in clude<math.h>struct Poi ntdouble x;double y;double ClosestPoi nts(P

10、oi nt S,i nt n)int i,j,a=O,b=O,c=O;int p=O,q=O;double dmi n,k=99999.0,d1,d2,d,r25,m,sum=0;Poi nt temp,S15,S25,P15,P25;if(n<2)return k;for(i=0;i< n-1;i+)for(j=n-1;j>=i;j-)if(Sj.x<Sj-1.x)temp=Sj;Sj=Sj-1;Sj-1=temp;for(i=0;i< n; i+)sum+=Si.x;m=sum/(float)n;for(i=0;i<n;i+)if(Si.x<m)S

11、1a+=Si;elseS2b+=Si;d1=ClosestPoints(S1,a); d2=ClosestPoints(S2,b); if(d1<d2)d=d1;elsed=d2;for(i=0;i<a;i+) if(abs(S1i.x-m)<d) P1p+=S1i;for(i=0;i<b;i+) if(abs(S2i.x-m)<d) P2q+=S2i;for(i=0;i<p-1;i+) for(j=p-1;j>=i;j-) if(P1j.y<P1j-1.y) temp=P1j;P1j=P1j-1;P1j-1=temp;for(i=0;i<

12、q-1;i+)for(j=q-1;j>=i;j-)if(P2j.y<P2j-1.y)temp=P2j;P2j=P2j-1;P2j-1=temp;dmin=abs(P20.y-P10.y);for(i=0;i<q;i+)for(j=0;j<p;j+) if(abs(P2i.y-P1j.y)<d).专业整理 .rc+=sqrt(P1i.x-P2j.x)*(P1i.x-P2j.x)+(P1i.y-P2j.y)*(P1i.y-P2j .y);dmin=r0;for(i=0;i<c;i+)if(ri<dmin)dmin=ri;if(d<dmin)retur

13、n d;else return dmin;void main()int i,n;Point S100;cout<<" 请输入点的个数 ( 小于等于 100 的正整数 ):"<<endl; cin>>n;cout<<" 请输入平面上的 "<<n<<" 个点的横纵坐标 :"<<endl; for(i=0;i<n;i+)cin>>Si.x>>Si.y;cout<<" 平面上最近两个点间的距离为： "

14、;<<ClosestPoints(S,n)<<endl; 1.4运行结果与分析图1.2问题1运行结果输入4个不同点的坐标分别为4 , 5,6 , 1,2 , 10,7 , 8,输出平面上 最近两个点的距离为4.47214。根据多组测试的数据来看，分治法解决该问题得 效率比蛮力法要高效的多，但是如果各子问题是不独立的则分治法要做许多不必 要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法 较好。2分支限界解决旅行商售货员问题2.1问题描述某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要 选定一条从驻地出发，经过每个城市一次，最后回到

15、驻地的路线，使总的路程（或 总旅费）最小。路线是一个带权图。如图1.3中各边的费用（权）为正数。图1.3的一条周 游路线是包括V中的每个顶点在的一条回路。周游路线的费用是这条路线上所有 边的费用之和。旅行售货员问题的解空间可以组织成一棵树， 从树的根结点到任一叶结点的 路径定义了图的一条周游路线。旅行售货员问题要在图1.3中找出费用最小的周 游路线。图1.32.2算法设计分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。 但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件 的一个解，或

16、是在满足约束条件的解中找出使某一目标函数值达到极大或极小的 解，即在某种意义下的最优解。针对本问题我们可以得出：1.利用二维数组保存图信息 City_GraphMAX_SIZEMAX_SIZE,其中 City_Graphij 的值代表的是城市i与城市j之间的路径费用,一旦一个城市 没有通向另外城市的路，则不可能有回路，不用再找下去了2.我们可以任意选择一个城市，作为出发点。(因为最后都是一个回路，无所谓从哪出发)。算法的基本思路：首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。 如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到 优先队列中，否则舍去

17、该叶结点。当svn-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结 点所相应的路径是xO:s，其可行儿子结点是从剩余顶点 xs+1:n-1中选取的 顶点xi，且(xs ，xi)是所给有向图G中的一条边。对于当前扩展结点的 每一个可行儿子结点，计算出其前缀(x0:s，xi)的费用cc和相应的下界lcost。当Icostvbestc时，将这个可行儿子结点插入到活结点优先队列中，算 法中while循环的终止条件是排列树的一个叶结点成为当前扩展结点。当s=n-1时，已找到的回路前缀是x0:n-1，它已包含图G的所有n个顶点。因 此，当s=n-1时，相应的扩展结点表示一个叶结点，此时该叶结

18、点所相应的回路 的费用等于cc和lcost的值，剩余的活结点的lcost值不小于已找到的回路的 费用，它们都不可能导致费用更小的回路。因此已找到叶结点所相应的回路是一个最小费用旅行售货员回路，算法结束时返回找到的最小费用，相应的最优解由数组V给出。2.3 算法实现#include <stdio.h> #include <istream> using namespace std;/ 宏定义 #define MAX_CITY_NUMBER 10/ 城市最大数目#define MAX_COST 10000000 / 两个城市之间费用的最大值 / 全局变量 int City_G

19、raphMAX_CITY_NUMBERMAX_CITY_NUMBER;/ 表示城市间边权重的数组int City_Size;/ 表示实际输入的城市数目int Best_Cost;/ 最小费用int Best_Cost_PathMAX_CITY_NUMBER;/ 最小费用时的路径/ 定义结点 typedef struct Nodeint lcost;/优先级int cc;/当前费用int rcost;/ 剩余所有结点的最小出边费用的和int s;/当前结点的深度，也就是它在解数组中的索引位置int xMAX_CITY_NUMBER; /当前结点对应的路径struct Node* pNext; /

20、指向下一个结点Node;/ 定义堆和相关对操作 typedef struct MiniHeapNode* pHead; / 堆的头MiniHeap;/ 初始化void InitMiniHeap(MiniHeap* pMiniHeap)pMiniHeap->pHead = new Node; pMiniHeap->pHead->pNext = NULL;/ 入堆void put(MiniHeap* pMiniHeap,Node node)Node* next;Node* pre;Node* pinnode = new Node;/ 将传进来的结点信息 copy 一份保存/ 这样

21、在函数外部对 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(int k=0;k<City_Size;k+) pinnode->xk = node.xk;pre = pMiniHeap->pHead; next = pMiniHeap->pHe

22、ad->pNext; if(next = NULL)pMiniHeap->pHead->pNext = pinnode; elsewhile(next != NULL) if(next->lcost) > (pinnode->lcost)/ 发现一个优先级大的，则置于其pinnode->pNext = pre->pNext; pre->pNext = pinnode; break; /pre = next;next = next->pNext;pre->pNext = pinnode;/ 出堆Node* RemoveMiniHe

23、ap(MiniHeap* pMiniHeap)Node* pnode = NULL; if(pMiniHeap->pHead->pNext != NULL) pnode = pMiniHeap->pHead->pNext;跳出放在末尾pMiniHeap->pHead->pNext = pMiniHeap->pHead->pNext->pNext;return pnode;/ 分支限界法找最优解 void Traveler()int i,j;int temp_xMAX_CITY_NUMBER;Node* pNode = NULL;int mi

24、niSum; /int miniOutMAX_CITY_NUMBER;/所有结点最小出边的费用和MiniHeap* heap = new MiniHeap; /InitMiniHeap(heap); /保存每个结点的最小出边的索引 分配堆 初始化堆miniSum = 0;for (i=0;i<City_Size;i+) miniOuti = MAX_COST; / for(j=0;j<City_Size;j+)初始化时每一个结点都不可达if (City_Graphij>0 && City_Graphij<miniOuti)/miniOuti = City

25、_Graphij;if (miniOuti = MAX_COST)/ i Best_Cost = -1; return ;从 i 到 j 可达，且更小城市没有出边miniSum += miniOuti;for(i=0;i<City_Size;i+) /Best_Cost_Pathi = i;Best_Cost = MAX_COST;/pNode = new Node; / pNode->lcost = 0;/pNode->cc = 0;/pNode->rcost = miniSum;/miniSumpNode->s = 0; / pNode->pNext =

26、 NULL; for(int k=0;k<City_Size;k+) pNode->xk = Best_Cost_Pathk; 化的路径put(heap,*pNode); /初始化的最优路径就是把所有结点依次走一遍初始化的最优费用是一个很大的数初始化第一个结点并入堆当前结点的优先权为 0 也就是最优当前费用为 0(还没有开始旅行)剩余所有结点的最小出边费用和就是初始化的层次为 0/ 第一个结点所保存的路径也就是初始入堆while(pNode != NULL && (pNode->s) < City_Size-1)/堆不空 不是叶子for(int k=0;

27、k<City_Size;k+)Best_Cost_Pathk = pNode->xk ; / 将最优路径置换为当前结点本 身所保存的/* * pNode 结点保存的路径中的含有这条路径上所有结点的索引* * x 路径中保存的这一层结点的编号就是 xCity_Size-2* * 下一层结点的编号就是 xCity_Size-1*/if (pNode->s) = City_Size-2) / 是叶子的父亲int edge1City_Graph(pNode->x)City_Size-2(pNode->x)City_Size-1;int edge2 = City_Graph

28、(pNode->x)City_Size-1(pNode->x)0;if(edge1 >= 0 && edge2 >= 0 && (pNode->cc+edge1+edge2) < Best_Cost)/edge1 -1表示不可达/ 叶子可达起点费用更低Best_Cost = pNode->cc + edge1+edge2; pNode->cc = Best_Cost;pNode->lcost = Best_Cost; / 优先权为 Best_CostpNode->s+;/ 到达叶子层elsefor(i=

29、pNode->s;i<City_Size;i+) 层/部结点从当前层到叶子可达/pNode的层数就是它在最优路径中的位置int temp_cc pNode->cc+City_GraphpNode->xpNode->spNode->xi;int temp_rcost = pNode->rcost-miniOutpNode->xpNode->s;/最小出边费用和/rcost 减去当前这个结点的最小出边费用if (temp_cc+temp_rcost<Best_Cost) /出边费用和小于当前的最优解，说明可能存在更优解for (j=0;j

30、<City_Size;j+) / 便下面修改temp_xj=Best_Cost_Pathj;temp_xpNode->xpNode->s+1 = Best_Cost_Pathi;/放入路径的深度为 s+1 的地方下一个结点的剩余 等于当前结点的 下一个结点的最小 完全 copy 路径， 以将当前结点的编号temp_xi =/ 将原路 / 径中的深度为 s+1 的结点编号放入当前路径的 /的的深度为i的结点与深度W为s+1的结点交换Best_Cost_PathpNode->s+1;相当于将原路径中Node* pNextNode = new Node;if(City_Gra

31、phpNode->xpNode->spNode->xi >= 0) /pNextNode->cc = temp_cc; pNextNode->lcost = temp_cc+temp_rcost; pNextNode->rcost = temp_rcost; pNextNode->s = pNode->s+1; pNextNode->pNext = NULL; for(int k=0;k<City_Size;k+) pNextNode->xk = temp_xk;put(heap,*pNextNode);delete pNextNode;pNode = RemoveMiniHeap(heap);int main()int i,j;printf(" 请输入旅行的节点数： "); scanf("%d",&City_Size); for(i=0;i<City_Size;i+)printf(&