算法设计与分析书中程序(第08章)

《算法设计与分析书中程序(第08章)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、【程序8-1】递归回溯法VoidRBacktrack(intk){//应以RBacktrack(0)调用本函数for(每个x[k],使得x[k]ÎT(x[0],L,x[k-1])&&(Bk(x[0],L,x[k])){if((x[0],x[1],L,x[k])是一个可行解)//判定是否为可行解输出(x[0],x[1],L,x[k]);//输出可行解RBacktrack(k+1);//深度优先进入下一层}}}【程序8-2】迭代回溯法VoidIBacktrack(intn){intk=0;while(k>=0){if(还剩下尚未检测的x[k]

2、，使得x[k]ÎT(x[0],L,x[k-1])&&Bk(x[0],L,x[k]){if((x[0],x[1],L,x[k])是一个可行解)//考虑x[k]的下一个可取值输出(x[0],x[1],L,x[k]);k++;//考虑下一层分量}elsek--;//回溯到上一层}}【程序8-3】蒙特卡罗算法intEstimate(SType*x){intk=0,m=1,r=1;do{SetTypeS={x[k]

3、x[k]ÎT(x[1],L,x[k-1])&&Bk(x[1],L,x[k]==true)}；if(!Size(S))returnm;r

4、=r*Size(S);m=m+r;x[k]=Choose(S);k++;}while(1);}【程序8-4】n-皇后问题的回溯算法boolPlace(intk,inti,int*x){//判定两个皇后是否在同一列或在同一斜线上for(intj=0;j

5、

6、(abs(x[j]-i)==abs(j-k)))returnfalse;·181·returntrue;}voidNQueens(intk,intn,int*x){for(inti=0;i

7、n-1if(Place(k,i,x)){//约束函数x[k]=i;if(k==n-1){for(i=0;i

8、or(intj=0;j<=k;j++)cout<=m)&&(s+w[k+1]<=m)){x[k]=0;SumOfSub(s,k+1,r-w[k],x,m,w);//搜索右子树}}voidSumOfSub(int*x,intn,floatm,float*w){floatr=0;for(inti=0;i

9、;//计算·181·if(r>=m&&w[0]<=m)SumOfSub(0,0,r,x,m,w);}【程序8-6】图的m-着色算法templatevoidMGraph::NextValue(intk,intm,int*x){//本函数在[1,m]中为x[k]确定一个值最小的，且不与其邻接点冲突的颜色//x[k]=0表示没有可用颜色，颜色从1开始编号do{x[k]=(x[k]+1)%(m+1);//尝试下一种颜色if(!x[k])return;//没有可用颜色for(intj=0;j

10、&x[k]==x[j])//若(i,j)是图的边，且相邻结点k和j颜色相同break;//发生冲突，选下一种颜色if(j==k)return;//成功选择一种颜色返回}while(1);}templatevoidMGraph::mColoring(intk,intm,int*x){do{NextValue(k,m,x);//为x[k]分配颜色if(!x[k])break;//x[k]=0表示当前没有适当的颜色if(k==n-1){//得到图G的一种m-着色方案for(inti=0;i

11、<<'';cout<voidMGr