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

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

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

3、索方式的不同： 回溯法主要以深度优先的方式搜索解空间树，而分支限界法则;.主要以广度 先或以最小耗 先的方式搜索解空 。在分支限界法中，每个活 点只有一次机会成 展 点。一旦成 展 点，就一次性 生其所有儿子 点。在 些儿子 点中， 致不可行解或 致非最 解的儿子 点被舍弃，其余儿子 点被加入活 点表中。此后，从活 点表中取下一 点成 当前 展 点，并重复上述 点 展 程。 个 程一直持 到找到所需的解或活 点表 空 止。三、算法 1、回溯法tsp 的目的是得到一条路径，即一个解向量 （ x1,x2.xn ）， 排列 。 所有城市 行 号后，按大小 序存 于数 path 中，构造一个交 函数

4、swap（）； 数 path 行遍 ，判断当前城市与目 城市是否 通，若 通，通 swap 函数 当前 点和目 城市 行交 ，即 的 点拓展。若不 通 恢复，并 入下一次的循 ， 循 到叶子 点 ， 判断叶是否与初始 点相 ，并 算代价 cost 是否小于当前最小代价 bestc ，若小于， 更新 bestc ，再返回上一 点，知道遍 完 中的所有 点。2、分支限界法因 是 典的tsp ，所以确定 的解空 排列 。 解的表示：可以将 的解表示成一个n 元式 x1,x2, ,xn 。使用 先 列 最小耗 先求解。界函数的确定： 首先利用 心的方法 得一个 的上界。 于当前路径下的 展的 程中，每

5、一步需要存 的当前的 点的下界。 其中的第二部分需要 算的是当前路径的起始 点以及 止 点各自与仍未 的 点中的 点只存存在的最小代价。 点的 展 程如下： 根据 先 从 列中 取 先 最高的元素， 当 点不是叶子 点的父 点 ， 展 点的所有子 点， 在 展的 程中需要根据 算所得的下界与当前求解得到的最 解 行 比， 如果下界大于当前的最 解 相 的子 点 行剪枝 理， 否 展 子 点， 将其加入到 列中。 当当前所 的 点 叶子 点的父 点 ，判断当前 用 +当前 点到叶子 点的 ;.用 +叶子结点到起始结点的费用之和是否优于最优解，如果是则更新最优解，并将当前的解加入到队列中。 如果不

6、是则继续取队列中的元素进行扩展。 但取出的元素为叶子节点或者队列中的元素为空的时候， 则搜索结束，输出当前的最优解。四、算法实现1、回溯法核心代码：publicvoid backtrack(intdepth)/depth深度if (depth=size)if (mappathdepth-1pathdepth != -1 &mappathdepthpath1!= -1& cost +mappathdepthpath1bestc)bestp=path.clone();bestc = cost + mappathdepthpath1;/bestc = cost +apathi-1pathi+apat

7、hipath1;/ 重复计算了上一边 else for ( intj =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 -=mappathdepthpathdepth+1;swap(path,depth+1,j);.2、分支限界法核心代码：publicfloatfzxj( int m)intn=m. length-

8、1; / 节点数linkedlist heap=new linkedlist() ;/minouti=i的最小出边费用floatminout =new float n+1 ;floatminsum=0; / 最小出边费用和for ( inti =1; i =n; i +) / 针对每个节点，找到最小出边/ 计算 minouti和 minsumfloatmin =float. max_value;for ( intj =1; j =n; j +)if ( map i j float . max_value&map i j min)min =map i j ;if ( min=float. max

9、_value)returnfloat . max_value;minout i =min ;minsum+=min ;/ 初始化int x=new int n ;for ( inti =0; i n; i +)x i =i +1;tspnode enode=new tspnode( 0, 0, minsum, 0, x) ; float bestc =float . max_value;/ 搜索排列空间树while ( enode != null&enode . pn- 1)/ 非叶节点 x=enode . path ;if ( enode . p=n- 2)/ 当前扩展结点是叶节点的父节点/

10、 再加两条边构成回路/ 所构成回路是否优于当前最优解if ( map x n- 2 x n- 1 !=- 1&map x n- 1 1 !=- 1&enode . cost + map x n- 2 x n- 1 +map x n- 1 1 bestc )/ 找到费用更小的回路bestc =enode . cost +map x n- 2 x n- 1 +map x n- 1 1 ; enode . cost =bestc ;.enode . lcost=bestc ;enode . p+;heap . add( enode ) ;collections. sort ( heap ) ; el

11、se / 内部结点/ 产生当前扩展结点的儿子结点for ( inti =enode . p+1; i n; i +)if ( map x enode . px i !=- 1)/ 可行儿子结点floatcc =enode . cost+map x enode . p x i ;floatrcost =enode . rcost =minout x enode . p;floatb=cc +rcost ; /下界if ( bbestc )/ 子树可能含有最优解，结点插入最小堆intxx =new int n ;for ( intj =0; j n; j +)xx j =x j ;xx enode

12、 . 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 ( inti =0; i n; i +)m i +1 =x i ;returnbestc ;五、算法复杂性理论分析1、回溯法tsp问题是排列树问题，因而该算法的时间复杂度为o(n!) 。;.2、分支限界法tsp 是排列 ， 在分支限界法界函数无法剪枝 有最坏情况 复 性为 o(n!) ，但通 界函数剪枝可以使复 度下降。六、算法代 （ 独文件提交） 目文件七、算法 （ 告只写 方法与用例 方法与 果， 程序 独提交） 模回溯法分支限界法53ms852ms1010ms1323ms20272510ms7541ms25-20723ms-八、 中的 回溯法： 点：可以快速的找到一 解， 并在