江世海+图着色问
安徽新华学院
[回溯算法]
专业: 08计算机科学与技术<2>班
学生姓名: 江世海,刘攀攀,邓山东,王中列,方峰,陈诚
指导教师: 请输入指导教师
完成时间: 2012年11月26日
1算法描述
回溯算法素有“通用解题法”之称。使用它可以系统的搜索一个问题的所有解或者一个解。它是一种既带有系统性又带有跳跃性的搜索算法。 系统性——深度优先搜索包含解空间中所有的树。
跳跃性——剪枝。
回溯算法的基本思想是:数的深度优先搜索+限界(剪枝)。因此在具体解决某一问题时,需要给出解空间的树形表示和定义剪枝操作的算法。 回溯算法形成式及终止条件
算法形式:递归形式和非递归形式
算法的终止条件:当求所有解时,回溯到根节点且根的所有子树都已被搜索遍才结束。
当求一个解时。只要搜索至一个问题解即终止。
2.实例描述及分析
给定无向连通图G和m种不同的颜色。用这些颜色为图G的各个定点这着色,每个顶点着一种颜色。是否有一种颜色使G中的每条边的2个顶点着不同的颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同的颜色,则称这个数m为该图的色数。求有一个图的色数m的问题称为图的m可着色优化问题。
四色猜想:在一个平面或球面上的任何地图能够只用4种颜色来着色,是相邻的国家在地图上着不同颜色。这里假设每个国家在地图上是单连通域,还假设2个国家相邻是指这个国家有一段不为0的公共边界,而不仅有一个公共点。这样的图很容易用平面图表示。地图上的每一个地区相应于平面图中的一个顶点。2个区域在地图上相邻,它们在平面图中相应的2个顶点治安警又有一条边相连。图5-6是一个有五个区域的地图及相应的平面图。这个地图需要4种颜色来着色。
1
5 1
4 2 3 2
22 1 22 3 1 5 4
图5-6
给定图G=(V,E)和m种颜色,如果这个图不是m可着色,给出否定回答;如果这个图是m可着色的,找出所有不同的着色法。用图的邻接矩阵a表示无限联通那个图G=(V,E)。若(i,j)属于G=(V,E)的边集E,则a[i][j]=1,否则a[i][j]=0。整数1,2,.......,m用来表示m种不同的颜色。顶点i所着的颜色用x[i]表示。数组x[1:n]是问题的姐向量。问题的解空间可表示为一颗高度为n+1的完全m叉树。解空间树的第i(1<= i <=n)层中的每个结点都是m个儿子,每个儿子相应于x[i]的m个可能的着色之一。第n+1层结点均为叶结点。图5-7是n=3和m=3时问题的解空间树。
X[2]= 1 2 3
X[2]= 1
2 3 X[3]1 3 2 =
图5-7 n=3和m=3时问题的解空间树
在下面的解图的m可着色问题的回溯算法中,Backtrack(i)搜索空间中第i层子树。类Color 的数据成员
解空间中结点信息,以减少传给Backtrack的参数。Sum记录当前已找到的可m着色
数。
在算法Backtrack中,当i>n 时,算法搜索至叶结点,得到新的m着色方案,当前找到的可m着色方案数sum增1.
当i<=n时,当前扩展结点Z是解空间中的内部节点。该结点有x[i]=1,2,....,m共m个儿子结点。对当前扩展结点Z的每个儿子结点,有#函数#Ok检查其可行性,并以深度优先的方案递归的对可行子树搜索,或剪去不可行子树。
3.算法实现(附实现的完整代码、运行结果界面)
#include
//using namespace std; class Color
{
friend int 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++;
for(int i=1;i<=n;i++)
{
cout<>b;
cout<>c;
a=new int *[b];
for(i=1;i<=b;i++)
a[i]=new int [b];
cout<<"请依次输入邻接矩阵的数据(相邻结点之间有边则相应的数组元素
为1,否为0):"<>a[j][i];
}
cout<总结(关于课程和作业,结合小组实际谈谈收获和建议。至少200字)
通过这次的算法
的作业,我们学到了许多的以前没有知识。首先在选题的时候,我们经过商量最终确定了做回溯的算法。因为以前在学《数据结构》的时候,老师对于树那章的介绍给我留下了很大的兴趣。这次上算法分析课又再次有机会碰到这个问题。如果现在有时间的话,我还是很愿意也值得花时间把这门课程学习好。
在确定了题目以后,我们就开始探讨m着色问题的算法思想。原来这个算法里也用到了递归的搜索解空间树。所谓搜索的解空间树,其实就是按照所有可能的解情况找出所有符合条件的解。但是在看代码的时候大家没有仔细的研究以至于在后来的编码时候带来了很大的障碍。书中已经给出了绝大部分的代码实现,我们把它编程实现了,当然遇到了许多的困难。
首先,第一个错误就是二位数组的传递过程中遇到了障碍。在类里已经存在一个只想二维数组的指针,即指针的指针。然后再用函数mColoring(int n,int m,int
**a)调用主函数里的现成的数组。可是这样的话,由于现成的数组无法直接转换就会产生转换的错误。这一直耽误了我们很长的时间来调程序。后来经过查资料和探讨,最终通过创建动态的二位数组来解决转换错误的问题,因为生成的数组就是指针的指针。同时还可以动态的输入不同的数据来判断。上面的图片结果就是在节点n为5,颜色数m为4的情况下生成的最终全部解。这个问题的解决极大地鼓舞了我们的士气。
其次,就是解决地址越界的错误。正如上面所说的,在研究代码时没有仔细看清楚,最后才产生这样的问题。:Backtrack(int t)和:Ok(int k) 函数其实都是从数组下标i为1的情况下开始检索的。因此,我们在输入由平面图转换而成的二维数组时也应该从第2行开始输入,即数组的下标i=1时输入数据。最终这个问题也被成功的解决,得到了正确的结果。
通过这次的经历,我们意识到,做任何事情都必须求真务实的做,而不是打酱油~
5.小组成员名单
江世海,
刘攀攀,
王中列,
陈诚,
邓山东,
方峰