算法设计与分析 课件 第六章 回溯法6.3.4 路线选择问题.ppt

计算机算法设计与分析第6章回溯法路线选择问题在一个矿场有n个采矿区，矿场每天需要将各个矿区采的矿石运回处理。矿车从矿石处理车间出发，依次经过每个采矿区一次将其采的矿石装车，然后运回到矿石处理车间。矿场各个采矿区之间的距离已知。如何进行路线选择，使得矿石回收的运输路线总长度最短。请用回溯算法求解矿石回收运输路线选择问题。路线选择问题路线选择问题是一个典型的TSP问题图。设矿场各个采矿区的分布如图所示。图中结点A为矿石处理车间，结点B、C、D、E为四个采矿区，图中顶点之间边上权值表示两个点之间的距离。排列树定义v[1]~v[n]为问题的解向量，表示有哪些信誉好的足球投注网站过程中每一次选择经过的顶点。将顶点A~E映射为数字1~5，v[i]=j表示第i次选择经过的顶点为j。第二步：确定有哪些信誉好的足球投注网站结构---排列树第一步：定义解向量第三步：确定剪枝函数v[1:n]有两重含义：①v[1:i-1]代表前i-1步按顺序经过的顶点②v[i:n]代表还未经过的顶点在第i次选择经过顶点时，只能在未经过顶点序列v[i]~v[n]中进行选择。算法需要判断当前路径长度是否优于已经找到的最优回路长度作为剪枝函数，判断当路径长度小于前面已知最优值时，则继续下一步探索，算法进入排列树下一层有哪些信誉好的足球投注网站，否则被剪枝处理。符号定义edge[n][n]：表示TSP问题图的邻接矩阵。v[n]：表示顶点序列，初值为{1,2,3,4,5}，将前面的图中的顶点A,B,C,D,E映射为数字编号1,2,3,4,5。bestv[n]：存储最优路径顶点序列。bestc：表示最优路径长度，初值为INF。cc：表述当前路程长度，初值为0。路线选择问题递归回溯伪码Backtrack(i){if(i==n){if(当前路径长度+点n-1到n和点n到1的边长当前最优路径长度)){ for(j?1;j=n;j++)bestv[j]?v[j]; bestc?cc+edge[v[i-1]][v[i]]+edge[v[i]][1];}}else{for(j?i;j=n;jif(当前路径+点i-1到j边长bestc){//有哪些信誉好的足球投注网站子树 swap(v[i],v[j]); cc?cc+edge[v[i-1]][v[i]]; Backtrack(i+1); cc?cc-edge[v[i-1]][v[i]]; swap(v[i],v[j]);}}//else}//函数Backtrack()从点i-1扩展点i时，若i为叶子结点n，且edge[n-1][n]+edge[n][1]+ccbestc则记录最优路径，并将edge[n-1][n]+edge[n][1]+cc记录为新的最优路径值bestc第i步从未经过的顶点i~n中选择一个j且i-1到j边长+当前路径长度bestc按排列树框架处理递归过程时间复杂度分析回溯算法在最坏情况下需要访问整个解空间排列树全部结点才能得到问题的最优解，更新当前最优解O((n-1)!)次，每次更新bestc需计算时间O(n)，从而整个算法的计算时间复杂度为O(n!)。从顶点A出发，经其他每个顶点再回到出发点A，问题的解是找到一个顶点序列的排列，所以有哪些信誉好的足球投注网站结构为排序树。第1步，从顶点A出发，第二步有4中选择，可选择一个经过顶点（比如顶点B）。第3步有3种选择，可选择一个经过顶点（比如顶点C）。第4步有2种选择，继续选择一个经过顶点（比如顶点D），第5步只能选择叶子结点E，最后由叶子结点E回到出发顶点A。由此产生路径选择问题的一个可行解ABCDEA，路径长度为61。*{//进行一系列判断，注意的是进入此步骤的层数应是叶子结点的父结点*从顶点A出发，经其他每个顶点再回到出发点A，问题的解是找到一个顶点序列的排列，所以有哪些信誉好的足球投注网站结构为排序树。第1步，从顶点A出发，第二步有4中选择，可选择一个经过顶点（比如顶点B）。第3步有3种选择，可选择一个经过顶点（比如顶点C）。第4步有2种选择，继续选择一个经过顶点（比如顶点D），第5步只能选择叶子结点E，最后由叶子结点E回到出发顶点A。由此产生路径选择问题的一个可行解ABCDEA，路径长度为61。*{//进行一系列判断，注意的是进入此步骤的层数应是叶子结点的父结点*