发布时间 : 星期四 文章排课表问题的数学原理及其算法研究更新完毕开始阅读7b3dfca4ccbff121dc36831e
2013届本科生毕业论文
1．3 解决NP问题的几种算法及其比较
解决NP完全问题只能依靠近似算法,所以下面介绍几种常用算法的设计思想,包括动态规划、贪心算法、回溯法等.
（一）动态规划算法
动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移.一个决策序列就是在变化的状态中产生出来的.所以,这种多阶段最优化决策解决问题的过程就称为动态规划.
(1)基本思想与策略
基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息.在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解.依次解决各子问题,最后一个子问题就是初始问题的解.
由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中.
动态规划算法与分治法最大的差别是:适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解).
(2)适用的情况
能采用动态规划求解的问题的一般要具有3个性质:
A 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理;
B 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响.也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关;
C 有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到.(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势).
(3)求解的基本步骤
动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态.这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线):初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态.
动态规划的设计都有着一定的模式,一般要经历以下几个步骤:
Ⅰ 划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段.在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解;
Ⅱ 确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来.当然,状态的选择要满足无后效性;
Ⅲ 确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态.所以如果确定了决策,状态转移方程也就可写出.但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程.寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件.
一般,只要解决问题的阶段、状态和状态转移决策确定了,就可以写出状态转移方程（包括边界条件）.实际应用中可以按以下几个简化的步骤进行设计: ⅰ 分析最优解的性质,并刻画其结构特征; ⅱ 递归的定义最优解;
ⅲ 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值; ⅳ 根据计算最优值时得到的信息,构造问题的最优解.
(4)算法实现的说明
动态规划的主要难点在于理论上的设计,也就是上面4个步骤的确定,一旦设计完成,实现部分就会非常简单.使用动态规划求解问题,最重要的就是确定动态规划三要素: ① 问题的阶段;
② 每个阶段的状态;
③ 从前一个阶段转化到后一个阶段之间的递推关系.
2
2013届本科生毕业论文
递推关系必须是从次小的问题开始到较大的问题之间的转化,从这个角度来说,动态规划往往可以用递归程序来实现,不过因为递推可以充分利用前面保存的子问题的解来减少重复计算,所以对于大规模问题来说,有递归不可比拟的优势,这也是动态规划算法的核心之处.
确定了动态规划的这三要素,整个求解过程就可以用一个最优决策表来描述,最优决策表是一个二维表,其中行表示决策的阶段,列表示问题状态,表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大价值等),填表的过程就是根据递推关系,从1行1列开始,以行或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解.
（二）贪心算法
当一个问题具有最优子结构性质时,我们会想到用动态规划法去解它,但有时会有更简单、更有效的算法,即贪心算法.顾名思义,贪心算法总是做出在当前看来最好的选择.也就是说贪心算法并不是整体最优上加以考虑,他所做出的选择只是在某种意义上的局部最优的选择.虽然贪心算法不是对所有问题都能得到整体最优解,但对范围相当广的许多问题它能产生整体最优解,如图的算法中单源最短路径问题,最小支撑树问题等.在一些情况下,即使贪心算法不能得到整体最优解,但其最终结果却是最优解的很好的近似解.
在贪心算法中较为有名的算法是Dijkstra算法[4].它作为路由算法用来寻求两个节点间的最短路径.Dijkstra算法的思想是:假若G有n个顶点,于是我们总共需要求出n?1条最短路径,求解的方法是:初试,写出V0(始顶点)到各顶点(终顶点)的路径长度,或有路径,则令路径的长度为边上的权值;或无路经,则令为∞.再按长度的递增顺序生成每条最短路径.事实上生成最短路径的过程就是不断地在始顶点V向终顶点W间加入中间点的过程,因为在每生成了一条最短路径后,就有一个该路径的终顶点U,那么那些还未生成最短路径的路径就会由于经过U而比原来的路径短,于是就让它经过U.
（三）回溯法
回溯算法也叫试探法,它是一种系统地搜索问题的解的方法.用回溯算法解决问题的一般步骤: a 针对所给问题,定义问题的解空间,它至少包含问题的一个（最优)解; b 确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间;
c 以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索.
问题的解空间通常是在搜索问题解的过程中动态产生的,这是回溯算法的一个重要特性.确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以深度优先的方式搜索整个解空间.这个开始结点就成为一个活结点,同时也成为当前的扩展结点.在当前的扩展结点处,搜索向纵深方向移至一个新结点.这个新结点就成为一个新的活结点,并成为当前扩展结点.如果在当前的扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点.此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点成为当前的扩展结点.回溯法即以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止.
回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试.八皇后问题就是回溯算法的典型,第一步按照顺序放一个皇后,然后第二步符合要求放第2个皇后,如果没有符合位置,那么就要改变第一个皇后的位置,重新放第2个皇后的位置,直到找到符合条件的位置就可以了.回溯在迷宫搜索中使用很常见,就是这条路走不通,然后返回前一个路口,继续下一条路.回溯算法说白了就是穷举法.不过回溯算法使用剪枝函数,剪去一些不可能到达最终状态(即答案状态)的节点,从而减少状态空间树节点的生成.回溯法是一个既带有系统性又带有跳跃性的的搜索算法.它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树.算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解.如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯.否则,进入该子树,继续按深度优先的策略进行搜索.回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束.而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可以结束.这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,它适用于解一些组合数较大的问题.
2 目前流行的几种排课算法的介绍
2．1 自动排课算法 2.1.1 问题的描述
3
2013届本科生毕业论文
我们讨论的自动排课问题的简化描述如下:
设要安排的课程为{C1,C2?,Cn},课程总数为n,而各门课程每周安排次数(每次为连续的2学时)为{N1,N2?,Nn};每周教学日共5天,即星期一～星期五;每个教学日最多安排4次课程教学,即1～2节、3～4节、5～6节和7～8节(以下分别称第1、2、3、4时间段).在这种假设下,显然每周的教学总时间段数为5×4=20,并存在以下约束关系:
n?20 (1) N?6n, i?1, Ni?20 (2) 自动排课问题是:设计适当的数据结构和算法,以确定{C1,C2?,Cn}中每个课程的教学应占据的时间段,并且保证任何一个时间段仅由一门课程占据. 2.1.2 主要数据结构
对于每一门课程,分配2 个字节的“时间段分配字”(无符号整数) :{N1,N2?,Nn} . 其中任何一个时间段分配字(假设为Ti) 都具有如下格式:
Ti的数据类型C 语言格式定义为:unsigned int . Ti的最高位是该课程目前是否是有效的标志,0 表
示有效,1 表示无效(如停课等) ;其它各位称为课程分配位, 每个课程分配位占连续的3 个位(bit) ,表示某教学日(星期一～ 星期五) 安排该课程的时间段的值,0 表示当日未安排,1 ～ 4 表示所安排的相应的时间段(超过4 的值无效) .
在这种设计下,有效的时间段分配字的值应小于32768 (十六进制8000) ,而大于等于32768 的时间段分配字对应于那些当前无效的课程(既使课程分配位已设置好也如此),因此很容易实现停课/ 开课处理.
2.1.3 排课算法
在上述假设下,自动排课算法的目标就是确定{C1,C2?,Cn}所对应的{T1,T2?,Tn}从安排的可
20!种排法(N的含义见(2)式).如果有4 门课,每门课一周上2 次,则N?8,这8 次
(20?N)!20!课可能的安排方法就会有= 5079110400,即50 多亿种. 如果毫无原则地在其中选择一种方案,
(20?8)!能性上看,共有
将会耗费巨大量的时间. 所以排课的前提是必须有一个确定的排课原则. 我们采用轮转分配法作为排课原则: 从星期一第1 时间段开始按{C1,C2?,Cn} 中所列顺序安排完各门课程之后(每门课安排1次),再按该顺序继续向后面的时间段进行安排,直到所有课程的开课次数符合{N1,N2?,Nn}中给定的值为止. 在算法描述中将用{C[1],C[2]?,C[n]} 表示{C1,C2?,Cn}, 对{N1,N2?,Nn}和
{T1,T2?,Tn} 也采用同样的表示[5].
算法1 排课算法[6]
输入:{C1,C2?,Cn}、{N1,N2?,Nn}, 输出:{T1,T2?,Tn}. ① 初始化:
星期值Week?1;
时间段值Segment?1;
{T[1],T[2],?T[n]}中各时间段分配字清零.
② 新一轮扫描课程:
置继续处理标志flag?0;
对课程索引值c?index?1,2,?n进行以下操作:
]?0,则做以下操作: 如果N[c?index把segment的值写入T[c-index]的第(week-1) 3 3～week 3 3 - 1位中N[c?index]的值减1;
]?0,则置flag?1; 如果N[c?index如果Week?5 并且Segment?4;
4
2013届本科生毕业论文
则:置flag?1并转③;
否则:如果Segment?4; 则:置Segment?1且Week增1;
否则:Segment增1;
检测是否已全部安排完毕: 如果flag?1; 则:转②; 否则:转③.
③ 检测是否成功: 如果flag?1; 则:开课次数过多; 否则:课程安排成功. ④ 算法结束
显然,本算法的时间复杂度为O(n)(n为每周总开课次数,见(2)式),而存储时间段分配字所用空间为2n个字节(n为课程门数). 2.1.4 冲突检测算法
有时在自动排课完毕后,需要人工调整某些课程的安排时间,如把第i门课程在人工干预下改成星期数为week、时间段为segment的位置,则根据上述数据结构需做如下运算:
T[i]?T[i]&(~(7??(week?1)*3))?(segment??(week?1)*3)[7] (3)
其中&、～和n分别为按位与、按位取反和按位左移运算符(下同).
问题是如何判断是否已有其它课程安排在同一个时间段上. 设人工调整的时间段分配字为T[1],则该问题描述为:判断时间段分配字T[1] 与{T[2],T[3]?,T[n]} 中的某个分配字是否存在相同课程分配位上的相等的非零时间段值,或者说{T[2],T[3]?,T[n]}中是否存在与T[1] 冲突的时间段分配字. 为简化起见,在以下算法描述中假设所有时间段分配字的最高位为0. 算法2 冲突检测算法 输入: T1和{T2,T3,?Tn};
输出:与T1 冲突的{T2,T3,?Tn} 中的时间段分配字.
① 对c-index = 2,3, ?,n 做以下操作: 初始化屏蔽字mask?7;
对星期值Week?1,2,3,4,5做以下操作:
如果T[1] & mask 等于T[c-index] & mask,而且二者不等于0 则: T[1]与T[c-index ]相冲突,转① mask 左移3 位(或乘8) ② 算法结束
本算法时间复杂度为O(n)( n 为课程门数) 2.1.5 算法分析
此算法以课程为中心,进行搜索匹配,取最先匹配的值;具有占有空间少,运算速度快的特点.但其未对数据进行择优选取,所以不能对教学资源（教师、教室)合理分配,也不能满足一些特殊要求(比如有些老师喜欢上午上课,有些老师偏向于集中式上课;有些课程安排到上午会更合适些,有些课程不能安排到上午等). 2．2 基于优先级的排课算法
从数学上讲,排课问题是一个在时间、教师、学生和教室四维空间,以教学计划和各种特殊要求为约束条件的组合规划问题.其实质就是解决各因素之间的冲突.在设计算法时,为了降低课程调度
[8]
的算法复杂性,我们主要采用了化整为零的思想及优先级算法. 2.2.1 排课的预处理 2.2.1.1 等价类的划分
将具有共同听课对象的任务划分在同一等价类中,在每个等价类之间只存在地点上的冲突,而没
5