西北工业大学算法设计试验2

1、实验二：回溯法 VS分支定界法一、问题分析回溯法可以处理货郎担问题， 分支定界法也可以处理货郎担问题， 回溯法和分支 定界法哪个算法处理货郎担问题效率更高呢？实现回溯法、分支定界法，以及不同的界值函数（课上讲过的或者自己新设 计的），通过随机产生 10 个不同规模的算例（城市数量分别为 10，20，40，80， 100，120，160，180，200，500，或者其它规模），比较回溯法和分支定界法在 相同界值函数下的执行效率。 另外，分别比较回溯法和分支定界法在不同界值函 数下的执行效率。二、算法基本思想1、回溯法 从初始状态出发，搜索其所能到达的所有“状态” ， 当一条路走到尽头 ，再后退一

2、步或若干步，从另外一种状态出发，继续搜索， 直到所有的路径都搜索过。这种不断前进 、不断回溯寻找解的方法叫回溯法。 回溯法通常将问题解空间组织成“树”结构，采用系统的方法搜索解空间树，从 而得到问题解。搜索策略： 深度优先为主，也可以采用广度优先、函数优先、广度深度结合等。 避免无效搜索策略：约束函数：在扩展结点处剪去不满足约束条件的子树 界限函数：在扩展结点处剪去得不到最优解的子树2、分支限界法 分支界限法类似与回溯法，也是在问题解空间中搜索问题解的一种算法。 分支界限法与回溯法思想对比： 求解目标：回溯法的可以用于求解目标是找出解空间树中满足约束条件的所有 解，而分支限界法的求解目标通常是

3、找出满足约束条件的一个解或最优解。搜索方式的不同： 回溯法主要以深度优先的方式搜索解空间树， 而分支限界法则 主要以广度优先或以最小耗费优先的方式搜索解空间树。 在分支限界法中，每个活结点只有一次机会成为扩展结点。一旦成为扩展结点， 就一次性产生其所有儿子结点。 在这些儿子结点中， 导致不可行解或导致非最优 解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。 这个过程一直持续到找到所需的解或活结点表为空时为止。三、算法设计1、回溯法TSP问题的目的是得到一条路径， 即一个解向量 ( X1,X2.Xn )，为排列树问 题。对

4、所有城市进行编号后，按大小顺序存储于数组 path 中，构造一个交换函 数 swap()；对数组 path 进行遍历，判断当前城市与目标城市是否连通，若连 通，通过 swap 函数对当前节点和目标城市进行交换，即树的节点拓展。若不连 通则恢复， 并进入下一次的循环， 循环到叶子节点时， 判断叶是否与初始节点相 连，并计算代价 cost 是否小于当前最小代价 bestc ，若小于，则更新 bestc ，再 返回上一节点，知道遍历完树中的所有节点。2、分支限界法因为问题是经典的 TSP问题，所以确定问题的解空间树为排列树。 问题解的表示：可以将问题的解表示成一个 n 元式 x1,x2, ,xn 。

5、 使用优先级队列实现最小耗费优先求解。界函数的确定： 首先利用贪心的方法获得一个较优的上界。 对于当前路径下的扩 展的过程中， 每一步需要存储的当前的结点的下界。 其中的第二部分需要计算的 是当前路径的起始结点以及终止结点各自与仍未访问过的结点中的结点只存存 在的最小代价。结点的扩展过程如下： 根据优先级从队列中选取优先级最高的元素， 当结点不是 叶子结点的父节点时， 扩展该结点的所有子节点， 在扩展的过程中需要根据计算 所得的下界与当前求解得到的最优解进行对比， 如果下界大于当前的最优解则对 相应的子节点时进行剪枝处理， 否则扩展该子节点， 将其加入到队列中。 当当前 所访问的结点为叶子结点

6、的父节点时，判断当前费用 +当前结点到叶子结点的费 用+叶子结点到起始结点的费用之和是否优于最优解，如果是则更新最优解，并 将当前的解加入到队列中。 如果不是则继续取队列中的元素进行扩展。 但取出的 元素为叶子节点或者队列中的元素为空的时候， 则搜索结束，输出当前的最优解。四、算法实现1、回溯法核心代码：public void backtrack( int depth) /depth 深度if (depth=size)if (mappathdepth-1pathdepth != -1 &mappathdepthpath1!= -1& cost +mappathdepthpath1bestc)

7、bestp=path.clone();bestc = cost + mappathdepthpath1;/bestc = cost +apathi-1pathi+apathipath1;/ 重复计算了上一边else for (int j =depth;j=size;j+)if (mappathdepthpathj!=-1)swap(path,depth+1,j);cost +=mappathdepthpathdepth+1;/System.out.println(Arrays.toString(x)+:+cost);backtrack(depth+1);cost -=mappathdepthp

8、athdepth+1;swap(path,depth+1,j);2、分支限界法核心代码：public float fzxj ( int m)int n=m. length - 1; / 节点数LinkedList heap =new LinkedList () /minOuti=i 的最小出边费用 float minOut =new float n+1 ;float minSum=0; / 最小出边费用和for ( int i =1; i =n; i +) / 针对每个节点，找到最小出边/ 计算 minOuti 和 minSumfloat min =Float . MAX_VALU;Efor

9、( int j =1; j =n; j +)if ( map i j Float . MAX_VALUE&map i j min) min =map i j ;if ( min=Float . MAX_VALU)Ereturn Float . MAX_VALU;EminOut i =min; minSum+=min ;/ 初始化int x=new int n ;for ( int i =0; i n; i +)x i =i +1;TSPnode enode =new TSPnode( 0, 0, minSum, 0, x);float bestc =Float . MAX_VALU;E/ 搜索

10、排列空间树while ( enode != null &enode . pn- 1)/ 非叶节点x =enode . path ;if ( enode . p=n-2)/ 当前扩展结点是叶节点的父节点/ 再加两条边构成回路/ 所构成回路是否优于当前最优解if ( map x n- 2 x n-1 !=- 1&map x n- 1 1 !=- 1&enode . cost + map x n- 2 xn-1 +map x n-1 1 bestc )/ 找到费用更小的回路bestc =enode . cost +map x n- 2 x n-1 +map x n- 1 1; enode . cos

11、t =bestc ;enode . lcost =bestc ;enode . p+;heap. add( enode ) ;Collections .sort ( heap) ; else / 内部结点/ 产生当前扩展结点的儿子结点for (int i =enode . p+1; i n; i +)if (map x enode . p x i !=- 1)/ 可行儿子结点float cc =enode . cost +map x enode . p xi float rcost =enode . rcost =minOut x enode . p float b=cc +rcost ; /

12、 下界 if ( bbestc )/ 子树可能含有最优解，结点插入最小堆int xx =new int n ;for (int j =0; j n; j +)xx j =xj ;xx enode . p+1 =x i ;xx i =x enode . p+1 ;TSPnode node =newTSPnode( b, cc, rcost , enode . p+1, xx);heap. add( node ) ;Collections . sort ( heap ) ;/ 取下一个扩展结点enode =heap . poll () ;/ 将最优解复制到 v1.nfor ( int i =0;

13、i n; i +)m i +1=x i ;return bestc ;五、算法复杂性理论分析1、回溯法TSP问题是排列树问题，因而该算法的时间复杂度为 O(n!)2、分支限界法TSP问题是排列树问题， 在分支限界法界函数无法剪枝时有最坏情况时间复杂性 为 O（n!） ，但通过界函数剪枝可以使复杂度下降。六、算法代码（单独文件提交）见项目文件七、算法测试（报告只写测试方法与用例设计方法与结果，测试程序单独提交）问题规模回溯法分支限界法53ms852ms1010ms1323ms20272510ms7541ms25-20723ms-八、实验中的问题总结回溯法：优点：可以快速的找到一组解， 并在此基础