江世海+图着色问题

江世海+图着色问题 安徽新华学院 [回溯算法] 专业: 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<