搜索
实践5分支界限法解决TSP问题Xxxxx1.由繁入简，暴力解决一切！（回溯法）（所有代码纯手打）Figure1路径0、1、2、3四个城市距离如上：这是一个闭环，从哪个城市出发都要回到原点，从哪个城市出发都无所谓。我们假设从城市0最后回到0。因为要经过所有城市，所以路径一定是0xxx0，如：01230；xxx是123的全排列则是所有情况。所有情况总数：(n-1)!=3!=6。1.用回溯算法求全排列1231322132313123212.累计求路径和如：231Sum=path[0][2]+path[2][3]+path[3][1]+path[1][0]3.统计距离，算出最小距离Result=min(sum1+sum2+…+sum3)2.登峰造极，更高更快！（分支界限法）（所有代码纯手打）Figure2扩展结点我们把带扩展结点放入一个优先队列，如结点k，k的优先级别为。到i大代价加上i,k之间的距离。即：W+path[i][k]。还要一个保存当前结点所访问过所有节点的数据结构Set.intV,若当前结点已经在以前的路径中访问过则不再扩展。V．find(i)==V.end()则表明当前结点未访问过。数据结构如下：structnode{intv;//节点编号intp;//优先级，越小优先级越高queueintaq;setintal;//用于保存当前节点已访问过的节点，但不保存节点顺序。booloperator(nodea)const{returna.pp;}}tt;因为不会重复访问统一结点所以当访问到节点数为n是则说明所有节点都已访问过，加上最后节点与开始节点的距离就可以回到出发点了。路径距离我们记为bestcost，若在以后更新节点中当前路径和加上当前节点到出发的距离大于bestcost则该节点不在进行扩展为死节点。3.代码1、回溯：#includeiostreamusingnamespacestd;intb[100];booluse[100];boolused[100][100];intn=3;voidout(){for(inti=0;i=n+1;i++)cout-b[i];coutendl;}intmatr[5][5];intsum;//路径之和intnode;//搜索路径inttt;voiddfs(intk)//k==1[1],2,3,4{for(inti=1;i=n;i++){{if(!use[i]){use[i]=1;b[k]=i;sum+=matr[b[k-1]][i];coutmatr[b[k-1]][i]endl;if(k==n){sum+=matr[i][0];coutmatr[i][0]endl;coutsumendl;sum-=matr[i][0];out();}dfs(k+1);use[i]=0;sum-=matr[b[k-1]][i];}}}}intmain(){freopen(input.txt,r,stdin);for(inti=0;i4;i++)for(intj=0;ji;j++){if(i==j)continue;cinmatr[i][j];matr[j][i]=matr[i][j];}dfs(1);for(i=0;i4;i++){for(intj=0;j4;j++){//if(i==j)continue;coutmatr[i][j];//matr[j][i]=matr[i][j];}coutendl;}coutokendl;}2.分支界限法：#includeiostream#includestring#includequeue#includesetusingnamespacestd;intbcost=100000;structnode{intv;//节点编号intp;//优先级，越小优先级越高queueintaq;setintal;//用于保存当前节点已访问过的节点，但不保存节点顺序。booloperator(nodea)const{returna.pp;}}tt;priority_queuenodeque;intn=6;intmatr[6][6];voidsolve(){tt.p=0;//加入第一个节点tt.v=0;tt.aq.push(0);tt.al.insert(0);que.push(tt);while(!que.empty()){//取出当前节点intP=que.top().p;intV=que.top().v;setintAL=que.top().al;queueintAQ=que.top().aq;setintAL0=que.top().al;queueintAQ0=que.top().aq;que.pop();for(inti=0;in;i++){AL=AL0;AQ=AQ0;if(i!=V&&AL.find(i)==AL.end()){tt.p=P+matr[V][i];if(tt.p+matr[i][0]=bcost)continue;tt.v=i;AL.insert(i);AQ.push(i);tt.al=AL;tt.aq=AQ;if(AL.size()==n){tt.aq.push(0);while(!tt.aq.empty()){cout-tt.aq.front();tt.aq.pop();}coutendl目前最佳方案总路径为：tt.p+matr[i][0]endl;bcost=tt.p+matr[i][0];}elseque.push(tt);}}}}intmain(){freopen(input.txt,r,stdin);for(inti=0;in;i++)for(intj=0;ji;j++){if(i==j)continue;cinmatr[i][j];matr[j][i]=matr[i][j];}solve();return0;}4.实验结果Figure3输入数据输入数据：243521632117333第一个数表示2-1之间的距离为2，第二的数表示3-1之间的距离为4，第三个数表示3-2之间的距离为3……..下面是暴力搜索结果，搜索出所有路径，且最先距离为11。时间复杂度为n!;Figure4暴力搜索下面是分支界限法搜索结果。Figure5分支界限当分支界限法以后所搜的路径不在小于第一次搜索的结果时，第一次结果必然是最小值5.结论分支界限法相比暴力搜索主要优化方面体现在通过设置界限来限制一些扩展结点，即当前结点超过此界限则一定不是最优解，则不再进行扩展当前结点，省去很多时间。各题界限不同，则应具体问题具体分析。