考场安排---图的着色原理之运用

考场安排

姓名:杨小华 

【问题描述】

设学校共有n门课,需要进行期末考试,因为不少学生不止选修一门课程,所以不能把

同一个学生选修的两门课程安排在同一场次进行考试,问学期的期末考试最少需多少场次考

完?(提示:如果两门课被同一个同学选上,则表示这两门课的顶点之间存在一条边)。

试设计一算法,当给定一个图时G=(V,E),|V|=n,(Vi,Vj)ЄE,当且仅当有一个同学选了课程i和课程j,试给出一个考试安排方案N1,N2,N3…Nk,NsNt=Φ(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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT派

干货 | PyTorch相比TensorFlow,存在哪些自身优势?

1、 PyTorch 课替代NumPy 使用:PyTorch 本身主要构件是张量——和 NumPy 看起来差不多。使得 PyTorch 可支持大量相同的 API...

1.9K40
来自专栏潇涧技术专栏

Python Algorithms - C7 Greedy

Python算法设计篇(7) Chapter 7: Greed is good? Prove it!

14020
来自专栏老马说编程

(34) 随机 / 计算机程序的思维逻辑

随机 本节,我们来讨论随机,随机是计算机程序中一个非常常见的需求,比如说: 各种游戏中有大量的随机,比如扑克游戏洗牌 微信抢红包,抢的红包金额是随机的 北京购...

27960
来自专栏DannyHoo的专栏

iOS开发中使用算法之冒泡法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u010105969/article/details/...

12330
来自专栏null的专栏

优化算法——遗传算法

与遗传算法的第一次接触 遗传算法是我进入研究生阶段接触的第一个智能算法,从刚开始接触,到后来具体去研究,再到后来利用遗传算法完成了水利水电的程序设计比赛,整个过...

2.2K60
来自专栏数据结构与算法

cf932E. Team Work(第二类斯特灵数 组合数)

$$m^n = \sum_{i = 0}^m C_{n}^i S(n, i) i!$$

11440
来自专栏程序员叨叨叨

7.1 Cg 关键字第 7 章 输入\输出与语义绑定

第三章从 GPU 运行原理和数据流程的角度阐述了顶点着色程序和片段着色程序的输入输出,即,应用程序(宿主程序)将图元信息(顶点位置、法向量、纹理坐标等)传递给顶...

16830
来自专栏技术总结

算法(3)

22870
来自专栏freesan44

python 算法开发笔记

21920
来自专栏算法channel

图算法|Prim算法求最小生成树

01 — 一个实际问题 要在n个城市之间铺设光缆,要求有2个: 这 n 个城市的任意两个之间都可以通信; 铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,...

1.1K70

扫码关注云+社区

领取腾讯云代金券