实验五回溯算法的设计与实现

《实验五回溯算法的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、学生实验报告学院:课程名称:专业班级:姓名:学#:软件与通信工程学院算法分析与设计软件144班刘洋0144119学生实验报告学牛姓名刘洋学号0144119同组人实验项目回溯算法的设计与实现□必修□选修□演示性实验□验证性实验□操作性实验□综合性实验实验地点G108实验仪器台号指导教师李刚实验日期及节次4-89A一、实验综述1、实验目的及要求目的：(1)熟悉回溯算法的一般思想；(2)掌握回溯算法的实现调试、改进方法;(3)熟悉回溯算法在解决问题中的应用要求：(1)完整解决3着色问题和8皇后问题；(2)如实报告实验表现。2、实验仪器、设备或软件

2、仪器：Windowsxp/7/8/10软件：vs2013二、实验过程(实验步骤、记录、数据、分析)3着色问题：生成实例：图的in色判定问题：给定无向连通图G和m种颜色。用这些颜色为图G的各顶点着色.问是否存在着色方法，使得G中任2邻接点有不同颜色。实验代码：#ineludeusingnamespacestd;intsum;//判断对顶点k着色以后是否合法着色boolok(intx[],intk,boolc[5][5],intn){inti;for(i=0;i

3、//第k个顶点与某个相邻的顶点有颜色冲突returnfalse;returntrue;//合法//输入n为顶点个数，颜色数m,图的邻接矩阵c[][]//输出n个顶点的着色x[]voidm_coloring(intn,intin,intx[],boolc[5][5]){inti,k;//一开始各个顶点无颜色for(i=0;i=0){x[k]++;while((x[k]<=m)&&(!ok(x,k,c,n)))//得到最高标值的颜色x[k]++;if(x[k]<=m)//

4、第k个顶点的染色是合法的{if(k==n-1)//所有的顶点都已经染完色，程序退出{sum++;printfC第中%d方案:",sum);for(i=0;i

5、;j++)c[i][j]=true;//定义图，也可以设置成数组表示距离矩阵的形式c[0][4]=false;c[2][4]=false;c[4][0]=false;c[4][2]=false;//对5个顶点的图进行4着色mcoloring(5,4,x,c);if(sum~0)cout<<"无解"<

6、行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。实验代码：^include;usingnamespacestd;^defineN8/*N为皇后个数*/intcount二0;intM[N]={0},L[2*N]={0},R[2*N]={0};intA[N][N]={0};/*皇后位置*/voidprint(intA[N][N]);intmytry(inti,intM[N],intL[2*N],intR[2*N],i

7、ntA[N][N]);voidnuiir)(){intn=mytry(0,M,L,R,A);//代表从0行开始试探cout<

8、-l){print(A);cout«endl;count++;}elsemytry(i+l,M,L,R,A);//试探下一行A[i][j]二0;/*去皇后*/M[j]=L[i-j