下载文档原格式
算法分析与设计实验报告第六次附加实验cout<<endl;}elsefor(int i=1;i<=m;i++){x[t]=i;if(ok(t)) Backtrack(t+1);//回溯，继续寻找下一层x[t]=0;//回到最初状态，使x[1]继续尝试其他填色的可能解}}测试结果当输入图如下时：结果如下：12435只要输入边即可当输入的图如下时：结果如下：附录：完整代码（回溯法）//图的m着色问题回溯法求解#include<iostream>using namespace std;class Color{friend void mColoring(int,int,int **);private:bool ok(int k);void Backtrack(int t);int n, //图的顶点个数m, //可用颜色数**a, //图的邻接矩阵*x; //当前解long sum; //当前已找到的可m着色的方案数};bool Color::ok(int k) //检查颜色可用性{for(int j=1;j<=n;j++)if((a[k][j]==1)&&(x[j]==x[k])) //两个点之间有约束且颜色相同return false;return true;}void Color::Backtrack(int t){if(t>n) //到达叶子节点{sum++; //可行解+1cout<<"着色： ";for(int i=1;i<=n;i++) //输出可行解方案cout<<x[i]<<" ";cout<<endl;}elsefor(int i=1;i<=m;i++){x[t]=i;if(ok(t)) Backtrack(t+1);//回溯，继续寻找下一层x[t]=0;//回到最初状态，使x[1]继续尝试其他填色的可能解 }}void mColoring(int n,int m,int **a){Color X;//初始化XX.n=n;X.m=m;X.a=a;X.sum=0;int *p=new int[n+1];for(int i=0;i<=n;i++)p[i]=0;X.x=p;cout<<"顶点： ";for(int i=1;i<=n;i++) //用于输出结果cout<<i<<" " ;cout<<endl;X.Backtrack(1); //从顶点1开始回溯delete []p;cout<<"解法个数："<<X.sum<<endl;}int main(){int n;int m;cout<<"please input number of node:";cin>>n;cout<<"please input number of color:";cin>>m;int **a=new int*[n+1];for(int i=0;i<=n;i++)a[i]=new int[n+1];for(int i=0;i<=n;i++) //利用抽象图实现图的邻接矩阵for(int j=0;j<=n;j++)a[i][j]=0;int edge;cout<<"please input adjacent edge number:";cin>>edge;int v,w;cout<<"please inout adjacent edge:"<<endl; //只要输入边即可for(int i=0;i<edge;i++){cin>>v>>w; //由于是无向图，所以对应的邻接矩阵对应的边都有，即v->m,m->v都有边a[v][w]=1;a[w][v]=1;}mColoring(n,m,a);system("pause");return 0;}。
图的着色问题一、题目简述(1) 图的m-着色判定问题给定一个无向连通图 G 和 m 种不同的颜色。
用这些颜色为图 G 的各顶点着色，每个顶点着一种颜色，是否有一种着色法使 G 中任意相邻的两个顶点着不同颜色？(2) 图的m-着色优化问题若一个图最少需要 m 种颜色才能使图中任意相邻的两个顶点着不同颜色，则称这个数 m 为该图的色数。
求一个图的最小色数 m 的问题称为m-着色优化问题。
二、算法思想1. m-着色判定问题总体思想：通过回溯的方法，不断为每一个节点着色，每个点的颜色由一个数字代表，初始值为1。
在对前面 step - 1 个节点都合法的着色之后，开始对第 step 个节点进行着色。
如果 n 个点均合法，且颜色数没有达到 m 种，则代表存在一种着色法使 G中任意相邻的两个顶点着不同颜色。
具体步骤：1. 对每个点 step ，有 m 种着色可能性，初始颜色值为1。
2. 检查第 step 个节点颜色的可行性，若与某个已着色的点相连且颜色相同，则不选择这种着色方案，并让颜色值加1，继续检查该点下一种颜色的可行性。
3. 如果第 step 点颜色值小于等于 m ，且未到达最后一个点，则进行对第 step + 1 点的判断。
4. 如果第 step 点颜色值大于 m ，代表该点找不到合适的分配方法。
此时算法进行回溯，首先令第 step 节点的颜色值为0，并对第 step - 1 个点的颜色值+1后重新判断。
5. 如果找到一种颜色使得第 step 个节点能够着色，说明 m 种颜色的方案是可行的。
6. 重复步骤2至5，如果最终 step 为0则代表无解。
2. m-着色优化问题基于问题1，对于一个无向图 G ，从1开始枚举染色数，上限为顶点数，第一个满足条件的颜色数即为所求解。
三、实现过程（附代码）1. m-着色判定问题#include<iostream>using namespace std;int color[100]; // 每个点的颜色int mp[100][100]; // 图的邻接矩阵int n, m, x; // n顶点，m种颜色方案，x条边bool check(int step) {// 判断与step点相邻的点，颜色是否与step点相同，若相同则返回falsefor (int i=1; i<=n; i++) {if (mp[step][i] ==1&&color[i] ==color[step]) {return false;}}return true;}bool Solve(int m) {// 求解是否可以找到一种可行的染色方案int step=1; // step指示当前节点while (step>=1) {color[step] +=1; // 假定颜色值从1开始，若为回溯，选择下一种方案while (color[step] <=m) { // 按照问题条件选择第step点颜色if (check(step)) {break;} else {color[step]++; // 搜索下一个颜色}}if (color[step] <=m&&step==n) { // 如果找完n个点，且染色方法小于等于m种 return true;} else if (color[step] <=m&&step<n) {step++; // 求解下一个顶点} else { // 如果染色数大于m个，回溯color[step] =0; // 回溯，该点找不到合适的分配方法，对上一点进行分析step--;}}// 如果step退到0，则代表无解return false;}int main() {int i, j;bool ans=false;cout<<"输入顶点数n和着色数m"<<endl;cin>>n>>m;cout<<"输入边数"<<endl;cin>>x;cout<<"具体输入每条边"<<endl;for (int p=0; p<x; p++) { // 以无向邻接矩阵存储边cin>>i>>j;mp[i][j] =1;mp[j][i] =1;}if (Solve(m)) {cout<<"有解";} else {cout<<"无解";}return0;}2. m-着色优化问题#include<iostream>using namespace std;int color[100]; // 每个点的颜色int mp[100][100]; // 图的邻接矩阵int n, m, x; // n顶点，m种颜色方案，x条边bool check(int step) {// 判断与step点相邻的点，颜色是否与step点相同，若相同则返回falsefor (int i=1; i<=n; i++) {if (mp[step][i] ==1&&color[i] ==color[step]) {return false;}}return true;}bool Solve(int m) {// 求解是否可以找到一种可行的染色方案int step=1; // step指示当前节点while (step>=1) {color[step] +=1; // 假定颜色值从1开始，若为回溯，选择下一种方案while (color[step] <=m) { // 按照问题条件选择第step点颜色if (check(step)) {break;} else {color[step]++; // 搜索下一个颜色}}if (color[step] <=m&&step==n) { // 如果找完n个点，且染色方法小于等于m种 return true;} else if (color[step] <=m&&step<n) {step++; // 求解下一个顶点} else { // 如果染色数大于m个，回溯color[step] =0; // 回溯，该点找不到合适的分配方法，对上一点进行分析step--;}}// 如果step退到0，则代表无解return false;}int main() {int i, j;bool ans=false;cout<<"输入顶点数n"<<endl;cin>>n;cout<<"输入边数"<<endl;cin>>x;cout<<"具体输入每条边"<<endl;for (int p=0; p<x; p++) { // 以无向图邻接矩阵存储边 cin>>i>>j;mp[i][j] =1;mp[j][i] =1;}for (m=1; m<=n; m++) { // 从小到大枚举着色数mif (Solve(m)) { // 如果有解，输出答案并跳出循环cout<<"最小色数m为 "<<m;break;}}return0;}四、结果及分析问题1测试用例：问题2测试用例：经检验，最少着色数的范围为2-4，意味着使 G 中任意相邻的两个顶点着不同颜色最多需要4种颜色。
《算法设计与分析》课程实验报告实验序号：10实验项目名称：实验十一回溯法（二）一、实验题目1.图的着色问题问题描述：给定无向连通图G和m种不同的颜色。
用这些颜色为图G的各顶点着色，每个顶点着一种颜色。
如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m可着色的。
图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。
2.旅行商问题问题描述：给出一个n个顶点的带权无向图，请寻找一条从顶点1出发，遍历其余顶点一次且仅一次、最后回到顶点1的最小成本的回路——即最短Hamilton回路。
3.拔河比赛问题描述：某公司的野餐会上将举行一次拔河比赛。
他们想把参与者们尽可能分为实力相当的两支队伍。
每个人都必须在其中一只队伍里，两队的人数差距不能超过一人，且两队的队员总体重应该尽量接近。
4.批处理作业调度问题描述：给定n个作业的集合J=(J1,J2, .. Jn)。
每个作业J都有两项任务分别在两台机器上完成。
每个作业必须先由机器1处理，再由机器2处理。
作业i需要机器j的处理时间为tji(i=1,2, ..n; j=1,2)。
对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间，则所有作业在机器2上完成处理的时间和，称为该作业调度的完成时间和。
批处理作业调度问题要求，对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。
二、实验目的（1）通过练习，理解回溯法求解问题的解状态空间树与程序表达的对应关系，熟练掌握排列树、子集树的代码实现。
（2）通过练习，体会减少搜索解空间中节点的方法，体会解的状态空间树的组织及上界函数的选取对搜索的影响。
（3）通过练习，深入理解具体问题中提高回溯算法效率的方法。
（4）（选做题）：在掌握回溯法的基本框架后，重点体会具体问题中解的状态空间搜索时的剪枝问题。
三、实验要求（1）每题都必须实现算法、设计测试数据、记录实验结果，并给出时间复杂度分析。
四、实验过程（算法设计思想、源码）1.图的着色问题(1)算法设计思想用邻接矩阵a[i][j]存储无向图，对于每一个顶点有m种颜色可以涂。
图着⾊问题⼀、图着⾊问题（1）图的m可着⾊判定问题给定⽆向连通图G和m种不同的颜⾊。
⽤这些颜⾊为图G的各顶点着⾊，每个顶点着⼀种颜⾊。
是否有⼀种着⾊法使G中每条边的2个顶点着不同颜⾊。
（2）图的m可着⾊优化问题若⼀个图最少需要m种颜⾊才能使图中每条边连接的2个顶点着不同颜⾊，则称这个数m为该图的⾊数。
⼆、m可着⾊判定问题的解法【算法】（1）通过回溯的⽅法，不断的为每⼀个节点着⾊，在前⾯cur-1个节点都合法的着⾊之后，开始对第cur-1个节点进⾏着⾊，（2）这时候枚举可⽤的m个颜⾊，通过和第cur-1个节点相邻的节点的颜⾊，来判断这个颜⾊是否合法（3）如果找到那么⼀种颜⾊使得第cur-1个节点能够着⾊，那么说明m种颜⾊的⽅案在当前是可⾏的。
（4）cur每次迭代加1，如果cur增加到N并通过了检测，说明m种颜⾊是可满⾜的。
（5）注意，这⾥只是要求判断m种颜⾊是否可满⾜，所以找到任何⼀种⽅案就可以了。
【代码实现】#include<iostream>#include<cstring>using namespace std;const int maxn = 105;int G[maxn][maxn];int color[maxn];bool ans;int n,m,k;void init(){ans = 0;memset(G, 0 , sizeof G);memset(color, 0 , sizeof color);}void dfs(int cur){if(cur > n) {ans = 1;return;}for(int i=1; i<=m; i++){ //对cur结点尝试使⽤每⼀种颜⾊进⾏涂⾊bool flag = 1;//cur之前的结点必被涂⾊for(int j=1; j<cur; j++){if(G[j][cur] == 1 && color[j] == i){flag = 0;//只要有⼀个冲突都不⾏break;}}//如果可以涂上i颜⾊，则考虑下⼀个结点的情况if(flag){color[cur] = i;dfs(cur + 1);}//如果到这⼀步第cur个结点⽆法着⾊，则返回探寻其他⽅案else color[cur] = 0;//回溯 ;}}int main(){while(cin>>n>>k>>m){init();for(int i=1; i<=k; i++){int x,y;cin>>x>>y;G[x][y] = G[y][x] = 1;}dfs(1);cout<<ans<<endl;}return0;}三、m可着⾊拓展【问题】在上述基础上，求出m种颜⾊能够给图G涂⾊的总总⽅案数量【算法】由于这个时候要求总⽅案数量，所以在找到⼀种可⾏⽅案后，总是进⾏回溯再搜索其他的解决⽅案，与上⾯不同，上⾯是只需要找出⼀种⽅案即可，所以如果找到了就不需要再回溯了，所以在这⾥只需要把回溯语句的位置写到dfs语句的后⾯即可。
