分支限界法求旅行售货员问题

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=