考场安排－－－图的着色原理之运用
考场安排
姓名：杨小华
【问题描述】
设学校共有n门课，需要进行期末考试，因为不少学生不止选修一门课程，所以不能把
同一个学生选修的两门课程安排在同一场次进行考试，问学期的期末考试最少需多少场次考
完？(提示：如果两门课被同一个同学选上，则表示这两门课的顶点之间存在一条边)。
试设计一算法，当给定一个图时G=（V，E），|V|=n，（Vi，Vj）ЄE，当且仅当有一个同学选了课程i和课程j，试给出一个考试安排方案N1，N2，N3…Nk，Ns∩Nt=Φ（s≠t，1≤s，t≤k）且V=Ni(1≤i≤k)。
【问题分析】
本问题可转换成是对一平面图的顶点着色问题判定，既采用回溯法求解。将所选的每门课程变成一个结点，若一个同学选了m(1≤m≤n)门课程时，则这m门课程所对应的结点互相用一条边连接起来。则相邻边的顶点不能着同一种颜色，既不能安排在同一场次考试。但本题又不同于m-着色问题，而是要求最少场次考完，故本问题是求min-着色问题，既所有的顶点最少可用多少种颜色来着色，则本问题可解。
【数据结构】
图的邻接矩阵test[MAX][MAX]来表示一个图G，其中若（i，j）是G的一条边，则test[i][j]= test[j] [i] =1，否则test[i][j]= test[j] [i] =0，因为本问题只关心一条边是否存在，所以用邻接矩阵。颜色总数用总课程数目表示。生成解则用数组value[MAX]来记录，其中value[i]是结点i的颜色，既课程i可安排在第value[i]场考试，result[MAX]用来记录最优解。程序中N表示课程总数，minSum表示最少的考试场次。
【算法设计与分析】
函数init（）是从testArrange.in中读取数据，并建立对应的邻接矩阵，对于本程序所给出的样例第一组数据的邻接矩阵为图1，平面图为图2。
函数nextValue（k）是生成下一种颜色，进入此过程前value[1] ，value[2]……value[k-1]以分得了颜色且相邻边的结点有不同的颜色。本过程在区域[1，N]中给value[k]确定一个值，如果还剩下一些颜色，它们与结点K邻接的结点分配的颜色不同，那么就将其中最高标值的颜色分配给结点K，如果没有剩下一些颜色，则置value[k]=0。
函数testArrange（）是考试方案的一个递归回溯算法，它计算并找出最少场次解。如果没有可用的颜色了，则回溯。给结点K分配颜色后，此时统计已分配的颜色数目，如果大于minSum的值，则进行剪枝，并回溯。在最初调用testArrange（1）之前，以对图的邻接矩阵置初值并对数组value[MAX]置0值。
函数count（）是对已分配的颜色数目进行统计。
函数print（）是打印考试场次安排方案。
对于每一个内结点，在最坏情况下，函数nextValue（）检查当前扩展结点的每一个儿子结点所相应的颜色的可用性需耗时O（n2），因此，回溯算法总的时间耗费Σni（n2）=n2（nn-1）/（n-1）=O（nn+1）
【程序清单】
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 10
int value[MAX],result[MAX],test[MAX][MAX],N,minSum=0;
void init(FILE *fp)//从文件读记录，并建立与课程相对应的邻接矩阵
{
int a[MAX],t,j,i=0;
char str[50],*p;
memset(test,0,sizeof(test));
fscanf(fp,"%d",&N);
minSum=N;
fseek(fp,2,1);
fgets(str,50,fp);
p=str;
while(1)
{
while(*p!='/n')
a[i++]=(int)strtol(p,&p,10);
if(a[0]==0)
break;
for(j=0;j<i;j++)
for(t=j+1;t<i;t++)
test[a[j]][a[t]]=test[a[t]][a[j]]=1;
i=0;
fgets(str,50,fp);
p=str;
}
}
int count(int *count,int k)//对以生成的解进行统计，以便剪枝
{
int i,j,n=0;
for(i=1;i<=k;i++)
{
for(j=i+1;j<=k;j++)
if(count[j]==count[i])
break;
if(j==k+1)
n++;
}
return(n);
}
int nextValue(int k)//生成下一个解
{
int j,n=0;
while(1)
{
value[k]=(value[k]+1)%(N+1);
if(value[k]==0)
return 0;
for(j=1;j<=N;j++)//对生成的解进行合法性检查
{
if((test[j][k]==1)&&(value[k]==value[j]))
break;
}
if(j==N+1)
{
return 0;
}
}
}
int testArrange(int k )//找一个图的考试方案
{
int j,t;
while(1)
{
nextValue(k);
if(value[k]==0)
return 0;
j=count(value,k);
if(j>minSum)
{ //如果目前生成解的总数以大于以前生成解的总数，则进行剪枝，并回溯
for(t=k+1;t<=N;t++)
value[t]=0;
continue;
}
if(k==N)
{
if(j<minSum)//记录最少的考试场数
{
minSum=j;
for(t=1;t<=N;t++)
result[t]=value[t];//记录最优解
}
}
else
testArrange(k+1);//递归调用
}
}
void print(int min)//打印考试场次安排
{
int i,t,k,j=1;
if(min==1)//只需一个场次
{
printf(" %d#:",j);
for(i=1;i<=N;i++)
printf("%d ",i);
printf("/n");
}
else if(min==N)//一门一个场次
{
for(i=1;i<=N;i++)
printf(" %d#:%d/n",i,i);
}
else//其他情况
{
for(t=1;t<=N;t++)
{
i=result[t];
if(i!=0)
{
printf(" %d#:",j++);
for(k=t;k<=N;k++)
{
if(result[k]==i)
{
printf("%d ",k);
result[k]=0;
}
}
printf("/n");
}
}
}
}
void main()
{
FILE *fp;
int n,i;
if((fp=fopen("testArrange.in","r"))==NULL)
{
printf("File cann't open!");
exit(0);
}
fscanf(fp,"%d",&n);
for(i=0;i<n;i++)
{
init(fp);
memset(value,0,sizeof(value));
testArrange(1);
printf("Turns:%d/n testArrange times:%d/n",i+1,minSum);
print(minSum);
fseek(fp,2,1);
}
fclose(fp);
}
【使用说明】
文件第一行数字表示有几组数据。接下来一行是第一组数据的课程总数N，紧接下来数行是各个学生所选的课程（每个学生所选的课程占一行），以0结束输入，然后是一行空行，以下便是第二组数据，与前描述一样。
样例输入：（以下数据均是文件S7051B.in的内容）
3
5
1 2 5
2 4
1
2
3 5
4 5
3 5
2 3
1 4
2 5
2 4 5
1 3 4
0
4
1 2
2 3
3 4
1 4
0
4
1
2
3
4
0
样例输出：
Turns:1
testArrange times:5
1#:1
2#:2
3#:3
4#:4
5#:5
Turns:2
testArrange times:2
1#:1 3
2#:2 4
Turns:3
testArrange times:1
1#:1 2 3 4