实验二用回溯法求解图的m着色问题
一、实验目的
1
2、使用回溯法编程求解图的m着色问题。
二、实验原理
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任何一个结点时，总是先判断该结点是否肯定不包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树搜索。否则，进入该子树，继续按深度优先的策略进行搜索。
回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可结束。
回溯法从开始结点(根结点)出发，以深度优先搜索的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时，应往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。
三、问题描述
给定一个无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。若一个图最少需要m种颜色才能使图中任何一条边连接的2个顶点着有不同的颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。设计一个算法，找出用m种颜色对一个图进行着色的不同方案。
四、算法设计与分析
用邻接矩阵a来表示一个无向连通图G=(V,E)。用整数1,2,…,m来表示m 种不同的颜色。x[i]表示顶点i所着的颜色来，则问题的解向量可以表示为n元组x[1:n]。问题的解空间可表示一棵高度为n+1的完全m叉树。解空间树的第i层中每一结点都有m个儿子，每个儿子相应于x[i]的m个可能的着色之一，第n+1层结点均为叶结点。
在回溯算法Backtrack中，当i>n时，表示算法已搜索至一个叶结点，得到一个新的m着色方案，因此当前已找到的可m着色方案数sum增1。当i≤n时，当前扩展结点Z是解空间树中的一个内部结点。该结点有x[i]=1,2,…,m。对当前扩展结点Z的每一个儿子结点,由函数Ok检查其可行性，并以深度优先的方式递归地对可行子树进行搜索，或剪去不可行子树。
五、实验结果
源程序：
#include
using namespace std;
int color[100],sum;
bool ok(int k,int c[100][100])
{
for(int i=1;iif(c[k][i]==1&&color[i]==color[k])
return false;
return true;
}
void backtrack(int k,int n,int m,int c[100][100]) {
if(k>n){
for(int i=1;i<=n;i++)
cout<cout<sum++;
}
else
for(int i=1;i<=m;i++){
color[k]=i;
if(ok(k,c)) backtrack(k+1,n,m,c);
color[k]=0;
}
}
int main()
{
int i,j,n,m;
int c[100][100];
cout<<"输入顶点数n和着色数m:\n";
cin>>n;
cin>>m;
cout<<"输入无向图的邻接矩阵:\n";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cin>>c[i][j];
cout<<"着色所有可能的解:\n";
backtrack(1,n,m,c);
cout<<"着色可能解的总数为:"<system("pause");
return 0;
}
Welcome To Download !!!
欢迎您的下载，资料仅供参考！
