顶点着色算法解决考试安排冲突的研究

摘要： 本文介绍了顶点着色法的基本机理，举例说明了顶点着色算法在考试安排中的应用。通过实际使用，该算法有效地解决了考试安排冲突的问题，且执行效率较高。

关键词： 顶点着色算法 考试安排 算法实施

1.引言

在高校教学管理工作中，经常会遇到这样的问题：有门课程被多名学生选修，每一位学生每场考试只能参加一门，那么最少需要多少场次安排完毕？显然，同一学生选修的两门课程不能在同一时间考试。当然，没有相同学生的课程可以安排在同一时间考试。这样问题可以总结为：在给定一个图G=（V，E），|V|=n，（V，V）∈E，当且仅当有一个同学选了课程i和课程j，试给出一个考试安排方案：

N，N，N，…，N，N∩N=?（s≠t，1≤s，t≤k）且V=N（1≤i≤k）。

2.算法描述

2.1顶点着色算法介绍

已知某无向图G=（V，E），图G的顶点最大值d={d（v）}，那么无向图顶点集合为V（G）={v，v，v，…，v}，顶点着色集合为：x={x，x，…xd}。

（1）设未染色的顶点集合D=D，已染色的顶点集合D=φ，i=0，取色数x∈x，对?坌∈D，x∶v，D{v}+D，x∶D，DD+D，D，PP+{v}+D（其中P为用颜色X所染色的顶点集合），ii+1。

（2）?坌∈D，设x∈x，x∶v，D{v}+D，D，x∶DID，DD+DID，P+{v}+D，ii+1。

（3）假若D=D，那么进入第（4）步，否则进入第（2）步。

（4）输出顶点颜色，停止执行。

3.算法实施

下面通过一个例子说明此算法在考试安排中的使用。

如图1所示：G=（V，E）是一个无向图，下面利用上面描述的算法对此图的顶点进行着色：

第一步：假设学生A选择了课程1、课程4，那么可以将课程1安排在第1场（设置为蓝色），课程4安排在第2场（设置成红色），如下图所示：

第二步：找出与课程1不冲突的课程（与顶点1不直接连接的顶点），也安排在第1场次考，如课程3、5。在选择3、5课程与课程1同时安排考试时，为减少后面出现冲突，最好选择选课人数最多的课程安排，假设3、5课程中选择课程5的人最多。那么，我们选择课程5与课程1同时考试，设置顶点5的颜色为蓝色。如下图所示：

第三步：继续找与课程1、课程5没有直接连接的点，将顶点颜色标识为蓝色。在上图中可以看到课程3没有与课程1、5直接相联，所以我们可以将课程3安排在第一场进行考试。如下图所示：

第四步：查看是否有与顶点1、3、5没有直接的点，如果没有当次循环结束。

第五步：进入第二场考试安排，查看与课程4没有直接连接的顶点。分析上图得知，课程2与课程6都没有与课程4直接连接可以安排在第二场考试。

通过以上分析，课程1、3、5可以安排在第一场考试，课程2、4、6可以安排在第二场考试。

为了进一步验证顶点着色算法在考试安排冲突问题上的卓越表现，随机选择3075名学生，共选修了100门课程。得出该算法执行效率统计结果如下图所示。

4.结语

通过顶点着色法在考试安排中的实际应用，实验结果表明，顶点着色算法在解决考试冲突问题上，针对3075名学生，100门课程仅使用了3秒钟便安排完毕。

尽管如此，算法仍有需要改进的地方。今后工作将主要集中在以下方面：可以采用路分治算法充分并行化；采用并行虚拟机技术，使算法在互联网络的PC机上实现并行。

参考文献：

［1］王晓贺，蔡国永.基于描述逻辑的策略冲突检测方法研究及实现［J］.计算机工程与科学，2008，（06）.

［2］朱晓林.冲突检测的Java实现［J］.计算机与数字工程，2006，（03）.

［3］洪斌.平面图着色的遗传算法［J］.贵州大学学报（自然科学版），1999，（04）.

［4］王绍文.平面图的四色算法［J］.光子学报，1995，（03）.

［5］王琳，虞厥邦.基于遗传机制的图着色分配算法的研究［J］.云南大学学报（自然科学版），2000，（04）.

［6］王小琼.基于粒子群的图顶点着色算法［D］.西安：华中科技大学，2007.

［7］廖辉传.基于遗传和启发式算法的混合顶点着色算法［J］.吉首大学学报（自然科学版），2008，（09）.

［8］Bodlaender H L.On the complexity of some coloring game［A］.in：Proceedings of WG，Workshop on Graph Theoretical Concepts in Computer Science，1999：35-39.

［9］J.A.Bondy and U.S.R.Murty，Graph Theory with Applications，the Macmillan Press LTD，1976.

［10］Guruswami V，Hastad J，Sudan M.Hardness of approximate hypergraph coloring.IEEE，2000.

［11］Karp R M.Reducibility among combinatorial problems.In：Raymond E.Miller and James W.Thather，plexity of Computer Computations，Plenum Press，1972：85-103.

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文