用顶点着色问题的贪婪算法解决排课问题  

Schedule Arrangement Algorithm Based on Greedy Method for Vertex Coloring Problem

作　　者：魏明山[1] 章丰田[1] 苏海艳[1] 杨雪莲[1] 米小娟[1] 

机构地区：[1]太原科技大学,山西太原030024

出　　处：《电脑学习》2010年第2期105-108,共4页Computer Study

基　　金：太原科技大学大学生创新训练计划(UIT)项目(项目编号:2009042)

摘　　要：顶点着色的贪婪算法中"按给定的顺序、满足一定的条件依次对顶点着色过程"可视为"按给定的顺序、满足一定的条件依次将顶点放入不同(颜色)的盒子中的过程",受此启发,设计相应的排课算法,首先提出"数量约束"的概念,给出该问题的具体需满足数量约束的项;然后将总表中的每条记录看成一个"顶点",将一张课表中每一个具体的表格视为不同(颜色)的"盒子",设计相应的启发式规则;最后把排课的过程巧妙的变成把每个"顶点"按相应的规则、在满足"数量约束"的要求的前提下放入上述"盒子"中的过程。The procedure of process vertex coloring problem with greedy method（coloring all the vertexes in a given order such that some conditions）can be seen as the procedure of putting all the vertexes into different color boxes in a given order such that some conditons.The paper devise the schedule arrangement algorithm based on this idea.Firstly,it defines the concept of quantity restriction and list the needed items satisfying the quantity restriction.Then it considers every record as a vertex,considers every sheet in a school timetable as a box with different color,and designs some heuristic rules.At last,it changes the procedure of arranging schedule into the procedure of putting all the vertexes into different color boxes in a given order by some heuristic rules such that some quantity restrictions.

关 键 词：排课 顶点着色 贪婪算法 数量约束 启发式规则 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]