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

《浙江工业大学算法实验4--回溯法实现报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验4回溯法实现报告一、实验目标：1.熟悉回溯法应用场景及实现的基本方法步骤；2.学会回溯法的实现方法和分析方法： 二、实验内容1.旅行售货员问题：当结点数为4，权重矩阵为40660，求最优路径及开销，分析用回溯法和分支限界法实现。回溯法求解#includeusingnamespacestd;constintN=4;//图的顶点数templateclassTraveling{templatefriendTypeTSP(Type**a,intn);private:voidBacktrack(inti);intn,//图

2、G的顶点数*x,//当前解*bestx;//当前最优解Type**a,//图G的领接矩阵cc,//当前费用bestc;//当前最优值intNoEdge;//无边标记};templatevoidTraveling::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]

3、

4、bestc==0)){for(intj=1;j<=n;j++)bestx[j]=x[j];bestc=cc+a[x[n-1]][x[n]

5、]+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]]

6、

7、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]);}}}}templateTypeTSP(Type**a,intn){Traveling

8、e>Y;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<<"最优路径为："<";}cout<

9、的顶点个数n="<>a[i][j];}}cout<<"最短回路的长为："<

10、ostream>templateclassGraph;templateclassMinHeap{templatefriendclassGraph;public:MinHeap(intmaxheapsize=10);~MinHeap(){delete[]heap;}intSize()const{returncurrentsize;}TMax(){if(currentsize)returnheap[1];}MinHeap&Insert(constT&x);MinHeap&DeleteMin(T&x);voidIn

11、itialize(Tx[],intsize,intArraySize);voidDeactivate();voidoutput(Ta[],intn);private:intcurrentsize,maxsize;T*heap;};templatevoidMinHeap::output(Ta[],intn){for(inti=1;i<=n;i++)cout<MinHeap::Mi