算法之回溯法实现.docx

《算法之回溯法实现.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验4回溯法实现一、实验目标：1.熟悉回溯法应用场景及实现的基本方法步骤；2.学会回溯法的实现方法和分析方法： 二、实验内容1.旅行售货员问题：当结点数为4，权重矩阵为0110239429340660，求最优路径及开销。2.0-1背包问题：对于n=5，C=10，vi={6,3,5,4,6}，wi={2,2，6,5,4}，计算xi及最优价值V。分别利用动态规划、回溯法和分支限界法解决此问题，比较并分析这三种算法实现！三、实验过程1.源代码旅行售货员问题（回溯法）：#includeusingnamespacestd;classtrave

2、l//回溯{friendintTSP(int**,int[],int,int);private:voidBacktrack(inti);intn,//顶点数*x,*bestx;int**a,cc,bestc,NoEdge;};voidSwap(inta,intb){inttemp;temp=a;a=b;b=temp;return;}voidtravel::Backtrack(inti){if(i==n){if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&&(cc+a[x[n-1]][x[n]]+a[x[n]]

3、[1])

4、

5、bestc==NoEdge){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++){if(a[x[i-1]][j]!=NoEdge&&a[x[n]][1]!=NoEdge&&(cc+a[x[i-1]][x[j]]

6、

7、bestc==NoEdge)){swap(x[i],x[j]);cc+=a[x[i-1]][x[i]];Backtrack(i+1);cc-=a[x[i-1]][x

8、[i]];swap(x[i],x[j]);}}}}intTSP(int**a,intv[],intn,intNoEdge){travelY;Y.x=newint[n+1];for(inti=1;i<=n;i++)Y.x[i]=i;Y.a=a;Y.n=n;Y.bestc=NoEdge;Y.bestx=v;Y.cc=0;Y.NoEdge=NoEdge;Y.Backtrack(2);delete[]Y.x;returnY.bestc;}intmain(){intconstmax=10000;cout<<"请输入节点数:"<>n;

9、int*v=newint[n];//保存路径intNoEdge=0;int**p=newint*[max];for(inti=0;i>p[i+1][j+1];cout<<"最短路径长度："<

10、l;return0;}运行截图：旅行售货员问题（分支限界法）：#includeusingnamespacestd;#defineMAX_CITY_NUMBER10//城市最大数目#defineMAX_COST1000//两个城市之间费用的最大值intCity_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER];//表示城市间边权重的数组intCity_Size;//表示实际输入的城市数目intBest_Cost;//最小费用intBest_Cost_Path[MAX_CITY_NUMBER];//结点ty

11、pedefstructNode{intlcost;//优先级intcc;//当前费用intrcost;//剩余所有结点的最小出边费用的和ints;//当前结点的深度，也就是它在解数组中的索引位置intx[MAX_CITY_NUMBER];//当前结点对应的路径structNode*pNext;//指向下一个结点}Node;//堆typedefstructMiniHeap{Node*pHead;//堆的头}MiniHeap;//初始化voidInitMiniHeap(MiniHeap*pMiniHeap){pMiniHeap->pHead=newNode

12、;pMiniHeap->pHead->pNext=NULL;}//入堆voidput(Mini