算法设计与分析课程设计题目：用回溯法分析着色问题学院：理学院专业：信息与计算科学班级：09信科二班姓名：***学号: 200910010207用回溯法分析着色问题目录1 回溯法 (3)1.1回溯法的概述 (3)1.2 回溯法的基本思想 (3)1.3 回溯法的一般步骤 (3)2 图的m着色问题 (3)2.1图的着色问题的来源 (3)2.2通常所说的着色问题 (3)2.3图的着色问题描述 (3)2.4回溯法求解图着色问题 (5)2.5图的m可着色问题的回溯算法描述 (6)2.5.1回溯算法 (6)2.5.2 m着色回溯法递归 (8)2.5.3 m着色回溯法迭代 (9)2.5.4例题利用回溯法给图着色 (11)2.6复杂度分析着色回溯法迭代 (12)§1 回溯法1.1回溯法的概述回溯法是一种系统地搜索问题解的搜索算法。
它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。
算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。
如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。
否则，进入该子树，继续按深度优先的策略进行搜索。
回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。
而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。
这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
1.2回溯法的基本思想回溯法的基本思想是，在确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。
这个开始结点就成为一个活结点，同时也成为当前的扩展结点。
在当前的扩展结点处，搜索向纵深方向移至一个新结点。
这个新结点就成为一个新的活结点，并成为当前扩展结点。
如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。
换句话说，这个结点不再是一个活结点。
此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。
回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
1.3回溯法的一般步骤用回溯法解题的一般步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
§2 图的m着色问题2.1图的着色问题的来源图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。
问题处理：如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。
例如,（a）所示的区域图可抽象为（b）所表示的平面图。
19世纪50年代，英国学者提出了任何地图都可以4中颜色来着色的4色猜想问题。
过了100多年，这个问题才由美国学者在计算机上予以证明，这就是著名的四色定理。
例如，在图（b）中，区域用城市名表示，颜色用数字表示，则图中表示了不同区域的不同着色问题。
2.2通常所说的着色问题是指下述两类问题：a)给定无环图G=(V,E)，用m种颜色为图中的每条边着色，要求每条边着一种颜色，并使相邻两条边有着不同的颜色，这个问题称为图的边着色问题。
b)给定无向图G=(V,E)，用m种颜色为图中的每个顶点着色，要求每个顶点着一种颜色，并使相邻两顶点之间有着不同的颜色，这个问题称为图的顶着色问题。
2.3图的着色问题描述给定无向连通图G和m种不同的颜色。
用这些颜色为图G的各顶点着色，每个顶点着一种颜色。
是否有一种着色法使G中每条边的2个顶点着不同颜色。
这个问题是图的m可着色判定问题。
若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。
求一个图的色数m的问题称为图的m可着色优化问题。
四色问题是m图着色问题的一个特例，根据四色原理，证明平面或球面上的任何地图的所有区域都至多可用四种、颜色来着色，并使任何两个有一段公共边界的相邻区域没有相同的颜色。
这个问题可转换成对一平面图的４－着色判定问题(平面图是一个能画于平面上而边无任何交叉的图)。
将地图的每个区域变成一个结点，若两个区域相邻，则相应的结点用一条边连接起来。
多年来，虽然已证明用5种颜色足以对任一幅地图着色，但是一直找不到一定要求多于4种颜色的地图。
直到1976年这个问题才由爱普尔，黑肯和考西利用电子计算机的帮助得以解决。
他们证明了4种颜色足以对任何地图着色。
2.4回溯法求解图着色问题首先把所有顶点的颜色初始化为0，然后依次为每个顶点着色。
如果其中i个顶点已经着色，并且相邻两个顶点的颜色都不一样，就称当前的着色是有效的局部着色；否则，就称为无效的着色。
如果由根节点到当前节点路径上的着色，对应于一个有效着色，并且路径的长度小于n，那么相应的着色是有效的局部着色。
这时，就从当前节点出发，继续探索它的儿子节点，并把儿子结点标记为当前结点。
在另一方面，如果在相应路径上搜索不到有效的着色，就把当前结点标记为死结点，并把控制转移去搜索对应于另一种颜色的兄弟结点。
如果对所有m个兄弟结点，都搜索不到一种有效的着色，就回溯到它的父亲结点，并把父亲结点标记为死结点，转移去搜索父亲结点的兄弟结点。
这种搜索过程一直进行，直到根结点变为死结点，或者搜索路径长度等于n，并找到了一个有效的着色为止。
由于用m种颜色为无向图G=(V,E)着色，其中，V的顶点个数为n，可以用一个n元组C=(c1,c2,…,cn)来描述图的一种可能着色，其中，ci∈{1, 2, …, m}，(1≤i≤n)表示赋予顶点i的颜色。
例如，5元组(1, 2, 2, 3, 1)表示对具有5个顶点的无向图（a）的一种着色，顶点A着颜色1，顶点B着颜色2，顶点C着颜色2，如此等等。
如果在n元组C中，所有相邻顶点都不会着相同颜色，就称此n元组为可行解，否则为无效解。
容易看出，每个顶点可着颜色有m种选择，n个顶点就有m n种不同的着色方案，问题的解空间是一棵高度为n的完全m叉树，这里树高度的定义为从根节点到叶子节点的路径的长度。
每个分支结点，都有m个儿子结点。
最底层有m n个叶子结点。
例如，表示用3种颜色为3个顶点的图着色的状态空间树。
如图所示，对第i（i>=1）层上的每个顶点，从其父节点到该节点的边上的标号表示顶点i着色的颜色编号。
2.5图的m可着色问题的回溯算法描述2.5.1回溯算法假定图的n个顶点集合用{0,1,2,….,n-1}，颜色集合用{1,2,3,…,m}。
用数组x[n]存放n个顶点的着色，用邻接矩阵c[n][n]来表示图中顶点的邻接关系，若顶点i 与顶点j之间存在关联边，则元素c[i,j]为1否则为0。
所用的数据结构如下：var n,m:integer;//表示顶点数，颜色数x:array[1..n] of integer;//顶点的着色c:array[1..n,1..n] of integer;//表示图的邻接矩阵此外，用ok函数来判断当前顶点的着色是否为有效着色，如果是有效着色，返回1，否则返回0。
Function ok(k:integer):integer;Var I;BeginOk:=1;For I:=0 to k doIf ((c[k,I]=1)and(x[I]=x[k])) ThenBeginOk:=0;Break;End;End;Ok函数假定0~k-1顶点的着色是有效着色，在此基础上判断0~k顶点的着色是否有效。
如果顶点k与顶点I是相邻接的顶点，0≤i≤k-1,而顶点k的颜色与顶点I的颜色相同，就是无效颜色，即返回0，否则返回1。
有了Ok函数之后，图的m着色问题可描述如下：算法:用m种颜色给图着色输入：输入图的顶点数n,颜色数m,图的邻接矩阵c[][]输出：n个顶点的着色x[]procedure m_coloring()var I,k:integer;beginfor I:=0 to n do x[I]:=0; //解向量初始化为0k:=0;while(k>=0) dobeginx[k]:=x[k]+1; //使当前的颜色加1while((x[k]<=m)and(ok(k)=0) do //当前颜色是否有效x[k]:=x[k]+1; //无效,继续搜索下一种颜色 if (x[k]<=m) Then //搜索成功否？If (k=n-1) then break //是最后一个顶点，完成搜索Else k:=k+1; //不是，处理下一个顶点Else //搜索失败，回溯到上一个顶点 BeginX[k]:=0;K:=k-1;End;End;End.2.5.2 m着色回溯法递归//输入n为顶点个数，颜色数m，图的邻接矩阵c[][]//输出n个顶点的着色x[]//递归方法求解#include <iostream>using namespace std;bool c[6][6];int x[6];int m=3;int n=5;bool ok(int k) //判断对顶点k着色以后是否合法着色{int i;for(i = 1; i < k; i++)if((c[k][i]==1 && x[k] == x[i]))return false;return true;}void output(int x[]){cout<<"The feasible result is:"<<endl;for(int i=1;i<=n;i++)cout<<x[i]<<' ';cout<<endl;return;}void backtrack (int t){if (t>n) output(x);elsefor (int i=1;i<=m;i++) {x[t]=i;if (ok(t)) backtrack(t+1);x[t]=0;}}int main(){int i, j;for(i = 1; i < 5; i++)for(j = 1; j < 5; j++)c[i][j] = false;c[1][2] = true;c[1][3] = true;c[2][3] = true;c[2][4] = true;c[2][5] = true;c[3][5] = true;c[4][5] = true;c[2][1] = true;c[3][1] = true;c[3][2] = true;c[4][2] = true;c[5][2] = true;c[5][3] = true;c[5][4] = true;backtrack(1);cout << endl;return 0;}2.5.3 m着色回溯法迭代//输入n为顶点个数，颜色数m，图的邻接矩阵c[][]//输出n个顶点的着色x[]//第一个结点也可以有m种着色方案#include <iostream>using namespace std;bool c[6][6];int x[6];int m=3;int n=5;bool ok(int k) //判断对顶点k着色以后是否合法着色{int i;for(i = 1; i < k; i++)if((c[k][i]==1 && x[k] == x[i]))return false;return true;}void m_coloring(int n, int m){int i, k;for(i = 1; i <= n; i++)x[i] = 0;k =1;while(k >=1){x[k]++;while(x[k] <= m)i f( ok(k)==1) break;e lse x[k]++;if(x[k] <= m && k==n){ for(i=1;i<=n;i++) cout<<x[i]<<" ";cout<<endl;k--;//return; 如果只需要一个解可以将上两句去掉，加入返回语句}e lse if (x[k]<=m &&k<n)k++;e lse{x[k]=0;k--;}}}int main(){int i, j;for(i = 1; i < 5; i++)for(j = 1; j < 5; j++)c[i][j] = false;c[1][2] = true;c[1][3] = true;c[2][3] = true;c[2][4] = true;c[2][5] = true;c[3][5] = true;c[4][5] = true;c[2][1] = true;c[3][1] = true;c[3][2] = true;c[4][2] = true;c[5][2] = true;c[5][3] = true;c[5][4] = true;m_coloring(5, 3);cout << endl;return 0;}2.5.4例：利用回溯法给下图（a）着色。