排课表问题的DNA计算摘要：本文首先把边着色问题转化成可满足性问题，然后利用lipto
解决sat思想来解决边着色问题，最后应用一个实例来说明算法。关键词：sat问题；边着色；d
a计算中图分类号：tp3016文献标识码：a文章编号：100795992013070000021引言近年来，随着在校学生人数逐年增多，高校排课安排成为一项复杂的工作。课表问题是运筹学中的时间表问题，课表问题涉及到众多因素，包括：教师、班级、教室和授课时间等。1995年pri
ceto
大学的lipto
解决了sat问题。本文从图论的角度采用d
a计算来对简单课表问题进行解决。d
a计算一般由两个步骤构成：第一步，建立一个大的可行解集合的数据库；第二步，将那些不满足所给定问题的解的数据逐一删除。2基于图论的排课模型21简单排课表问题假设教学要求的关联矩阵如表1所示，其中，表示教师，表示班级，教师表示教师需要给上课的次数。表1对应的关联矩阵可表示成一个图，如图1所示。图1由图1可知：图是以一个以为顶点集，授课关系为边集的二
f分图，边集表示。22用边着色理论分配课时定义：设是无环图，若能用种颜色给的边着色，使相邻边具
有不同颜色，则称是边可着色的，边着色数称为图的一个正常边着色。图的正常边着色的最小值，称为的边色数，用表示。
定理1：设是无环图，则。证：因为相邻边具有不同颜色，所以与顶点关联的边必须着不同颜色，故。定理2：设是二部图，则。3排课问题的算法设计31问题描述本文将图的边着色问题转化为sat问题来解决。引入以下定理：定理1图的边着色问题可以转化成为sat问题。证明：令，其中。则图的每一种着色方案对应于向量的一种赋值方案。则：（1）每一条边着一种颜色。等价于：。（2）相邻的边着不同的颜色。等价于：对于，对应的边为，，其中表示边和的相邻关系，（1表示相邻，0表示不相邻），则对于，满足。因此，图一种着色方案是否为正常着色问题的问题等价于合取范式是否为真的问题。32边着色问题的d
a计算。具体算法如下：步骤1：对图的每
f条边进行d
a编码，生成图的所有边着色，即得到初始数据池试管；步骤2：删除有边没有着色的d
a序列，保留图g的所有边着色；步骤3：以顶点关联的边为约束条件通过删除实验，得到边着色。
4一个实例下面用上述算法来求解7个顶点、7条边的无向简单图（如图1）的边3着色问题。其中颜色集合为。对于图1所对应的邻接矩阵为，元素，如下：该简r