回溯经典-m 图着色问题（转）
四色问题:
四色问题是m 图着色问题的一个特列，根据四色原理，证明平面或球面上的任何地图的所有区域都至多可用四种、颜色来着色，并使任何两个有一段公共边界的相邻区域没有相同的颜色。这个问题可转换成对一平面图的４－着色判定问题(平面图是一个能画于平面上而边无任何交叉的图) 。将地图的每个区域变成一个结点，若两个区域相邻，则相应的结点用一条边连接起来。多年来，虽然已证明用5种颜色足以对任一幅地图着色，但是一直找不到一定要求多于4种颜色的地图。直到1976年这个问题才由爱普尔(k．i ．apple) ，黑肯(w．haken) 和考西(j．koch) 利用电子计算机的帮助得以解决。他们证明了4种颜色足以对任何地图着色。
在这一节，不是只考虑那些由地图产生出来的图，而是所有的图。讨论在至多使用m 种颜色的情况下，可对一给定的图着色的所有不同方法。
m 图着色问题：
题目大意：
1，已知一个图g 和m>0种颜色，在只准使用这m 种颜色对g 的结点着色的情况下，是否能使图中任何相邻的两个结点都具有不同的颜色呢? 这个问题称为m-着色判定问题。
2，在m-着色最优化问题则是求可对图g 着色的最小整数m 。这个整数称为图g 的色数。这是求图的最少着色问题，求出m 的值。 题目的解法：
第一个问题，m-着色判定问题：
可以通过回溯的方法，不断的为每一个节点着色，在前面n-1个节点都合法的着色之后，开始对第n 个节点进行着色，这时候枚举可用的m 个颜色，通过和第n 个节点相邻的节点的颜色，来判断这个颜色是否合法，如果找到那么一种颜色使得第n 个节点能够着色，那么说明m 种颜色的方案是可行的。返回真即可：
view plaincopy to clipboardprint?
//用于判断当前节点上涂上这个颜色可不可行，与其邻接节点的颜色做判断，这里用邻接表来存储图的信息
bool isok(int step)
{
vector::iterator iter;
for(iter = input[step].begin(); iter != input[step].end(); iter++) {
if(Color[step] == Color[*iter]) return false;
}
return true;
}
//step表示0->n的节点，color_num是指给color_num的颜色的个数可用
//判断如果给color_num的颜色的个数是否可行，如果可行返回true, 否则false
bool DFS(int step, int color_num)
{
if(step >= n) return true;
else
{
int i;
for(i = 1; i
{
Color[step] = i;
if(isok(step))
{
if(DFS(step + 1, color_num))
return true;
}
Color[step] = 0;
}
}
return false;
}
//用于判断当前节点上涂上这个颜色可不可行，与其邻接节点的颜色做判断，这里用邻接表来存储图的信息
bool isok(int step)
{
vector::iterator iter;
for(iter = input[step].begin(); iter != input[step].end(); iter++) {
if(Color[step] == Color[*iter]) return false;
}
return true;
}
//step表示0->n的节点，color_num是指给color_num的颜色的个数可用
//判断如果给color_num的颜色的个数是否可行，如果可行返回true, 否则false
bool DFS(int step, int color_num)
{
if(step >= n) return true;
else
{
int i;
for(i = 1; i
{
Color[step] = i;
if(isok(step))
{
if(DFS(step + 1, color_num))
return true;
}
Color[step] = 0;
}
}
return false;
}
第二个问题：求出最少的着色数m
有了上面的问题的积累，对于这个问题就很简单了，只要从1到n 枚举颜色数，来调用上面的DFS(0, m),如果有一次调用返回true ，那么这时这个颜色就是我们要求的最少的着色数。
view plaincopy to clipboardprint?
for(i = 1; i
{
if(DFS(0, i))
{
cout
break;
}
}
用邻接矩阵吧。只需要4种颜色。n ——顶点总数，m 为着色数4，x[n]表示0或1，即是否用某种颜色，g[][]为邻接矩阵。
int nextcolor(int k,int m,int n,int x[],int g[][4])
{
int j;
while(1)
{
x[k]=(x[k]+1)%(m+1);//查找颜色，若一直加到第m+1种颜色，表示没有可行的颜色
if(x[k]==0) return 0;
else
for(j=0;j
{
if(g[k][j]==1&&x[j]==x[k]) //与其相邻点作比较，看是否颜色相同 return 0;
else return 1;
}
}
}
int mcolor(int m,int n,int k,int x[],int g[][4])
{
while(1)
{
nextcolor(k,m,n,x,g);
if(x[k]==0) return 0;//若没有可行的颜色，则返回0
if(k==n)
{
for(int i=0;i
printf("%d ",x[i]);
break; }
else mcolor(m,n,k+1,x,g);
}
}
从一个省开始，给它涂上任意一种颜色1，遍历它旁边的省份，涂上与已经涂色并于他相邻的省份不同的颜色就行了。
理论上4种颜色就够了. 地图的四色问题嘛!
可能会有多组解。用递归（dfs) 就可以输出所有解了。
地图着色算法C 语言源代码
前面我写了一个地图着色（即四色原理）的C 源代码。
写完以后想了一下，感觉还不完善，因为从实际操作的角度来考虑，四种可用的颜色放在旁边，不同的人可能会有不同的选择顺序，另外，不同的人可能会选择不同的城市作为着色的起点，而当时的程序没有考虑这个问题。于是，把程序修改为下面的样子，还请同行分析并指出代码中的不足之处：
＃i nclude
#define N 21
int allcolor[4];/*可用的颜色*/
int ok(int metro[N][N],int r_color[N],int current)
{/*ok函数和下面的go 函数和原来的一样, 保留用来比较两种算法*/ int j;
for(j=1;j
if(metro[current][j]==1&&r_color[j]==r_color[current]) return 0;
return 1;
}
void go(int metro[N][N],int r_color[N],int sum,int current) {
int i;
if(current
for(i=1;i
{
r_color[current]=i;
if(ok(metro,r_color,current))
{
go(metro,r_color,sum,current+1); return;
}
}
}
void color(int metro[N][N],int r_color[N],int sum,int start) {
int i,j,k;
r_color[start]=allcolor[0];
for(i=start+1;i!=start;i=(i+1)%(sum+1))/*把所有编号看作一个环*/ if(i==0)/*城市号从1开始编号, 故跳过0编号*/
continue;
else
for(j=0;j
{
r_color[i]=allcolor[j];/*选取下一种颜色, 根据allcolor 中颜色顺序不同，结果不同*/
for(k=1;k
if(metro[i][k]==1&&r_color[k]==r_color[i])
break;
if(k>=i)
break;
}
}
void main()
{
int r_color[N]={0};
int t_color[N]={0};
int i;
int start;/*着色的起点*/
int metro[N][N]={{0},
{0,1,1,1,1,1,1}, {0,1,1,1,1}, {0,1,1,1,0,0,1}, {0,1,1,0,1,1}, {0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1},
{0,1,0,1,0,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,1,1,1,1,0,0,1},
{0,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1}, {0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,0,1},
{0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1}};
allcolor[0]=1;allcolor[1]=2;allcolor[2]=3;allcolor[3]=4;/*选色顺序，顺序不同，结果不同*/
start=1;
/* clrscr();*/
printf("\nAll color is:\n");
for(i=0;i
printf("%d ",allcolor[i]);
go(metro,r_color,20,1);
printf("\nFirst method:\n");
for(i=1;i
printf("%3d",r_color[i]);
color(metro,t_color,20,start);
printf("\nSecond method:\n");
printf("\nAnd the start metro is:%d\n",start); for(i=1;i
printf("%3d",t_color[i]);
}
图着色问题
【参考程序１】
const lin:array[1..12,1..12] of 0..1 {区域相邻数组,1表示相邻} =((0,1,1,1,1,1,0,0,0,0,0,0),
(1,0,1,0,0,1,1,1,0,0,0,0),
(1,1,0,1,0,0,0,1,1,0,0,0),
(1,0,1,0,1,0,1,0,1,1,0,0),
(1,0,0,1,0,1,0,0,0,1,1,0),
(1,1,0,0,1,0,1,0,0,0,1,0),
(0,1,0,0,0,1,0,1,0,0,1,1),
(0,1,1,0,0,0,1,0,1,0,0,1),
(0,0,1,1,0,0,0,1,0,1,0,1),
(0,0,0,1,1,0,0,0,1,0,1,1),
(0,0,0,0,1,1,1,0,0,1,0,1),
(0,0,0,0,0,0,1,1,1,1,1,1));
var color:array[1..12] of byte; {color数组放已填的颜色}
total:integer;
function ok(dep,i:byte):boolean; {判断选用色i 是否可用} var k:byte; {条件:相邻的区域颜色不能相同}
begin
for k:=1 to dep do if (lin[dep,k]=1) and (i=color[k]) then begin ok:=false;exit;end; ok:=true;
end;
procedure output; {输出}
var k:byte;
begin
for k:=1 to 12 do write(color[k],' ');writeln;
total:=total+1;
end;
procedure find(dep:byte); {参数dep:当前正在填的层数}
var i:byte;
begin
for i:=1 to 4 do begin {每个区域都可能是1-4种颜色}
if ok(dep,i) then begin
color[dep]:=i;
if dep=12 then output else find(dep+1);
color[dep]:=0; {恢复初始状态, 以便下一次搜索}
end;
end;
end;
begin
total:=0; {总数初始化}
fillchar(color,sizeof(color),0);
find(1);
writeln('total:=',total);
end.
【参考程序２】
const {lin数组:代表区域相邻情况}
lin:array[1..12] of set of 1..12 =
([2,3,4,5,6],[1,3,6,7,8],[1,2,4,8,9],[1,3,5,9,10],[1,4,6,10,11],
[1,2,5,7,11],[12,8,11,6,2],[12,9,7,2,3],[12,8,10,3,4],
[12,9,11,4,5],[12,7,10,5,6],[7,8,9,10,11]);
color:array[1..4] of char=('r','y','b','g');
var a:array[1..12] of byte; {因有12个区域, 故a 数组下标为1-12} total:integer;
function ok(dep,i:integer):boolean; {判断第dep 块区域是否可填第i 种色} var j:integer; { j 为什么设成局部变量?}
begin
ok:=true;
for j:=1 to 12 do
if (j in lin[dep]) and (a[j]=i) then ok:=false;
end;
procedure output; {输出过程}
var j:integer; { j 为什么设成局部变量?}
begin
inc(total); {方案总数加1}
write(total:4); {输出一种方案}
for j:=1 to 12 do write(color[a[j]]:2);writeln;
end;
procedure find(dep:byte);
var i:byte; { i 为什么设成局部变量?}
begin
for i:=1 to 4 do {每一区域均可从4种颜色中选一}
begin
if ok(dep,i) then begin {可填该色}
a[dep]:=i; {第dep 块区域填第i 种颜色}
if (dep=12) then output {填完12个区域}
else find(dep+1); {未填完}
a[dep]:=0; {取消第dep 块区域已填的颜色}
end;
end;
end;
begin {主程序}
fillchar(a,sizeof(a),0); {记得要给变量赋初值!}
total:=0;
find(1);
writeln('End.');
end.
算法描述：
标准的遍历子集树，OK 函数用于“剪枝”操作。
*/
#include
#include
#define N 5//图中节点的个数
#define m 4 //颜色的种类
int a[N+1][N+1]={
0,0,0,0,0,0,
0,1,1,1,1,0,
0,1,1,1,1,1,
0,1,1,1,1,0,
0,1,1,1,1,1,
0,0,1,0,1,1
};//连接矩阵
int x[N+1];//记录着的是哪种颜色
int sum=0;//保存可以着色的方案数
bool OK(int t,int i)
{
for(int j=1;j
{
if(a[t][j])
{
if(x[j]==i)return false;
}
}
return true;
}
void Backtrace(int t)
{
if(t>N)
{
sum++;
printf("第中%d方案：\n",sum);
for(int i=1;i
{
printf("%d ",x[i]);
}
printf("\n");
}
else
{
for(int i=1;i
{
if(OK(t,i))
{
x[t]=i;
Backtrace(t+1);
}
}
x[t]=0;
}
}
int main()
{
memset(x,0,(N+1)*sizeof(int));
Backtrace(1);
if(sum==0)
{
printf("不是%d可着色的!\n",m);
}
return 0;
}
另外说明一下函数memset ()的用法：
原型：extern void *memset(void *buffer, int c, int count);
用法：#include
功能：把buffer 所指内存区域的前count 个字节设置成字符c 。
说明：返回指向buffer 的指针。
用回溯法解决图的m 着色的另一种方法：
#include
using namespace std;
// 判断对顶点k 着色以后是否合法着色
bool ok(int x[], int k, bool c[5][5], int n)
{
int i;
for(i = 0; i
if((c[k][i] && x[k] == x[i])) // 第k 个顶点与某个相邻的顶点有颜色冲突 return false;
return true; // 合法
}
// 输入n 为顶点个数，颜色数m ，图的邻接矩阵c[][]
// 输出n 个顶点的着色x[]
void m_coloring(int n, int m, int x[], bool c[5][5])
{
int i, k;
// 一开始各个顶点无颜色
for(i = 0; i
x[i] = 0;
k = 0; // 从第0个顶点开始着色
while(k >= 0)
{
x[k]++;
while((x[k]
x[k]++;
if(x[k]
{
if(k == n - 1) // 所有的顶点都已经染完色，程序退出
break;
else
k++; // 继续下一个顶点的染色
}
else // 第k 个顶点的染色不合法，回溯
{
x[k] = 0;
k--;
}
}
}
// test
int main()
{
// 初始化
bool c[5][5];
int x[5];
int i, j;
for(i = 0; i
for(j = 0; j
c[i][j] = false;
// 定义图，也可以设置成数组表示距离矩阵的形式 c[0][1] = true;
c[0][2] = true;
c[1][2] = true;
c[1][3] = true;
c[1][4] = true;
c[3][4] = true;
c[2][4] = true;
c[1][0] = true;
c[2][0] = true;
c[2][1] = true;
c[3][1] = true;
c[4][1] = true;
c[4][3] = true;
c[4][2] = true;
// 对5个顶点的图进行3着色
m_coloring(5, 3, x, c);
// 输出颜色
cout
for(i = 0; i
{
cout
}
cout
return 0;
}
2.6.1主函数的设计
设计好算法后，现在不难给出算法的设计框架。在具体编程时，把一些功能放到外部函数中实现，只在主函数中留出接口。下面是主函数的框架, 使用的是MATLAB 的伪代码。
初始化：a ，m ，n 为a 的维数；%图的邻接矩阵、颜色数、顶点个数
k ，best_k，k_max，fl ；%迭代步数、最优解所在步、最大允许迭代数、下界L=n*m^.5
取整，h=zeros(L,3)；%禁忌表的设置
s=ones(1,n)，s_best=s，s_now=s，best ；%形式、最优解、当前解、最终解 V=zeros(1,n+1)，A=f(s_now)-1；%候选集、特赦值、f 为目标函数 开始：当f(s_now)>fl且(k-best_k
k=k+1；%迭代步数增加
生成s_now的候选集V ，其中的元素s 是非禁忌或者特赦f(s)
在V 中选择使目标函数值最小的解s_best
若f(s_best)
s_now=s_best；继续。结束
2.6.2候选集生成函数的设计
初始化：r=1；%候选集矩阵的行下标
循环：i=1:n，j=[1:s_now(i) s_now(i+1):m]
temp=s_now，temp(i)=j；%临时变量，储存当前解
change=[i,s_now(i),j]；%对换的变化方式
若禁忌表中没有一行和change 相同或者是特赦f(temp)
V(r,1:n)=temp，V(r,n+1)=f(temp)；%前n 行储存解最后一行储存目标值 r=r+1；end %增加迭代次数，继续
回溯经典-m 图着色问题（转）
四色问题:
四色问题是m 图着色问题的一个特列，根据四色原理，证明平面或球面上的任何地图的所有区域都至多可用四种、颜色来着色，并使任何两个有一段公共边界的相邻区域没有相同的颜色。这个问题可转换成对一平面图的４－着色判定问题(平面图是一个能画于平面上而边无任何交叉的图) 。将地图的每个区域变成一个结点，若两个区域相邻，则相应的结点用一条边连接起来。多年来，虽然已证明用5种颜色足以对任一幅地图着色，但是一直找不到一定要求多于4种颜色的地图。直到1976年这个问题才由爱普尔(k．i ．apple) ，黑肯(w．haken) 和考西(j．koch) 利用电子计算机的帮助得以解决。他们证明了4种颜色足以对任何地图着色。
在这一节，不是只考虑那些由地图产生出来的图，而是所有的图。讨论在至多使用m 种颜色的情况下，可对一给定的图着色的所有不同方法。
m 图着色问题：
题目大意：
1，已知一个图g 和m>0种颜色，在只准使用这m 种颜色对g 的结点着色的情况下，是否能使图中任何相邻的两个结点都具有不同的颜色呢? 这个问题称为m-着色判定问题。
2，在m-着色最优化问题则是求可对图g 着色的最小整数m 。这个整数称为图g 的色数。这是求图的最少着色问题，求出m 的值。 题目的解法：
第一个问题，m-着色判定问题：
可以通过回溯的方法，不断的为每一个节点着色，在前面n-1个节点都合法的着色之后，开始对第n 个节点进行着色，这时候枚举可用的m 个颜色，通过和第n 个节点相邻的节点的颜色，来判断这个颜色是否合法，如果找到那么一种颜色使得第n 个节点能够着色，那么说明m 种颜色的方案是可行的。返回真即可：
view plaincopy to clipboardprint?
//用于判断当前节点上涂上这个颜色可不可行，与其邻接节点的颜色做判断，这里用邻接表来存储图的信息
bool isok(int step)
{
vector::iterator iter;
for(iter = input[step].begin(); iter != input[step].end(); iter++) {
if(Color[step] == Color[*iter]) return false;
}
return true;
}
//step表示0->n的节点，color_num是指给color_num的颜色的个数可用
//判断如果给color_num的颜色的个数是否可行，如果可行返回true, 否则false
bool DFS(int step, int color_num)
{
if(step >= n) return true;
else
{
int i;
for(i = 1; i
{
Color[step] = i;
if(isok(step))
{
if(DFS(step + 1, color_num))
return true;
}
Color[step] = 0;
}
}
return false;
}
//用于判断当前节点上涂上这个颜色可不可行，与其邻接节点的颜色做判断，这里用邻接表来存储图的信息
bool isok(int step)
{
vector::iterator iter;
for(iter = input[step].begin(); iter != input[step].end(); iter++) {
if(Color[step] == Color[*iter]) return false;
}
return true;
}
//step表示0->n的节点，color_num是指给color_num的颜色的个数可用
//判断如果给color_num的颜色的个数是否可行，如果可行返回true, 否则false
bool DFS(int step, int color_num)
{
if(step >= n) return true;
else
{
int i;
for(i = 1; i
{
Color[step] = i;
if(isok(step))
{
if(DFS(step + 1, color_num))
return true;
}
Color[step] = 0;
}
}
return false;
}
第二个问题：求出最少的着色数m
有了上面的问题的积累，对于这个问题就很简单了，只要从1到n 枚举颜色数，来调用上面的DFS(0, m),如果有一次调用返回true ，那么这时这个颜色就是我们要求的最少的着色数。
view plaincopy to clipboardprint?
for(i = 1; i
{
if(DFS(0, i))
{
cout
break;
}
}
用邻接矩阵吧。只需要4种颜色。n ——顶点总数，m 为着色数4，x[n]表示0或1，即是否用某种颜色，g[][]为邻接矩阵。
int nextcolor(int k,int m,int n,int x[],int g[][4])
{
int j;
while(1)
{
x[k]=(x[k]+1)%(m+1);//查找颜色，若一直加到第m+1种颜色，表示没有可行的颜色
if(x[k]==0) return 0;
else
for(j=0;j
{
if(g[k][j]==1&&x[j]==x[k]) //与其相邻点作比较，看是否颜色相同 return 0;
else return 1;
}
}
}
int mcolor(int m,int n,int k,int x[],int g[][4])
{
while(1)
{
nextcolor(k,m,n,x,g);
if(x[k]==0) return 0;//若没有可行的颜色，则返回0
if(k==n)
{
for(int i=0;i
printf("%d ",x[i]);
break; }
else mcolor(m,n,k+1,x,g);
}
}
从一个省开始，给它涂上任意一种颜色1，遍历它旁边的省份，涂上与已经涂色并于他相邻的省份不同的颜色就行了。
理论上4种颜色就够了. 地图的四色问题嘛!
可能会有多组解。用递归（dfs) 就可以输出所有解了。
地图着色算法C 语言源代码
前面我写了一个地图着色（即四色原理）的C 源代码。
写完以后想了一下，感觉还不完善，因为从实际操作的角度来考虑，四种可用的颜色放在旁边，不同的人可能会有不同的选择顺序，另外，不同的人可能会选择不同的城市作为着色的起点，而当时的程序没有考虑这个问题。于是，把程序修改为下面的样子，还请同行分析并指出代码中的不足之处：
＃i nclude
#define N 21
int allcolor[4];/*可用的颜色*/
int ok(int metro[N][N],int r_color[N],int current)
{/*ok函数和下面的go 函数和原来的一样, 保留用来比较两种算法*/ int j;
for(j=1;j
if(metro[current][j]==1&&r_color[j]==r_color[current]) return 0;
return 1;
}
void go(int metro[N][N],int r_color[N],int sum,int current) {
int i;
if(current
for(i=1;i
{
r_color[current]=i;
if(ok(metro,r_color,current))
{
go(metro,r_color,sum,current+1); return;
}
}
}
void color(int metro[N][N],int r_color[N],int sum,int start) {
int i,j,k;
r_color[start]=allcolor[0];
for(i=start+1;i!=start;i=(i+1)%(sum+1))/*把所有编号看作一个环*/ if(i==0)/*城市号从1开始编号, 故跳过0编号*/
continue;
else
for(j=0;j
{
r_color[i]=allcolor[j];/*选取下一种颜色, 根据allcolor 中颜色顺序不同，结果不同*/
for(k=1;k
if(metro[i][k]==1&&r_color[k]==r_color[i])
break;
if(k>=i)
break;
}
}
void main()
{
int r_color[N]={0};
int t_color[N]={0};
int i;
int start;/*着色的起点*/
int metro[N][N]={{0},
{0,1,1,1,1,1,1}, {0,1,1,1,1}, {0,1,1,1,0,0,1}, {0,1,1,0,1,1}, {0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1},
{0,1,0,1,0,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,1,1,1,1,0,0,1},
{0,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1}, {0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,0,1},
{0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1}};
allcolor[0]=1;allcolor[1]=2;allcolor[2]=3;allcolor[3]=4;/*选色顺序，顺序不同，结果不同*/
start=1;
/* clrscr();*/
printf("\nAll color is:\n");
for(i=0;i
printf("%d ",allcolor[i]);
go(metro,r_color,20,1);
printf("\nFirst method:\n");
for(i=1;i
printf("%3d",r_color[i]);
color(metro,t_color,20,start);
printf("\nSecond method:\n");
printf("\nAnd the start metro is:%d\n",start); for(i=1;i
printf("%3d",t_color[i]);
}
图着色问题
【参考程序１】
const lin:array[1..12,1..12] of 0..1 {区域相邻数组,1表示相邻} =((0,1,1,1,1,1,0,0,0,0,0,0),
(1,0,1,0,0,1,1,1,0,0,0,0),
(1,1,0,1,0,0,0,1,1,0,0,0),
(1,0,1,0,1,0,1,0,1,1,0,0),
(1,0,0,1,0,1,0,0,0,1,1,0),
(1,1,0,0,1,0,1,0,0,0,1,0),
(0,1,0,0,0,1,0,1,0,0,1,1),
(0,1,1,0,0,0,1,0,1,0,0,1),
(0,0,1,1,0,0,0,1,0,1,0,1),
(0,0,0,1,1,0,0,0,1,0,1,1),
(0,0,0,0,1,1,1,0,0,1,0,1),
(0,0,0,0,0,0,1,1,1,1,1,1));
var color:array[1..12] of byte; {color数组放已填的颜色}
total:integer;
function ok(dep,i:byte):boolean; {判断选用色i 是否可用} var k:byte; {条件:相邻的区域颜色不能相同}
begin
for k:=1 to dep do if (lin[dep,k]=1) and (i=color[k]) then begin ok:=false;exit;end; ok:=true;
end;
procedure output; {输出}
var k:byte;
begin
for k:=1 to 12 do write(color[k],' ');writeln;
total:=total+1;
end;
procedure find(dep:byte); {参数dep:当前正在填的层数}
var i:byte;
begin
for i:=1 to 4 do begin {每个区域都可能是1-4种颜色}
if ok(dep,i) then begin
color[dep]:=i;
if dep=12 then output else find(dep+1);
color[dep]:=0; {恢复初始状态, 以便下一次搜索}
end;
end;
end;
begin
total:=0; {总数初始化}
fillchar(color,sizeof(color),0);
find(1);
writeln('total:=',total);
end.
【参考程序２】
const {lin数组:代表区域相邻情况}
lin:array[1..12] of set of 1..12 =
([2,3,4,5,6],[1,3,6,7,8],[1,2,4,8,9],[1,3,5,9,10],[1,4,6,10,11],
[1,2,5,7,11],[12,8,11,6,2],[12,9,7,2,3],[12,8,10,3,4],
[12,9,11,4,5],[12,7,10,5,6],[7,8,9,10,11]);
color:array[1..4] of char=('r','y','b','g');
var a:array[1..12] of byte; {因有12个区域, 故a 数组下标为1-12} total:integer;
function ok(dep,i:integer):boolean; {判断第dep 块区域是否可填第i 种色} var j:integer; { j 为什么设成局部变量?}
begin
ok:=true;
for j:=1 to 12 do
if (j in lin[dep]) and (a[j]=i) then ok:=false;
end;
procedure output; {输出过程}
var j:integer; { j 为什么设成局部变量?}
begin
inc(total); {方案总数加1}
write(total:4); {输出一种方案}
for j:=1 to 12 do write(color[a[j]]:2);writeln;
end;
procedure find(dep:byte);
var i:byte; { i 为什么设成局部变量?}
begin
for i:=1 to 4 do {每一区域均可从4种颜色中选一}
begin
if ok(dep,i) then begin {可填该色}
a[dep]:=i; {第dep 块区域填第i 种颜色}
if (dep=12) then output {填完12个区域}
else find(dep+1); {未填完}
a[dep]:=0; {取消第dep 块区域已填的颜色}
end;
end;
end;
begin {主程序}
fillchar(a,sizeof(a),0); {记得要给变量赋初值!}
total:=0;
find(1);
writeln('End.');
end.
算法描述：
标准的遍历子集树，OK 函数用于“剪枝”操作。
*/
#include
#include
#define N 5//图中节点的个数
#define m 4 //颜色的种类
int a[N+1][N+1]={
0,0,0,0,0,0,
0,1,1,1,1,0,
0,1,1,1,1,1,
0,1,1,1,1,0,
0,1,1,1,1,1,
0,0,1,0,1,1
};//连接矩阵
int x[N+1];//记录着的是哪种颜色
int sum=0;//保存可以着色的方案数
bool OK(int t,int i)
{
for(int j=1;j
{
if(a[t][j])
{
if(x[j]==i)return false;
}
}
return true;
}
void Backtrace(int t)
{
if(t>N)
{
sum++;
printf("第中%d方案：\n",sum);
for(int i=1;i
{
printf("%d ",x[i]);
}
printf("\n");
}
else
{
for(int i=1;i
{
if(OK(t,i))
{
x[t]=i;
Backtrace(t+1);
}
}
x[t]=0;
}
}
int main()
{
memset(x,0,(N+1)*sizeof(int));
Backtrace(1);
if(sum==0)
{
printf("不是%d可着色的!\n",m);
}
return 0;
}
另外说明一下函数memset ()的用法：
原型：extern void *memset(void *buffer, int c, int count);
用法：#include
功能：把buffer 所指内存区域的前count 个字节设置成字符c 。
说明：返回指向buffer 的指针。
用回溯法解决图的m 着色的另一种方法：
#include
using namespace std;
// 判断对顶点k 着色以后是否合法着色
bool ok(int x[], int k, bool c[5][5], int n)
{
int i;
for(i = 0; i
if((c[k][i] && x[k] == x[i])) // 第k 个顶点与某个相邻的顶点有颜色冲突 return false;
return true; // 合法
}
// 输入n 为顶点个数，颜色数m ，图的邻接矩阵c[][]
// 输出n 个顶点的着色x[]
void m_coloring(int n, int m, int x[], bool c[5][5])
{
int i, k;
// 一开始各个顶点无颜色
for(i = 0; i
x[i] = 0;
k = 0; // 从第0个顶点开始着色
while(k >= 0)
{
x[k]++;
while((x[k]
x[k]++;
if(x[k]
{
if(k == n - 1) // 所有的顶点都已经染完色，程序退出
break;
else
k++; // 继续下一个顶点的染色
}
else // 第k 个顶点的染色不合法，回溯
{
x[k] = 0;
k--;
}
}
}
// test
int main()
{
// 初始化
bool c[5][5];
int x[5];
int i, j;
for(i = 0; i
for(j = 0; j
c[i][j] = false;
// 定义图，也可以设置成数组表示距离矩阵的形式 c[0][1] = true;
c[0][2] = true;
c[1][2] = true;
c[1][3] = true;
c[1][4] = true;
c[3][4] = true;
c[2][4] = true;
c[1][0] = true;
c[2][0] = true;
c[2][1] = true;
c[3][1] = true;
c[4][1] = true;
c[4][3] = true;
c[4][2] = true;
// 对5个顶点的图进行3着色
m_coloring(5, 3, x, c);
// 输出颜色
cout
for(i = 0; i
{
cout
}
cout
return 0;
}
2.6.1主函数的设计
设计好算法后，现在不难给出算法的设计框架。在具体编程时，把一些功能放到外部函数中实现，只在主函数中留出接口。下面是主函数的框架, 使用的是MATLAB 的伪代码。
初始化：a ，m ，n 为a 的维数；%图的邻接矩阵、颜色数、顶点个数
k ，best_k，k_max，fl ；%迭代步数、最优解所在步、最大允许迭代数、下界L=n*m^.5
取整，h=zeros(L,3)；%禁忌表的设置
s=ones(1,n)，s_best=s，s_now=s，best ；%形式、最优解、当前解、最终解 V=zeros(1,n+1)，A=f(s_now)-1；%候选集、特赦值、f 为目标函数 开始：当f(s_now)>fl且(k-best_k
k=k+1；%迭代步数增加
生成s_now的候选集V ，其中的元素s 是非禁忌或者特赦f(s)
在V 中选择使目标函数值最小的解s_best
若f(s_best)
s_now=s_best；继续。结束
2.6.2候选集生成函数的设计
初始化：r=1；%候选集矩阵的行下标
循环：i=1:n，j=[1:s_now(i) s_now(i+1):m]
temp=s_now，temp(i)=j；%临时变量，储存当前解
change=[i,s_now(i),j]；%对换的变化方式
若禁忌表中没有一行和change 相同或者是特赦f(temp)
V(r,1:n)=temp，V(r,n+1)=f(temp)；%前n 行储存解最后一行储存目标值 r=r+1；end %增加迭代次数，继续