![分支限界法求旅行售货员问题_第1页](http://file1.renrendoc.com/fileroot_temp2/2021-1/25/740b5f26-5c6c-4cae-9e93-d31fa37ce822/740b5f26-5c6c-4cae-9e93-d31fa37ce8221.gif)
![分支限界法求旅行售货员问题_第2页](http://file1.renrendoc.com/fileroot_temp2/2021-1/25/740b5f26-5c6c-4cae-9e93-d31fa37ce822/740b5f26-5c6c-4cae-9e93-d31fa37ce8222.gif)
![分支限界法求旅行售货员问题_第3页](http://file1.renrendoc.com/fileroot_temp2/2021-1/25/740b5f26-5c6c-4cae-9e93-d31fa37ce822/740b5f26-5c6c-4cae-9e93-d31fa37ce8223.gif)
![分支限界法求旅行售货员问题_第4页](http://file1.renrendoc.com/fileroot_temp2/2021-1/25/740b5f26-5c6c-4cae-9e93-d31fa37ce822/740b5f26-5c6c-4cae-9e93-d31fa37ce8224.gif)
![分支限界法求旅行售货员问题_第5页](http://file1.renrendoc.com/fileroot_temp2/2021-1/25/740b5f26-5c6c-4cae-9e93-d31fa37ce822/740b5f26-5c6c-4cae-9e93-d31fa37ce8225.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、.算法分析与设计实验报告第 X 次实验姓名刘悦学号2班级物联1301班时间12.26上午地点工训楼C栋309 实验名称分支限界法求旅行售货员问题实验目的 通过上机实验,掌握分支限界算法的思想,利用Dijkstra 算法求解最短路径并实现。实验原理使用一个优先队列来存储活结点。优先队列中的每个活结点都存储从根到该活结点的相应路径。算法开始创建一个最小堆,表示活结点优先队列。堆中每个结点的lcost值是优先队列的优先级。接着计算出图中每个顶点的最小费用出边并用Minout记录。如果所给的有向图中某个顶点没有出边,则该图不可能有回路,算法结束。如果每个顶点都有出边,则根据计算出的Minout作算法初
2、始化。算法第一个扩展结点是排列树中根结点唯一的儿子结点。在该结点处,已确定的回路中的唯一顶点为顶点1.初始时有s=0,x0=1,x1:n-1=(2,3,n),cc=0,且rcost为Minouti的和,算法bestc记录当前最优值。 算法的终止条件是排列树的叶结点成为扩展结点。 当s=n-2时,当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应的一条可行回路且费用小于当前最小费用,则将该叶结点插入到优先队列中,否则去掉该叶结点。 当sn-2时,算法依次产生当前扩展结点的所有儿子结点。当前扩展结点所对应的路径是x0:s,其可行儿子结点是从剩余顶点xs+1:n-1中选取的顶点xi,且(xs
3、,xi)是有向图G的一条边。对于当前扩展结点的每一个可行儿子结点,计算出其前缀(x0:s,xi)的费用cc和相应的下界lcost。当lcostbestc时,将这个可行儿子结点插入到活结点优先队列中。 算法结束时返回找到的最小费用,相应的最优解由数组v给出。实验步骤 算法开始创建一个最小堆,表示活结点优先队列。 如果所给的有向图中某个顶点没有出边,则该图不可能有回路,算法结束。如果每个顶点都有出边,则根据计算出的Minout作算法初始化。 算法第一个扩展结点是排列树中根结点唯一的儿子结点。 算法的终止条件是排列树的叶结点成为扩展结点。 当s=n-2时,当前扩展结点是排列树中某个叶结点的父结点。如
4、果该叶结点相应的一条可行回路且费用小于当前最小费用,则将该叶结点插入到优先队列中,否则去掉该叶结点。 当sn-2时,算法依次产生当前扩展结点的所有儿子结点。关键代码/定义图的顶点数 const int N = 4; /*=定义Traveling类来存储的信息。=*/ template class Traveling public: Type BBTSP(int v); int n; /图G的顶点数 Type *a, /图G的邻接矩阵 / NoEdge, /图G的无边标识 cc, /当前费用 bestc; /当前最小费用 ; /*= 定义MinHeapNode类来存储最小堆中顶点的信息。* lc
5、ost表示子树费用的下界。 cc表示当前费用。 rcost表示xs:n-1中顶点最小出边费用和。 s表示根节点到当前节点的路径为x0:s。 x表示需要进一步搜索的顶点是xs+1,n-1。 =*/ template class MinHeapNode friend Traveling; public: operator Type() const return lcost; private: Type lcost, /子树费用的下界 cc, /当前费用 rcost; /xs:n-1中顶点最小出边费用和 int s, /根节点到当前节点的路径为x0:s *x; /需要进一步搜索的顶点是xs+1,n-
6、1; /*=BBTSP函数为使用优先队列求最小费用。 这里是使用一个优先队列来存储活结点。优先队列中的每个活结点都存储从根到该活结点的相应路径。算法开始创建一个最小堆,表示活结点优先队列。堆中每个结点的lcost值是优先队列的优先级。接着计算出图中每个顶点的最小费用出边并用Minout记录。如果所给的有向图中某个顶点没有出边,则该图不可能有回路,算法结束。如果每个顶点都有出边,则根据计算出的Minout作算法初始化。算法第一个扩展结点是排列树中根结点唯一的儿子结点。在该结点处,已确定的回路中的唯一顶点为顶点1.初始时有s=0,x0=1,x1:n-1=(2,3,n),cc=0,且rcost为Mi
7、nouti的和,算法bestc记录当前最优值。 算法的终止条件是排列树的叶结点成为扩展结点。 当s=n-2时,当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应的一条可行回路且费用小于当前最小费用,则将该叶结点插入到优先队列中,否则去掉该叶结点。 当sn-2时,算法依次产生当前扩展结点的所有儿子结点。当前扩展结点所对应的路径是x0:s,其可行儿子结点是从剩余顶点xs+1:n-1中选取的顶点xi,且(xs,xi)是有向图G的一条边。对于当前扩展结点的每一个可行儿子结点,计算出其前缀(x0:s,xi)的费用cc和相应的下界lcost。当lcostbestc时,将这个可行儿子结点插入到活结点
8、优先队列中。 算法结束时返回找到的最小费用,相应的最优解由数组v给出。 =*/ template Type Traveling:BBTSP(int v) /定义有1000个结点的最小堆 MinHeapMinHeapNode H(1000); /动态分配内存 Type * MinOut = new Typen+1; /计算MinOuti = 顶点i的最小出边费用 Type MinSum = 0; /最小出边费用和 for(int i=1; i=n; i+) Type Min = NoEdge; for(int j=1; j=n; j+) if(aij!=NoEdge & (aijMin|Min=
9、NoEdge) Min = aij; /如果某个顶点没有出边,则该图不可能有回路,算法结束 if(Min = NoEdge) return NoEdge; MinOuti = Min; MinSum += Min; /初始化 MinHeapNode E;/动态内存分配 E.x = new intn; /初始化 for(int i=0; in; i+) E.xi = i+1; E.s = 0; /根节点到当前节点路径为x0:s E.cc = 0; /当前费用 E.rcost = MinSum;/最小出边费用和 Type bestc = NoEdge; /搜索排列空间树 while(E.sn-1)
10、/非叶结点 if(E.s = n-2)/当前扩展节点是叶节点的父节点 /再加2条边构成回路 /所构成回路是否优于当前最优解 if(aE.xn-2E.xn-1!=NoEdge & aE.xn-11!=NoEdge & (E.cc+aE.xn-2E.xn-1+aE.xn-11bestc | bestc = NoEdge) /费用更小的回路/记录最小费用 bestc = E.cc + aE.xn-2E.xn-1+aE.xn-11; /记录结点的信息 E.cc = bestc; E.lcost = bestc; E.s+;/将结点放入最小堆中 H.Insert(E); else delete E.x;
11、/舍弃扩展节点 else/当前扩展节点是叶节点的父节点 for(int i=E.s+1;in;i+) if(aE.xE.sE.xi!=NoEdge) /可行儿子节点 Type cc = E.cc + aE.xE.sE.xi; Type rcost = E.rcost - MinOutE.xE.s; Type b = cc + rcost;/下界 if(bbestc | bestc = NoEdge) /子树可能含有最优解 /节点插入最小堆 MinHeapNode N; N.x = new intn;/保存结点信息 for(int j=0; jn; j+) N.xj = E.xj; N.xE.s
12、+1 = E.xi; N.xi = E.xE.s+1; N.cc = cc; N.s = E.s + 1; N.lcost = b; N.rcost = rcost; /将结点插入最小堆 H.Insert(N); delete E.x;/完成节点扩展 /最小堆空了就结束 if(H.Size() = 0) break; H.DeleteMin(E);/取下一扩展节点 /如果最小费用为NoEdge,则图中无回路 if(bestc = NoEdge) return NoEdge;/无回路 /将最优解复制到v1:n for(int i=0; i2 -3 -4-1M661 -2 -4 -3-1N251
13、-3 -2 -4-1O661 -3 -4-2-1P251 -4 -2 -3-1Q591 -4 -3 -2-14. 由上表可以知道最短的为至叶结点Q的路径1 -3 -2 -4-1,长度为25。这里可能会有疑问,至结点P的距离也为25,为什么不选择路径1 -4 -2 -3-1。这是因为只有当求得的路径比当前最优值小的时候才会记录,这里一样大,所以不会记录,也就不会输出这条路径。5. 算法输出结果如下:输出图的顶点个数。输出最短路径。输出最短路径的长度。输出时间。6. 可以看到输出的结果与分析的结果一样,所以算法实现正确。并且可以看到分支限界法在实现我们给的这个图的时候,时间性能很好。实验心得说实话
14、,个人觉得旅行售货员问题的实现算法不好写,因为旅行售货员问题的解空间是一棵排列树,个人觉得排列树较子集树来说,更加难以理解。这个算法的实现中,有一个地方卡了很久,虽然可以通过尝试数值的方法来确定到底是哪个,但是还是觉得自己理解了比较好,毕竟不是什么东西都可以挨个值试出来的,如果有一个问题有很多可能的数值如果要试的话会很费时间。卡了很久的地方就是当前扩展结点是叶结点的父结点的时候s(层数)的数值是什么。这个算法中是子集树的第二层的时候s为0。拿我们给的这个图的例子来说,就是B那一层s=0。所以当前扩展结点是叶结点的父结点的时候s应该等于n-2,而不是n-1。这里是因为算法的第1个扩展结点是排列树
15、中唯一儿子结点。在该结点处,已经确定的回路中唯一顶点为顶点1。像我刚刚说的,如果不知道到底是哪个值的话,可以依次尝试一下n、n-1和n-2这三个值,看为哪个值的时候输出正确的最短路径。这里的这个代码的编写主要是用来与前面的回溯法进行比较。回溯法主要是使用的深度优先的探索,就是从一个子结点向下扩展,一直扩展到叶子结点或者不能继续向下扩展。而这里的分支限界法是宽度优先的扩展策略,这里使用的是优先队列来实现的话,就是每次扩展优先级最小的结点。因为给定的这个图的结点比较少,所以两个算法输出的时间都为0,无法通过这一组测试数据给出两种算法的时间比较分析。通过这次实验,编写了分支限界法求旅行售货员问题,掌
16、握了分支限界法求解问题的基本步骤,掌握了旅行售货员问题的问题描述,求解过程。相信在以后的学习工作中可以熟练使用分支限界法求解问题,也可以使用多种方法求解旅行售货员问题。实验得分助教签名附录:完整代码#include MinHeap.h #include #include#include#include#include#define NoEdge -1 using namespace std; /定义图的顶点数 const int N = 4; /*=定义Traveling类来存储的信息。=*/ template class Traveling public: Type BBTSP(int v)
17、; int n; /图G的顶点数 Type *a, /图G的邻接矩阵 / NoEdge, /图G的无边标识 cc, /当前费用 bestc; /当前最小费用 ; /*= 定义MinHeapNode类来存储最小堆中顶点的信息。* lcost表示子树费用的下界。 cc表示当前费用。 rcost表示xs:n-1中顶点最小出边费用和。 s表示根节点到当前节点的路径为x0:s。 x表示需要进一步搜索的顶点是xs+1,n-1。 =*/ template class MinHeapNode friend Traveling; public: operator Type() const return lcos
18、t; private: Type lcost, /子树费用的下界 cc, /当前费用 rcost; /xs:n-1中顶点最小出边费用和 int s, /根节点到当前节点的路径为x0:s *x; /需要进一步搜索的顶点是xs+1,n-1; /*=BBTSP函数为使用优先队列求最小费用。 这里是使用一个优先队列来存储活结点。优先队列中的每个活结点都存储从根到该活结点的相应路径。算法开始创建一个最小堆,表示活结点优先队列。堆中每个结点的lcost值是优先队列的优先级。接着计算出图中每个顶点的最小费用出边并用Minout记录。如果所给的有向图中某个顶点没有出边,则该图不可能有回路,算法结束。如果每个顶
19、点都有出边,则根据计算出的Minout作算法初始化。算法第一个扩展结点是排列树中根结点唯一的儿子结点。在该结点处,已确定的回路中的唯一顶点为顶点1.初始时有s=0,x0=1,x1:n-1=(2,3,n),cc=0,且rcost为Minouti的和,算法bestc记录当前最优值。 算法的终止条件是排列树的叶结点成为扩展结点。 当s=n-2时,当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应的一条可行回路且费用小于当前最小费用,则将该叶结点插入到优先队列中,否则去掉该叶结点。 当sn-2时,算法依次产生当前扩展结点的所有儿子结点。当前扩展结点所对应的路径是x0:s,其可行儿子结点是从剩余
20、顶点xs+1:n-1中选取的顶点xi,且(xs,xi)是有向图G的一条边。对于当前扩展结点的每一个可行儿子结点,计算出其前缀(x0:s,xi)的费用cc和相应的下界lcost。当lcostbestc时,将这个可行儿子结点插入到活结点优先队列中。 算法结束时返回找到的最小费用,相应的最优解由数组v给出。 =*/ template Type Traveling:BBTSP(int v) /定义有1000个结点的最小堆 MinHeapMinHeapNode H(1000); /动态分配内存 Type * MinOut = new Typen+1; /计算MinOuti = 顶点i的最小出边费用 Ty
21、pe MinSum = 0; /最小出边费用和 for(int i=1; i=n; i+) Type Min = NoEdge; for(int j=1; j=n; j+) if(aij!=NoEdge & (aijMin|Min=NoEdge) Min = aij; /如果某个顶点没有出边,则该图不可能有回路,算法结束 if(Min = NoEdge) return NoEdge; MinOuti = Min; MinSum += Min; /初始化 MinHeapNode E;/动态内存分配 E.x = new intn; /初始化 for(int i=0; in; i+) E.xi =
22、i+1; E.s = 0; /根节点到当前节点路径为x0:s E.cc = 0; /当前费用 E.rcost = MinSum;/最小出边费用和 Type bestc = NoEdge; /搜索排列空间树 while(E.sn-1)/非叶结点 if(E.s = n-2)/当前扩展节点是叶节点的父节点 /再加2条边构成回路 /所构成回路是否优于当前最优解 if(aE.xn-2E.xn-1!=NoEdge & aE.xn-11!=NoEdge & (E.cc+aE.xn-2E.xn-1+aE.xn-11bestc | bestc = NoEdge) /费用更小的回路/记录最小费用 bestc =
23、E.cc + aE.xn-2E.xn-1+aE.xn-11; /记录结点的信息 E.cc = bestc; E.lcost = bestc; E.s+;/将结点放入最小堆中 H.Insert(E); else delete E.x;/舍弃扩展节点 else/当前扩展节点是叶节点的父节点 for(int i=E.s+1;in;i+) if(aE.xE.sE.xi!=NoEdge) /可行儿子节点 Type cc = E.cc + aE.xE.sE.xi; Type rcost = E.rcost - MinOutE.xE.s; Type b = cc + rcost;/下界 if(bbestc
24、| bestc = NoEdge) /子树可能含有最优解 /节点插入最小堆 MinHeapNode N; N.x = new intn;/保存结点信息 for(int j=0; jn; j+) N.xj = E.xj; N.xE.s+1 = E.xi; N.xi = E.xE.s+1; N.cc = cc; N.s = E.s + 1; N.lcost = b; N.rcost = rcost; /将结点插入最小堆 H.Insert(N); delete E.x;/完成节点扩展 /最小堆空了就结束 if(H.Size() = 0) break; H.DeleteMin(E);/取下一扩展节点
25、/如果最小费用为NoEdge,则图中无回路 if(bestc = NoEdge) return NoEdge;/无回路 /将最优解复制到v1:n for(int i=0; in; i+) vi+1 = E.xi; while(true)/释放最小堆中所有节点 delete E.x; if(H.Size() = 0) break; H.DeleteMin(E);/取下一扩展节点 return bestc; /*=main函数是主函数。实现输入输出,调用之前的分支限界法函数BBTSP求得最优值,并且通过数组v得到最优解。输出最短路径和最短路径的长度。 =*/ int main() cout=end
26、l;cout=分支限界法求TSP问题=endl;cout=endl; int bestxN+1;int bestlength; /输出图的顶点个数 cout图的顶点个数为:Nendl; /动态内存分配 int *a=new int*N+1; for(int i=0;i=N;i+) ai=new intN+1;/初始化 for(int i=0;i=N;i+)for(int j=0;jN;j+) aij=NoEdge; a12=30;a13=6;a14=4; a21=30;a23=5;a24=10; a31=6;a32=5;a34=20; a41=4;a42=10;a43=20; /定义Traveling类型的变量t Traveling t; /给变量t赋初值 t.a = a; t.n = N; /开始计时 clock_t start,end,over;start=clock();end=clock();over=end-start;start=clock();/调用函数 bestlength=t.BBTSP(bestx); /结束计时 end=clock();/输出最短回路 cout最短回路为:endl; for(int i=
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 避震山地车项目可行性实施报告
- 贵州省铜仁地区印江土家族苗族自治县2024届三年级数学第二学期期末学业水平测试模拟试题含解析
- 贵州省黔西南市2024-2025学年下学期初三英语试题期初联考考试试卷含答案
- 贵州省黔南州名校2025年下学期初三语文试题第一次联考考试试卷含解析
- 2024-2034年全球及中国动态电压恢复器行业市场发展分析及前景趋势与投资发展研究报告
- 学校设置体育教练员岗位的实施细则
- 公共标识语英译新20问
- 2024年版体育用品品牌代理与销售合同书
- 简约商务述职报告
- 三年级数学万以内加减法题同步检测例题大全附答案
- 五星级酒店样板间检查表中英文对照
- 发票、原始凭证分割单(大写自动填写)
- 外贸报价单模板
- 物业公司组织架构图
- 云南省用人单位人员就业录用登记表-就业登记
- 水文信息学第八水位流量关系讲解
- 第一章 非物质文化遗产概论
- 心脏起搏的护理课件
- 接地电阻测量.ppt
- 各型法兰用螺栓规格对照表(最新)
- (完整word版)施工日报、周报、月报样本
评论
0/150
提交评论