回溯法实验图的m着色问题Word文档下载推荐.docx
- 文档编号:1198783
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:8
- 大小:68.83KB
回溯法实验图的m着色问题Word文档下载推荐.docx
《回溯法实验图的m着色问题Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《回溯法实验图的m着色问题Word文档下载推荐.docx(8页珍藏版)》请在冰点文库上搜索。
2.学会利用其原理求解图的m着色问题
实验原理
实验步骤
关键代码
测试结果
实验分析
通过两个实例图,将m着色问题,进行了演示,可以看到,实际上两个图相差很小,可是结果却整整翻了一倍,这可以说明在越简单的图上,着色问题越容易找到解,解的个数也就越多。
其次在这个问题上我们可以看到它的解空间树并不是一颗子集树,而是真个解空间,每一个结点都会将所有的颜色遍历一遍,从而找到合适的颜色,所以这个回溯问题还是相对于之前的子集树和排列树来说,还是相对简单一点的。
实验心得
着色问题是最早接触的回溯法问题,一开始起始只知道回溯法就是遇到不能满足条件的时候就换一种方法,如果找不到的话就返回到上一个节点换一种方式,图的着色问题和其他的着色问题很相似,但是更简单,因为它的限制条件只有一个,即相邻区域着色不能相同,当转化成抽象图时,即两个有连线的节点之间着色不能相同,而且不需要建立一个子集树来进行回溯,但是这个有一个问题就是继续寻找下一层之后有一条语句是使x[t]=0,这条语句之前一直不能理解是什么意思,后来经过一些数据的手动测试,发现这个案例使用回溯法是使用了递归的方法,因此当完成叶子节点层之后,会回溯到其上一层,又重新更改其到另一种色号,在回溯叶子节点层,当这一层的所有颜色都尝试过之后,又会使再上一层的改变色号,再更改下两层色号,这样做的目的是因为回溯法可以找到所有的可行解,这样就通过回溯找到了所有的可行解。
这个实验的完成是我更加熟悉了回溯法的原理和思想。
实验得分
助教签名
附录:
完整代码(回溯法)
//图的m着色问题回溯法求解
#include<
iostream>
usingnamespacestd;
classColor
{
friendvoidmColoring(int,int,int**);
private:
boolok(intk);
voidBacktrack(intt);
intn,//图的顶点个数
m,//可用颜色数
**a,//图的邻接矩阵
*x;
//当前解
longsum;
//当前已找到的可m着色的方案数
};
boolColor:
:
ok(intk)//检查颜色可用性
for(intj=1;
j<
=n;
j++)
if((a[k][j]==1)&
&
(x[j]==x[k]))//两个点之间有约束且颜色相同
returnfalse;
returntrue;
}
voidColor:
Backtrack(intt)
if(t>
n)//到达叶子节点
{
sum++;
//可行解+1
cout<
<
"
着色:
"
;
for(inti=1;
i<
i++)//输出可行解方案
x[i]<
endl;
}
else
for(inti=1;
=m;
i++)
x[t]=i;
if(ok(t))Backtrack(t+1);
//回溯,继续寻找下一层
x[t]=0;
//回到最初状态,使x[1]继续尝试其他填色的可能解
voidmColoring(intn,intm,int**a)
ColorX;
//初始化X
X.n=n;
X.m=m;
X.a=a;
X.sum=0;
int*p=newint[n+1];
for(inti=0;
p[i]=0;
X.x=p;
cout<
顶点:
i++)//用于输出结果
;
X.Backtrack
(1);
//从顶点1开始回溯
delete[]p;
解法个数:
X.sum<
intmain()
intn;
intm;
pleaseinputnumberofnode:
cin>
>
n;
pleaseinputnumberofcolor:
m;
int**a=newint*[n+1];
a[i]=newint[n+1];
i++)//利用抽象图实现图的邻接矩阵
for(intj=0;
a[i][j]=0;
intedge;
pleaseinputadjacentedgenumber:
edge;
intv,w;
pleaseinoutadjacentedge:
//只要输入边即可
cin>
v>
w;
//由于是无向图,所以对应的邻接矩阵对应的边都有,即v->
m,m->
v都有边
a[v][w]=1;
a[w][v]=1;
mColoring(n,m,a);
system("
pause"
);
return0;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 回溯 实验 着色 问题
![提示](https://static.bingdoc.com/images/bang_tan.gif)