浙江工业大学算法实验4--回溯法实现报告

实验4回溯法实现报告一、实验目标：1.熟悉回溯法应用场景及实现的基本方法步骤；2.学会回溯法的实现方法和分析方法：二、实验内容1.旅行售货员问题：当结点数为4，权重矩阵为0110239429340660，求最优路径及开销，分析用回溯法和分支限界法实现。回溯法求解#includeiostreamusingnamespacestd;constintN=4;//图的顶点数templateclassTypeclassTraveling{templateclassTypefriendTypeTSP(Type**a,intn);private:voidBacktrack(inti);intn,//图G的顶点数*x,//当前解*bestx;//当前最优解Type**a,//图G的领接矩阵cc,//当前费用bestc;//当前最优值intNoEdge;//无边标记};templateclassTypevoidTravelingType::Backtrack(inti){if(i==n){if(a[x[n-1]][x[n]]!=0&&a[x[n]][1]!=0&&(cc+a[x[n-1]][x[n]]+a[x[n]][1]bestc||bestc==0)){for(intj=1;j=n;j++)bestx[j]=x[j];bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];}}else{for(intj=i;j=n;j++){//是否可进入x[j]子树?if(a[x[i-1]][x[j]]!=0&&(cc+a[x[i-1]][x[i]]bestc||bestc==0)){//搜索子树swap(x[i],x[j]);cc+=a[x[i-1]][x[i]];//当前费用累加Backtrack(i+1);//排列向右扩展,排列树向下一层扩展cc-=a[x[i-1]][x[i]];swap(x[i],x[j]);}}}}templateclassTypeTypeTSP(Type**a,intn){TravelingTypeY;Y.n=n;Y.x=newint[n+1];Y.bestx=newint[n+1];for(inti=1;i=n;i++){Y.x[i]=i;}Y.a=a;Y.cc=0;Y.bestc=0;Y.NoEdge=0;Y.Backtrack(2);cout最优路径为：endl;for(inti=1;i=n;i++){coutY.bestx[i]--;}coutY.bestx[1]endl;delete[]Y.x;Y.x=0;delete[]Y.bestx;Y.bestx=0;returnY.bestc;}intmain(){cout图的顶点个数n=Nendl;int**a=newint*[N+1];for(inti=0;i=N;i++){a[i]=newint[N+1];}cout图的邻接矩阵为:endl;for(inti=1;i=N;i++){for(intj=1;j=N;j++){cina[i][j];}}cout最短回路的长为：TSP(a,N)endl;for(inti=0;i=N;i++){delete[]a[i];}delete[]a;a=0;system(pause);return0;}分支限界法求解//Minheap2.h#includeiostreamtemplateclassTypeclassGraph;templateclassTclassMinHeap{templateclassTypefriendclassGraph;public:MinHeap(intmaxheapsize=10);~MinHeap(){delete[]heap;}intSize()const{returncurrentsize;}TMax(){if(currentsize)returnheap[1];}MinHeapT&Insert(constT&x);MinHeapT&DeleteMin(T&x);voidInitialize(Tx[],intsize,intArraySize);voidDeactivate();voidoutput(Ta[],intn);private:intcurrentsize,maxsize;T*heap;};templateclassTvoidMinHeapT::output(Ta[],intn){for(inti=1;i=n;i++)couta[i];coutendl;}templateclassTMinHeapT::MinHeap(intmaxheapsize){maxsize=maxheapsize;heap=newT[maxsize+1];currentsize=0;}templateclassTMinHeapT&MinHeapT::Insert(constT&x){if(currentsize==maxsize){return*this;}inti=++currentsize;while(i!=1&&xheap[i/2]){heap[i]=heap[i/2];i/=2;}heap[i]=x;return*this;}templateclassTMinHeapT&MinHeapT::DeleteMin(T&x){if(currentsize==0){coutEmptyheap!endl;return*this;}x=heap[1];Ty=heap[currentsize--];inti=1,ci=2;while(ci=currentsize){if(cicurrentsize&&heap[ci]heap[ci+1]){ci++;}if(y=heap[ci]){break;}heap[i]=heap[ci];i=ci;ci*=2;}heap[i]=y;return*this;}templateclassTvoidMinHeapT::Initialize(Tx[],intsize,intArraySize){delete[]heap;heap=x;currentsize=size;maxsize=ArraySize;for(inti=currentsize/2;i=1;i--){Ty=heap[i];intc=2*i;while(c=currentsize){if(ccurrentsize&&heap[c]heap[c+1])c++;if(y=heap[c])break;heap[c/2]=heap[c];c*=2;}heap[c/2]=y;}}templateclassTvoidMinHeapT::Deactivate(){heap=0;}//优先队列分支限界法求解#includeMinHeap2.h#includeiostreamusingnamespacestd;constintN=4;//图的顶点数templateclassTypeclassTraveling{friendintmain();public:TypeBBTSP(intv[]);private:intn;//图G的顶点数Type**a,//图G的邻接矩阵NoEdge,//图G的无边标识cc,//当前费用bestc;//当前最小费用};templateclassTypeclassMinHeapNode{friendTravelingType;public:operatorType()const{returnlcost;}private:Typelcost,//子树费用的下届cc,//当前费用rcost;//x[s:n-1]中顶点最小出边费用和ints,//根节点到当前节点的路径为x[0:s]*x;//需要进一步搜索的顶点是x[s+1,n-1]};intmain(){cout分支限界法endl;intbestx[N+1];cout图的顶点个数n=Nendl;int**a=newint*[N+1];for(inti=0;i=N;i++){a[i]=newint[N+1];}cout图的邻接矩阵为:endl;for(inti=1;i=N;i++){for(intj=1;j=N;j++){cina[i][j];}}Travelingintt;t.a=a;t.n=N;cout最短回路的长为：t.BBTSP(bestx)endl;cout最短回路为：endl;for(inti=1;i=N;i++){coutbestx[i]--;}coutbestx[1]endl;for(inti=0;i=N;i++){delete[]a[i];}delete[]a;a=0;system(pause);return0;}//解旅行员售货问题的优先队列式分支限界法templateclassTypeTypeTravelingType::BBTSP(intv[]){MinHeapMinHeapNodeTypeH(1000);Type*MinOut=newType[n+1];//计算MinOut[i]=顶点i的最小出边费用TypeMinSum=0;//最小出边费用和for(inti=1;i=n;i++){TypeMin=NoEdge;for(intj=1;j=n;j++){if(a[i][j]!=NoEdge&&(a[i][j]Min||Min==NoEdge)){Min=a[i][j];}}if(Min==NoEdge){returnNoEdge;//无回路}MinOut[i]=Min;MinSum+=Min;}//初始化MinHeapNodeTypeE;E.x=newint[n];for(inti=0;in;i++){E.x[i]=i+1;}E.s=0;//根节点到当前节点路径为x[0:s]E.cc=0;//当前费用E.rcost=MinSum;//最小出边费用和Typebestc=NoEdge;//搜索排列空间树while(E.sn-1)//非叶结点{if(E.s==n-2)//当前扩展节点是叶节点的父节点{//再加2条边构成回路//所构成回路是否优于当前最优解if(a[E.x[n-2]][E.x[n-1]]!=NoEdge&&a[E.x[n-1]][1]!=NoEdge&&(E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][1]bestc||bestc==NoEdge)){//费用更小的回路bestc=E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][1];E.cc=bestc;E.lcost=bestc;E.s++;H.Insert(E);}else{delete[]E.x;//舍弃扩展节点}}else//产生当前扩展节点的儿子节点{for(inti=E.s+1;in;i++){if(a[E.x[E.s]][E.x[i]]!=NoEdge){//可行儿子节点Typecc=E.cc+a[E.x[E.s]][E.x[i]];Typercost=E.rcost-MinOut[E.x[E.s]];Typeb=cc+rcost;//下界if(bbestc||bestc==NoEdge){//子树可能含有最优解//节点插入最小堆MinHeapNodeTypeN;N.x=newint[n];for(intj=0;jn;j++){N.x[j]=E.x[j];}N.x[E.s+1]=E.x[i];N.x[i]=E.x[E.s+1];N.cc=cc;N.s=E.s+1;N.lcost=b;N.rcost=rcost;H.Inse