搜索
实验二：回溯法VS分支定界法一、问题分析回溯法可以处理货郎担问题，分支定界法也可以处理货郎担问题，回溯法和分支定界法哪个算法处理货郎担问题效率更高呢？实现回溯法、分支定界法，以及不同的界值函数（课上讲过的或者自己新设计的），通过随机产生10个不同规模的算例（城市数量分别为10，20，40，80，100，120，160，180，200，500，或者其它规模），比较回溯法和分支定界法在相同界值函数下的执行效率。另外，分别比较回溯法和分支定界法在不同界值函数下的执行效率。二、算法基本思想1、回溯法从初始状态出发，搜索其所能到达的所有“状态”，当一条路走到尽头，再后退一步或若干步，从另外一种状态出发，继续搜索，直到所有的路径都搜索过。这种不断前进、不断回溯寻找解的方法叫回溯法。回溯法通常将问题解空间组织成“树”结构，采用系统的方法搜索解空间树，从而得到问题解。搜索策略：深度优先为主，也可以采用广度优先、函数优先、广度深度结合等。避免无效搜索策略：约束函数：在扩展结点处剪去不满足约束条件的子树界限函数：在扩展结点处剪去得不到最优解的子树2、分支限界法分支界限法类似与回溯法，也是在问题解空间中搜索问题解的一种算法。分支界限法与回溯法思想对比：求解目标：回溯法的可以用于求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标通常是找出满足约束条件的一个解或最优解。搜索方式的不同：回溯法主要以深度优先的方式搜索解空间树，而分支限界法则主要以广度优先或以最小耗费优先的方式搜索解空间树。在分支限界法中，每个活结点只有一次机会成为扩展结点。一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。三、算法设计1、回溯法TSP问题的目的是得到一条路径，即一个解向量（X1,X2...Xn），为排列树问题。对所有城市进行编号后，按大小顺序存储于数组path中，构造一个交换函数swap（）；对数组path进行遍历，判断当前城市与目标城市是否连通，若连通，通过swap函数对当前节点和目标城市进行交换，即树的节点拓展。若不连通则恢复，并进入下一次的循环，循环到叶子节点时，判断叶是否与初始节点相连，并计算代价cost是否小于当前最小代价bestc，若小于，则更新bestc，再返回上一节点，知道遍历完树中的所有节点。2、分支限界法因为问题是经典的TSP问题，所以确定问题的解空间树为排列树。问题解的表示：可以将问题的解表示成一个n元式[x1,x2,…,xn]。使用优先级队列实现最小耗费优先求解。界函数的确定：首先利用贪心的方法获得一个较优的上界。对于当前路径下的扩展的过程中，每一步需要存储的当前的结点的下界。其中的第二部分需要计算的是当前路径的起始结点以及终止结点各自与仍未访问过的结点中的结点只存存在的最小代价。结点的扩展过程如下：根据优先级从队列中选取优先级最高的元素，当结点不是叶子结点的父节点时，扩展该结点的所有子节点，在扩展的过程中需要根据计算所得的下界与当前求解得到的最优解进行对比，如果下界大于当前的最优解则对相应的子节点时进行剪枝处理，否则扩展该子节点，将其加入到队列中。当当前所访问的结点为叶子结点的父节点时，判断当前费用+当前结点到叶子结点的费用+叶子结点到起始结点的费用之和是否优于最优解，如果是则更新最优解，并将当前的解加入到队列中。如果不是则继续取队列中的元素进行扩展。但取出的元素为叶子节点或者队列中的元素为空的时候，则搜索结束，输出当前的最优解。四、算法实现1、回溯法核心代码：publicvoidbacktrack(intdepth){//depth深度if(depth==size){if(map[path[depth-1]][path[depth]]!=-1&&map[path[depth]][path[1]]!=-1&&cost+map[path[depth]][path[1]]bestc){bestp=path.clone();bestc=cost+map[path[depth]][path[1]];//bestc=cost+a[path[i-1]][path[i]]+a[path[i]][path[1]];//重复计算了上一边}}else{for(intj=depth;j=size;j++){if(map[path[depth]][path[j]]!=-1){swap(path,depth+1,j);cost+=map[path[depth]][path[depth+1]];//System.out.println(Arrays.toString(x)+:+cost);backtrack(depth+1);cost-=map[path[depth]][path[depth+1]];swap(path,depth+1,j);}}}}2、分支限界法核心代码：publicfloatfzxj(int[]m){intn=m.length-1;//节点数LinkedListTSPnodeheap=newLinkedListTSPnode();//minOut[i]=i的最小出边费用float[]minOut=newfloat[n+1];floatminSum=0;//最小出边费用和for(inti=1;i=n;i++){//针对每个节点，找到最小出边//计算minOut[i]和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_VALUE)returnFloat.MAX_VALUE;minOut[i]=min;minSum+=min;}//初始化int[]x=newint[n];for(inti=0;in;i++)x[i]=i+1;TSPnodeenode=newTSPnode(0,0,minSum,0,x);floatbestc=Float.MAX_VALUE;//搜索排列空间树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]][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);}}else{//内部结点//产生当前扩展结点的儿子结点for(inti=enode.p+1;in;i++){if(map[x[enode.p]][x[i]]!=-1){//可行儿子结点floatcc=enode.cost+map[x[enode.p]][x[i]];floatrcost=enode.rcost=minOut[x[enode.p]];floatb=cc+rcost;//下界if(bbestc){//子树可能含有最优解，结点插入最小堆int[]xx=newint[n];for(intj=0;jn;j++)xx[j]=x[j];xx[enode.p+1]=x[i];xx[i]=x[enode.p+1];TSPnodenode=newTSPnode(b,cc,rcost,enode.p+1,xx);heap.add(node);Collections.sort(heap);}}}}//取下一个扩展结点enode=heap.poll();}//将最优解复制到v[1...n]for(inti=0;in;i++)m[i+1]=x[i];returnbestc;}五、算法复杂性理论分析1、回溯法TSP问题是排列树问题，因而该算法的时间复杂度为O(n!)。2、分支限界法TSP问题是排列树问题，在分支限界法界函数无法剪枝时有最坏情况时间复杂性为O(n!)，但通过界函数剪枝可以使复杂度下降。六、算法代码（单独文件提交）见项目文件七、算法测试（报告只写测试方法与用例设计方法与结果，测试程序单独提交）问题规模回溯法分支限界法53ms852ms1010ms1323ms20272510ms7541ms25--20723ms…----八、实验中的问题总结回溯法：优点：可以快速的找到一组解，并在此基础之上进行调整。当搜索完解空间时便可以得到所有的解。缺点：需要搜索大量的结点，存在一定的盲目性，而且随着结点的个数不断地增加之后，解空间按照阶乘的增长速度递增，因而算法效率较低。分支限界法：优点：分支限界法采用采用价值队列优先的方式进行搜索，具有一定的目的性。同时利用贪心算法得到的一个上界，以及设定当前路径下的下界函数。通过设置界函数进行剪枝，提高算法的效率。缺点：复杂性高，上下界设计困难