实验七 分支限界法

实验七分枝定界法(2小时)一、实验的目的和要求1.掌握旅行推销员问题的分枝定界算法；2.区分分支定界算法和回溯算法，加深对分支定界算法的理解。第二，实验问题：销售人员必须去几个城市销售商品，了解城市之间的距离(或旅行费用)。他会选择一条从车站出发，经过每个城市一次，最后返回车站的路线，以尽量减少总距离(或总旅行费用)。三。实验提示旅行推销员问题的解空间是一排树。有两种方法可以做到这一点。第一种是只使用一个优先级队列，队列中的每个元素都包含到根的路径。另一种是保留部分解空间树和优先级队列，优先级队列中的元素不包含根的路径。以下是第一种方法。因为我们在寻找成本最低的旅行路线，所以我们可以使用成本最低的分支定界法。在实现过程中，使用一个最小优先级队列来记录活动节点，队列中每个节点的类型为MinHeapNode。每个节点包括以下区域：x(从1到n的整数排列，其中x0=1)，s(整数，使得从树排列的根节点到当前节点的路径定义行进路径的前缀x0:s，而其余要被访问的节点是x s 1 : n-1)，cc(行进路径前缀，即在解决方案空间树中从根节点到当前节点的成本)， Lcost(节点子树中任何叶节点的最小成本)，rcost(从顶点xs : n-1开始的所有边的最小成本之和)。 当类型为MinHeapNode(T)的数据转换为类型为T的数据时，结果是lcost值。分支定界算法代码见程序。程序负责人形成一个容量为100的最小堆，用于表示活动节点的最小优先级队列。按lcost值从最小堆中移除活动节点。接下来，计算有向图中每个顶点的最小代价边的最小代价。如果一些顶点没有边，则有向图中没有行进路径，搜索终止。如果所有顶点都有边，则可以开始成本最低的分支和边界搜索。根的子节点b是第一个E节点，在该节点上生成的行进路径前缀只有一个顶点1，因此s=0，x0=1，x1:n-1是剩余的顶点(即顶点2，3，n)。行进路径前缀1的成本是0，即cc=0，并且当rcost=n i=1时为MinOut。在该计划中，bestc给出了目前能找到的最低成本值。起初，因为没有发现旅行路径，因此最佳值设置为NoEdge。旅行商问题的最小费用分枝定界算法模板t adjacencywdigraph : bbtsp(int诉)/旅行商问题的最小费用分枝定界算法/定义一个可容纳多达1000个活动节点的最小堆明爱普H(1000)；T *MinOut=新1；/计算最小值=离开顶点1的最小成本边的成本t MINSum=0；/离开顶点1的最小成本边数对于(int I=1；i=n。i ) t最小值=无边缘；对于(int j=1；j=n。j)如果(j )!=无边缘(aj最小|最小=无边缘)闵=j；如果(最小值=无边缘)返回无边缘；/道路被堵塞了。最小值=最小值；最小值=最小值；/将电子节点初始化为树根中东节点；东x=新国际n；对于(I=0；I n；(I)e . x=I 1；e . s=0；/当地旅游路线是X 1 :e . cc=0；/其成本为0E.rcost=MinSumT bestc=NoEdge。/目前没有找到旅行路线/树的搜索排列而/不是一片叶子如果(E.s=n-2) /叶的父节点/通过添加两条边来完成行程/检查新的旅行路线是否更好如果(艾克斯n-2，艾克斯n-1！=没有埃克斯n-11！=无边缘a埃克斯n-2埃克斯n-1a埃克斯n-11bestc | | bestc=NoEdge)/寻找更好的旅行路线bestc=e . cc ae . xn-2e . xn-1ae . xn-11；E.cc=bestc。E.lcost=bestc。e。s；h。国际收支平衡表；否则删除；否则/生孩子对于(int I=e . s 1；I n；(I)如果(埃克斯埃克斯埃克斯！=无边缘)/可行子节点限制了路径的开销。埃克斯埃克斯埃克斯；埃克斯埃克斯；T b=cc rcost。/下限if (b bestc | bestc=NoEdge) /子树可能有更好的叶子/将根保存到最大堆节点N；N.x=新国际n；对于(int j=0；j . n .j)北j=东j；东1=东1；北x=东x东S1；N.cc=cc。不适用=东1；N.lcost=b。N.rcost=rcost。h。国际收支平衡表(N)；/结束可存活的孩子删除；/本节点处理完毕请尝试 H . DeleteMin(E)；/下一个电子节点接球(出界)突破；/没有未处理的节点如果(bestc=NoEdge)返回NoEdge；/没有旅行路线/复制最佳路径到v1:n对于(I=0；I n；(I)五一1=东十；而(真)/释放最小堆中的所有节点删除；请尝试 H . DeleteMin(E)；接球(出界)突破；返回bestc算法思想：算法思维旅行商问题的解空间可以组织成一棵树，从树的根节点到任何叶节点的路径定义了图的旅行路线。旅行推销员问题是在图g中找到最便宜的旅行路线。路线是一个加权图。图表中每一边的成本(重量)都是正数。一个图的旅行路线是一个包含v中每个顶点的循环。旅行费用是路线上所有费用的总和。在算法开始时，创建一个最小堆来表示活动节点优先级队列。堆中每个节点的子树成本下限的lcost值是优先级队列的优先级。然后，该算法计算图中每个顶点的最小成本边，并用minout记录。如果给定有向图中的顶点没有边，则该图不能有循环，算法结束。如果每个顶点都有一条边，算法将根据计算出的最小值进行初始化。算法的while循环完成了树排列内部节点的扩展。