《分支限界法求旅行售货员问题_物联1301班_刘悦_201308080112概要》由会员分享，可在线阅读，更多相关《分支限界法求旅行售货员问题_物联1301班_刘悦_201308080112概要（16页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计实验报告第 X 次实验姓名刘悦学号201308080112班级物联1301班时间12.26上午地点工训楼C栋309 实验名称分支限界法求旅行售货员问题实验目的 通过上机实验，掌握分支限界算法的思想，利用Dijkstra 算法求解最短路径并实现。实验原理使用一个优先队列来存储活结点。优先队列中的每个活结点都存储从根到该活结点的相应路径。算法开始创建一个最小堆，表示活结点优先队列。堆中每个结点的lcost值是优先队列的优先级。接着计算出图中每个顶点的最小费用出边并用Minout记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路,算法结束。如果每个顶点都有出边，则根据计算出的
2、Minout作算法初始化。算法第一个扩展结点是排列树中根结点唯一的儿子结点。在该结点处，已确定的回路中的唯一顶点为顶点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的一条边。对于当前扩展结点的每一个可行儿子结点,计算出其前缀(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类来存储最小堆中
5、顶点的信息。* lcost表示子树费用的下界。 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; /需要进一步搜索的
6、顶点是xs+1,n-1; /*=BBTSP函数为使用优先队列求最小费用。 这里是使用一个优先队列来存储活结点。优先队列中的每个活结点都存储从根到该活结点的相应路径。算法开始创建一个最小堆，表示活结点优先队列。堆中每个结点的lcost值是优先队列的优先级。接着计算出图中每个顶点的最小费用出边并用Minout记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路,算法结束。如果每个顶点都有出边，则根据计算出的Minout作算法初始化。算法第一个扩展结点是排列树中根结点唯一的儿子结点。在该结点处，已确定的回路中的唯一顶点为顶点1.初始时有s=0,x0=1,x1:n-1=(2,3,n),cc=0
7、，且rcost为Minouti的和，算法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 & (a
9、ijMin|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 = i+1; E.s = 0; /根节点到当前节点路径为x0:s E.cc = 0; /当前费用 E.rcost = MinSum;/最小出边费用和 Type bestc = NoEdge; /搜索排列空间树 whi
10、le(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 = 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;
