《分支限界法求旅行售货员问答物联》由会员分享，可在线阅读，更多相关《分支限界法求旅行售货员问答物联（37页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计实验报告第X次实验姓名刘悦学号201308080112班级物联1301班时间12.26上午地点工训楼C栋309实验名称分支限界法求旅行售货员问题实验目的通过上机实验，掌握分支限界算法的思想，利用Dijkstra 算法求解最短路 径并实现。实验原理使用一个优先队列来存储活结点。优先队列中的每个活结点都存储从根到该活结点的相应路径。算法开始创建一个最小堆，表示活结点优先队列。堆中每个结点的Icost值是优先队列的优先级。接着计算出图中每个顶点的最小费用出边并用Min out记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法结束。如果每个顶点都有出边，则根据计算出的Mi
2、n out作算法初始化。算法第一个扩展结点是排列树中根结点唯一的儿子结点。在该结点处，已确定的回路中的唯一顶点为顶点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中
3、选取的顶点xi,且(xs,xi)是有向图G的一条边。对于当前扩展结点的每一个可行儿子结 点,计算出其前缀(xO:s,xi)的费用cc和相应的下界Icost。当lcostbestc 时,将这个可行儿子结点插入到活结点优先队列中。算法结束时返回找到的最小费用，相应的最优解由数组v给出。 算法开始创建一个最小堆，表示活结点优先队列。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法结束。如果每个顶点都有出边，则根据计算出的Min out作算法初始化。算法第一个扩展结点是排列树中根结点唯一的儿子结点。实验步骤 算法的终止条件是排列树的叶结点成为扩展结点。当s=n-2时,当前扩展结点是排列树中
4、某个叶结点的父结点。如果该叶结点相应的一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则去掉该叶结点。 当sn-2时，算法依次产生当前扩展结点的所有儿子结点。/定义图的顶点数const int N = 4;关键代码/*=疋义Traveling类来存储的信息。*/templateclass Typeclass Traveli ngpublic:Type BBTSP(i nt v);int n;/图G的顶点数Type *a,/图G的邻接矩阵/ NoEdge,/图G的无边标识cc,/当前费用bestc;/当前最小费用;/*疋义MinHeapNode类来存储最小堆中顶点的信息。*l
5、cost表示子树费用的下界。cc表示当前费用。rcost表示xs:n-1中顶点最小出边费用和。s表示根节点到当前节点的路径为x0:s。x表示需要进一步搜索的顶点是xs+1,n-1=*/templateclass Typeclass Mi nHeap Nodefriend Traveli ng;public:operator Type() constreturn lcost;private:Type lcost,/子树费用的下界cc, /当前费用rcost;xs: n-1中顶点最小出边费用和int s,II根节点到当前节点的路径为x0:s*x;II需要进一步搜索的顶点是xs+1,n-1；I*BB
6、TSP函数为使用优先队列求最小费用。这里是使用一个优先队列来存储活结点。优先队列中的每个活结点都存储从根到该活结点的相应路径。算法开始创建一个最小堆，表示活结点优先队列。 堆中每个结点的Icost值是优先队列的优先级。接着计算出图中每个顶点的最小费用出边并用Min out记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法结束。如果每个顶点都有出边，则根据计算出的 Min out作算法初始化。算法第一个扩展结点是排列树中根结点唯一的儿子结点。在该结点处，已确定的回路中的唯一顶点为顶点1.初始时有 s=0,x0=1,x1:n_1=(2,3,n),cc=0，且 rcost 为 Min
7、outi的和，算法 bestc记录当前最优值。算法的终止条件是排列树的叶结点成为扩展结点。当s=n-2时,当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应的一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中,否则去掉该叶结点。当sn-2时,算法依次产生当前扩展结点的所有儿子结点。当前扩展结点所对应的路径是x0:s,其可行儿子结点是从剩余顶点xs+1:n-1中选取的顶点xi,且(xs,xi)是有向图G的一条边。对于当前扩展结点的每一个可行儿子结 点,计算出其前缀(x0:s,xi)的费用cc和相应的下界Icost。当lcostbestc 时,将这个可行儿子结点插入到活结点优
8、先队列中。算法结束时返回找到的最小费用，相应的最优解由数组v给出。*/templateclass TypeType Traveli ng:BBTSP(i nt v)/定义有1000个结点的最小堆Mi nH eapMi nH eapNode H(1000);/动态分配内存Type * MinOut = new Type n+1;/计算MinOuti=顶点i的最小出边费用Type Mi nSum = 0; /最小出边费用和for(i nt i=1; i=n; i+)Type Min = NoEdge;for(i nt j=1; j=n; j+)if(aij!=NoEdge & (aijMi n|M
9、i n=NoEdge)Min = aij;/如果某个顶点没有出边，则该图不可能有回路，算法结束if(Min = NoEdge)retur n NoEdge;Mi nOuti = Mi n;Min Sum += Min;/初始化Mi nHeap Node E;/动态内存分配E.x = new intn;/初始化for(i nt i=0; in; i+)E.xi = i+1;E.s = 0;/根节点到当前节点路径为x0:sE.cc = 0;/当前费用E.rcost = Mi nSum;/最小出边费用和Type bestc = NoEdge;/搜索排列空间树while(E.s n-1)/非叶结点if
10、(E.s = n-2)/当前扩展节点是叶节点的父节点/再加2条边构成回路/所构成回路是否优于当前最优解if(aE.x n-2E.x n-1!=NoEdge&aE.x n-11!=NoEdge& (E.cc+aE.x n-2E.x n-1+aE.x n-11bestc| bestc = NoEdge)/费用更小的回路/记录最小费用bestc = E.cc + aE.x n-2E.x n-1+aE.x n-11;/记录结点的信息E.cc = bestc;E.l cost = bestc;E.s+;/将结点放入最小堆中H.l nsert(E);elsedelete E.x;/ 舍弃扩展节点else/
11、当前扩展节点是叶节点的父节点for(i nt i=E.s+1;i n;i+)if(aE.xE.sE.xi!=NoEdge)/可行儿子节点Type cc = E.cc + aE.xE.sE.xi;Type rcost = E.rcost - Mi nOutE.xE.s;Type b = cc + rcost;/下界if(bbestc | bestc = NoEdge)/子树可能含有最优解/节点插入最小堆Mi nHeap Node N;N.x = new in t n;/保存结点信息for(i nt j=0; j n; j+)N.xj = E.x j;N.xE.s+1 = E.xi;N.xi =
12、E.xE.s+1;N.cc = cc;N.s = E.s + 1;N.lcost = b;N.rcost = rcost;/将结点插入最小堆H.I nsert(N);delete E.x; 完成节点扩展/最小堆空了就结束if(H.Size() = 0)break;H.DeleteMi n(E);取下一扩展节点/如果最小费用为 NoEdge,则图中无回路if(bestc = NoEdge)return NoEdge;/ 无回路/将最优解复制到v1:nfor(i nt i=0; i2-3_4-1M661 -2-4-_3-1N251-3-2_4-1O661-3-4-2-1P251-4-2-3-1Q591-4
