（计算机应用技术专业论文）高校排课系统的研究.pdf

湖北工业大学硕士学位论文 摘要 排课是高等院校教学管理中必不可少的常规工作，同时也是整个教学管理中 最复杂、最繁重的工作之一。排课问题普遍存在于各类高等院校当中，无论其规 模大小、学科多少，都要涉及到课表编制。伴随着高等教育事业的不断发展和在 校大学生人数的逐渐增加，高校课程的开设必将朝着更广、更深的方向发展，高 校课表的合理编排和科学调度在高校教学管理中作用更加凸现，它有利于师生之 间教与学的适当平衡，有利于日常教学工作的平稳推进，有利于教学质量的稳步 提高，有利于教学资源的高效利用，对建设和谐校园更是不可或缺。 虽然排课问题较早地被人所研究，但是由于其具有规模大、约束复杂以及规 律不断变化等特点，加之排课冲突现象一直存在，解决冲突时所采用的不同回溯 算法又各有千秋，使得排课问题一直难以得到突破性进展，故而排课问题至今仍 在继续研究。 随着计算机软件技术的飞速发展，各式各样的排课软件相继产生，但由于各 个高校教学情况的现实差异，造成难以使用统一的软件完成排课任务，主要表现 在教学资源条件不同、课程设置要求不同以及课程编排方式不同等等。 本文在认真研究排课问题以及相关算法的基础上提出一种基于动态规划思想 和优先级自动编排的新排课算法。此算法可根据教室、教师、时间和班级的约束 关系，做出等价类划分。根据所设定的优先级顺序完成一次性扫描排课，尽量避 免调整冲突，并在此基础上实现了一个课程调度系统，既使为适应学分制排课要 求或满足教师提出较苛刻的上课条件要求，也能在较短时间内完成排课计划，本 文以某学校附属学院排课系统( 以下简称p c a 系统) 为例对排课问题的数学模型 进行了详细描述，设计以编码形式来表达优先级，对排课系统中的数据设计进行 了细致分析，对在自动排课处理中涉及的分治法、贪心法、回溯法三种算法思想 进行了描述，并提出广度优先回溯算法( 以下简称b f b ) 。对基于优先级自动编排 算法的实现步骤进行了描述，最后结合排课软件的发展趋势以及实际需求提出某 学校附属学院排课系统整体规划确定p c a 系统的功能结构。对系统的网络模型等 方面的软硬件环境详细描述；并对存在问题进行了分析和探讨；对系统未来的发 展做出展望。 关键词：排课系统，p c a ，动态规划，优先级，广度优先回溯 湖北工业大学硕士学位论文 i i 1 1 一i i i i _ _ ，i i _ l a b s t r a c t c o u r s es c h e d u l i n g ，an c c e s s i t yo fu n i v e r s i t yt e a c h i n gm a n a g e m e n t , i sc o n s i d e r e dt o b ec o m p l e xa n dh e a v ya m o n go t h e rt a s k sr e g a r d l e s so fi t ss i z ea n ds u b j e c t s w i t ht h e d e v e l o p m e n to fh i g h e re d u c a t i o na n di n c r e a s i n gn u m b e ro fc o l l e g es t u d e n t s ，c o u r s e a r r a n g e m e n tw i tb eh i g m yp r o m o t e d aw e l lb a l a n c e dc o u r s es c h e d u l i n gs y s t e mw o u l d p l a ya l li m p o r t a n tp a r ti nt h et e a c h i n gm a n a g e m e n to w i n gt oi t sb e n e f i t sa sf o l l o w i n g s ： k e e pab a l a n c eb e t w e e nt e a c h i n ga n dl e a r n i n g ；i m p r o v et h ed a i l yw o r ko ft e a c h i n g m a n a g e m e n t ；k e e pa d v a n c i n go ft e a c h i n gq u a l i t y ；e f f e c t i v e l ym a k eu s eo ft e a c h i n g r e s o u r c e sa n da l s oa c ta sa ni n d i s p e n s a b l ep a r to fb u i l d i n gu pah a r m o n i o i l ss c h o o l e n v i r o n m e n t n 忙r e s e a r c ho nt h ec o u r s es c h e d u l i n gi ss t i l lu n d e re x p l o i t a t i o na l t h o u g hw i t hs o m a n ya c h i e v e m e n t si nd i f f e r e n ta r e a s h o w e v e r , j tr e m a i n st ob cp r o b l e m si ns o m ea r e a s a si t su n a v o i d a b l et r a i t s l i k el a r g ei ns i z e ，c o m p l e xi nr e 翻l l - i c t , v a r i o u si nr u l e s w h a t s m o r e ，b a c k t r a c k i n ga l g o r i t h mi sn o ts a t i s f y i n gi nt a c k l i n gc o n f l i c t st h a to f t e ne x i s ti n c o u r s es c h e d u l i n g w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rs o f t w a r et e c h n o l o g y , v a r i o u ss o f t w a r eo f c o u r s es c h e d u l i n gs p r i n gu p b u t 晰t hr e g a r dt ot h ei n d i v i d u a ld i f f c r e n c eo fu n i v e r s i t i e s ， t h e r ea r en os a t i s f y i n gr e a c t i o n st oc o m p l e t es u c hai o b 、撕t hu n i f i e do n e t h er e a s o n sl i e i nt h ed i f f e r e n c e so ft e a c h i n gr e s o u r c e s ，c o u r s ea r r a n g e m e n ta n ds c h e d u l i n g ，e t e an e wc o u r s es c h e d u l i n ga l g o r i t h m ( p c a ) o nt h eb a s i so fd y n a m i cp r o g r a m m i n g t h o u g h ta n da u t o m a t i cp r i o r i t ys c h e d u l i n gi sb r o u g h ta b o u ta f t e ra n a l y z i n gc o u r s c h e d u l i n ga n dr e s e a r c h i n gr e l a t e da l g o r i t h m s ，f r o mw h i c he q u i v a l e n tc a t e g o r yc a nb e d o n ea c c o r d i n gt ot h ec o n s t r a i n tr e l a t i o n sl i k et i m e ，c l a s s r o o m , t e a c h e ra n dc l a s s ，a n d t h e no i l e - o 疗s c a n n i n gt i m e t a b l es c h e d u l i n gi sc o n d u c t e dw i t ha s s i g n e dp r i o r i t yo r d e r , a v o i d i n ga d j u s t m e n tt ot h ec o n f l i c t sa n dt h u sas c h e d u l i n gs y r s t e mc a nb er e a l i z e di nt h i s w a y c o u r s es c h e d u l i n gc a l lb ef i n i s h e di nas h o r tt i m en om a t t e rw h a tc r e d i ts y s t e ma n d t e a c h e r sd e m a n df o r t a k i n gat i m e t a b l es c h e d u l i n gs y s t e mo fau n i v e r s i t y sb r a n c h s c h o o lf o re x a m p l e ，t h i sp a p e rf i r s td e s c r i b e si t sm a t h e m a t i cm o d e li nad e t a i l e dw a y a n di n d i c a t e sp r i o r i t yi nc o d e df o r m a n dt h e n , i ta n a l y z e st h ed a t ad e s i g n i n gi np c a s y s t e r na n db r i n g sa b o u tt h eb r e a d t h - f i r s tb a c k w a r da l g o r i t h m w i t hs t e p so nt h e s u m m a r yo ft h e o r i e sc o n c e r n i n gw i t ha u t o m a t i cs c h e d u l i n gl i k cd i v i d i n g ，b a c k t r a c k i n g a t1 a s t , w i t har e g a r dt ot h et r e n da n dr e q u i r e m e mo ft h i sb r a n c hs c h 0 0 1 t h ep a p e r p r o v i d e sag e n e r a lp l a nw h i c hh a sd e f i n e dt h ef u n c t i o n a ls t r u c t u r eo fp c as y s t e ma n d g i v e nad e s c r i p t i o ni ni t sn e t w o r km o d e l ，t o p o l o g ys t r u c t u r ea n dr e q u i r e ds o f t w a r ea n d h a r d w a r ee n v i r o n m e n t , a sw c l la sa na n a l y s i sa n de x p l o i t a t i o nf o rp o s s i b l ep r o b l e m s n l ep a p e ri sc o n c l u d e dw i t ha no u t l o o kf o rt h ea p p l i c a t i o no ft h es y s t e mi nt h ef u t u r e k e y - w o r d s ：t i m e t a b l es c h e d u l i n gs y s t e m ，p c a ，d y n a m i cp l a n n i n g ，p r i o r i t y ，b r e a d t h f i r s t b a c k w a r d i i 湘如j 棠大謦 学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取 得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体己经 发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律结 学位论文作者签名： 魄中妨如日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，p , p ：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权湖北工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 学位做作者鲐事多旮渖指导教师始t 烈聪 日期：o q 年 月加日 日期： 哆年勋知日 | 拭呵 慷协_ _ 本山p扛1 果 湖北工业大学硕士学位论文 1 1 研究背景 第1 章绪论 排课是高等院校教学管理中必不可少的常规工作，同时也是整个教学管理中 最复杂、最繁重的工作。排课问题普遍存在于各类高等院校当中，无论其规模大 小、学科多少，都要涉及到课表编制。伴随着高等教育事业的不断发展和在校大 学生人数的逐渐增加，高校课程的开设必将朝着更广、更深的方向发展，高校课 表的合理编排和科学调度在高校教学管理中作用更加凸现，它有利于师生之间教 与学的适当平衡，有利于日常教学工作的平稳推进，有利于教学质量的稳步提高， 有利于教学资源的高效利用，对建设和谐校园更是不可或缺。 虽然排课问题较早地被人所研究，但是由于其具有规模大、约束复杂以及规 律不断变化等特点。加之排课冲突现象一直存在，解决冲突时所采用的不同回溯 算法又各有千秋，使得排课问题一直难以得到突破性进展，故而排课问题至今仍 在继续研究。 随着计算机软件技术的飞速发展，各式各样的排课软件相继产生，但由于各 个高校教学情况的现实差异，造成难以使用统一的软件完成排课任务，主要表现 在教学资源条件不同、课程设置要求不同以及课程编排方式不同等等。 1 1 1 高校排课系统的发展 编排课程最早是手工编排，具体分为下列几个步骤：( 1 ) 由教学管理人员查 询全校教学日历表以及各专业教学计划表( 2 ) 将教学任务交至各个学院( 3 ) 负 责接收教学任务的学院及时安排教师授课并将信息报教学管理人员汇总( 4 ) 完成 全校课程的编排，必须保证教室、教师、时间、班级等安排不发生冲突( 5 ) 列出 各班级课表并发放到每个班上( 6 ) 列出教师课表发放给教师( 7 ) 列出全校课表、 教室课表等以各教学管理人员查询。 对于手工编排而言，必须依赖一批经验丰富的、熟悉教务管理的工作人员一 起，集中数周时间完成编排任务。同时，还需要处理排课过程中的各种冲突，在 此基础上经过专人反复检查修订，直到符合要求为止。由此可见，手工排课费时 费力而且错误率高，并且随着班级或课程数量的增加，手工排课越来越难以实现。 湖北_ t - - 业大学硕士学位论文 1 1 2 排课问题的重要性 排课是高等院校教学管理中必不可少的常规工作，同时也是整个教学管理中 最复杂、最繁重的工作。排课问题普遍存在于各类高等院校当中，无论其规模大 小、学科多少，都要涉及到课表编制。科学地编制课程表，合理地搭配课程，适 当地平衡师生之间的教与学，充分地利用教学资源，对稳定教学秩序，提高教学 质量，都起着及其重要的推动作用。 随着教学管理信息系统的逐渐普及，教学管理中排课问题也备受广大师生的 关注。若用t ，s ，c 分别表示时间、教室、教师和班级，a 表示算法复杂度，则有 a = f ( t , r , s ，c ) ，其中f 是由t , r , s ，c 确定的四元函数，这四个因素的相互制约和冲 突是排课问题的核心。国外早在上世纪5 0 年代就开始有人研究，2 0 世纪9 0 年代 有关排课问题的研究仍然没有间断相关研究所使用的技术概括起来，包括整数 规划、图论、分支定界技术及模拟退化法等，实践证明仅仅使用数学方法解决繁 重的排课问题很难行得通，而借助运筹学中的动态规划思想将问题有机分解，则 可能是一个有效地解决方法。国内对于排课问题的研究从8 0 年代也已经开始，虽 然产生了相关的排课软件，但是其需要苛刻的条件约束，仅仅是一个比较复杂的 信息决策系统：特别是目前高等学校逐步实行学分制，课程班建制逐渐被打乱， 还有例如英语等各类教学改革的需要，附属学院以及职业学院大量教学任务的承 担，在加之本身教师和教室资源短缺，倘若安排教学时要求对教师要求( 例如要 求4 节连上、指定上课时间或指定时间范围、提出较苛刻的教学条件等) 在一定 范围内尽量满足，那么相应的约束条件势必大量增加，十分苛刻，自动排课更加 艰难，目前尚未有普遍适用的解决办法。 1 2 研究的目的 本文在认真研究排课问题以及相关算法的基础上提出一种基于动态规划思想 和优先级自动编排的新排课算法p c a 射。此算法可根据教室、教师、时间和班级 的约束关系，做出等价类划分，根据所设定的优先级顺序完成一次性扫描排课， 尽量避免调整冲突，并在此基础上实现了一个课程调度系统。既使为适应学分制 排课要求或满足教师提出较苛刻的上课条件要求，也能在较短时间内完成排课计 划，本文以某学校附属学院排课系统( 以下简称p c a 系统) 为例，对排课问题的 数学模型进行了详细描述，设计以编码形式来表达优先级，对p c a 系统中的数据 设计进行了细致分析，对在自动排课处理中涉及的分治法、贪心法、回溯法三种 算法思想进行了描述。并提出广度优先回溯算法( 以下简称b f b ) ；对基于优先级 2 湖北工业大学硕士学位论文 自动编排算法的实现步骤进行了描述。最后，结合排课软件的发展趋势以及实际 需求，提出某学校附属学院p c a 系统的总体规划，确定p c a 系统的功能结构。对 系统的网络模型、拓扑结构、系统实现的软硬件环境做详细描述，并对存在问题 进行了分析和探讨，对系统未来的发展做出展望。 1 3 相关文献综述 上世纪5 0 年代国外就有人开始研究课表编排问题。g o t l i e b 曾提出一个课表问 题的数学模型i l 】，后来人们对课表问题的算法和解的存在性等问题做了深层次研究 但一直未有满意的结果。7 0 年代e v e n 等人证明了课表问题属于n p 完全类以后人 们才将注意力更多地转向课表编排实用算法的探索与研究上来，直到后期国外对 课表问题的研究也十分普遍，例如：印度的v a s t a p u r 大学管理学院的a r a b i n d a t r i p a t h y 嘲s l ，加拿大m o n t r e a l 大学的j e a na u b i n 、j a c q u e sf e f l a n d t 5 0 】等。当前解决 课表问题的方法主要是模拟手工排课法【2 3 1 ，图论方法【1 6 1 ，拉格朗日松驰法，二次 分配型法仁8 】等多种方法，实践证明仅仅使用数学方法解决繁重的排课问题很难行 得通，而借助运筹学中的动态规划思想将问题有机分解，则可能是一个有效地解 决方法。国内也早在8 0 年代初期就开始研究课表编排问题，例如：南京工学院的 u t s s ( a u n i v e r s i t yt t m e t a b l es c h e d u l i n gs y s t e m ) 系统田】、武汉大学的智能计算机 排课系鲥2 1 i 、清华大学的t i s e r ( t u n e t a b l es c h e d u l e r ) 系统【硼、大连理工大学 的智能教学组织管理与课程调度系统【3 0 l 等，绝大多数都是模拟手工排课过程以 “班”为单位，运用启发式函数进行编排的。但是，这些课表系统一般都较为依 赖于各个学校的教学体制，不具备良好的移植性。 1 4 本文的研究内容和组织结构 随着高校规模的不断扩大，教学管理难度日益增加等现实环境的不断变化， 逐步构建相应的教学管理信息系统显得十分有必要。该系统主要是为了进一步加 强学校教学管理工作，使其朝着更加科学、规范的方向发展，逐步建立信息化和 网络化管理平台；最终实现资源共享与信息交互。教学管理信息系统主要包括两 部分，即学籍管理和课表管理( 以下简称p c a 系统) 。 通过相关调查显示：国内外高校还没有完全实现数字化校园，也没有成熟的、 通用的校园信息管理系统。对于教学管理p c a 系统也没有较好的建设平台，因此， 本文首先从课表编排等问题着手，重点研究和开发能够满足实际要求的排课系统， 逐步实现功能模块化，以达到系统的网络化管理。 3 湖北工业大学硕士学位论文 经过调查了解到：当前部分学校正在使用的教学管理系统基本上只能满足自 己学校的实际情况，具体算法以及相关约束条件均以自身的教学机制为主，还不 适合广泛推广。课表编排与管理是教学管理系统中很重要的部分，是一个涉及多 种因素组合规划的问题。它必须保证在编排课程中教师、教室、学生三者不出现 冲突，主要是指将开设不同课程的两个或以上的班级编排在同一时间或同一教室， 或者是将某一个教师在同一个时间段编排两门或两门以上课程等诸如此类情况。 同时，要满足教师要求和教室资源等其他约束条件。 随着国家高等教育改革的逐步深化，全国各地高等院校附属学院发展十分迅 速，本文结合现实情况，以某学校附属学院教学管理情况为例，针对其教学管理 中存在的现实问题进行了深入分析和研究。例如：由于缺乏固定的师资，使得相 当一部分教学任务必须依靠聘请的教师承担，势必导致教师开课时间受到极大限 制，从而造成课程编排中教师时间约束更加严格、苛刻，对于部分教师开课时间 无法满足的情况，只能依靠手工逐个调整，不仅费时费力，而且容易产生冲突。 本文研究过程中，经过对解决排课问题常采用方法的仔细研究和归纳总结( 例如： 需求矩阵法，布尔型关联规则算法，模拟手工排课法，二次分配型法，整数规划 法，分支定界法及模拟退化法、图论方法，拉格朗日松弛法等) ，最终提出了一种 基于动态规划思想的优先级自动排课调度算法。 动态规划思想就是指先要找到要求问题最优解的性质，并按结构分类特征将 所求解问题分解成若干个子问题，首先找到子问题的解，然后从子问题的解中得 到所要求问题的解。其实质是分治思想和解决冗余。动态规划思想是寻求最优化 问题的一种全新的算法设计思想。在实际问题中，存在特殊问题的求解过程，受 到它本身特殊性的约束，可以将求解过程分成若干个相互联系的阶段，在它的每 一阶段均做出最优化决策，从而使整个问题求解达到最优化的效果。因此各个阶 段决策的选取绝不是任意确定的，它必须依赖于当前面临的状态，又影响到后面 的发展。当各个阶段决策确定后，自然组成了一个决策序列，随之也就确定了整 个问题求解过程的一条发展路线。类似把一个问题看作是一个前后关联具有链状 结构的多阶段过程就称之为多阶段决策过程，这种问题称之为多阶段决策最优化 问题。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划 思想的设计方法需要具体问题具体对待，绝对没有一种通用算法设计。 按照这个指导思想以教学计划中规定的课程为主进行一定分类，将具有共同 特征的课程教学任务划分在同一等价类中，再利用对不同要求的识别划分等价类， 迅速找到与之匹配的教室。对于教学计划中的所有课程，根据教室、教师、时间 和班级的约束，可以将其依次从高到低设定优先级，而对于极为特别的课程可以 湖北工业大学硕士学位论文 放在最后编排，例如：体育课既不占用教室资源，而且所涉及的教师是相对独立 的群体，即使需要调课，处理过程也相对比较容易。倘若个别学校限定了体育课 安排的具体时问，对于这种情况则只需要适当提高其优先级即可按照上面的优 先级设定依次实现排课任务，待所有课程全部编排完毕后，需要对所有课程进行 分支限界检查，例如：以合班课不可以在小班教室上，分班课尽量不安排在大班 教室上，相应特殊要求的课程只能在特殊教室上等等条件进行限定检查，进一步 核对排课情况是否满足要求，以提高课程编排的准确率和成功率。最后，对于不 成功的课程可以适当放松约束条件或者通过手工细微调整以达到满意的排课结 果。 本文主要讲述了高等学校教学管理中排课系统的研究过程，紧紧围绕排课的 算法设计，详细研究了基于动态规划思想的优先级自动排课调度算法，将动态规 划思想作为理论依据，深入介绍了其基本原理和实现方法，并对排课中的冲突问 题进行了深入剖析。通过介绍某学校附属学院信息系统教务子系统的开发情况， 归纳总结遇到的实际问题，进一步阐述了排课问题将来亟待努力研究的方向。 5 湖北工业大学硕士学位论文 第2 章排课算法的研究 2 1 排课问题的数学模型 2 1 1 相关任务描述 班级集合：b = b i ，b 2 ，b 3 ，b 4 ，b i ，b 。) ；b i = b n ，b i 2 ，b i j ， b 沁 ，其中b i j 表示单个自然班级，b i 表示专业和年级相关的实际班级，它可以是 个自然班，也可以是多个自然班。 课程集合：c = c l ，c 2 ，( 3 3 ，c 4 ，c 4 ，c k ) ； 教师集合：s = s l ，s 2 ，s 3 ，s 4 ，s i ，s d ； 教室集合：r = r j ，r 2 ，r 3 ，r 4 ，r i ，o o ) yr k ，r m ；其中，r k 表示具体 教室，属性包括：楼号、序号、大小( 以容纳人数为衡量标准) 、是否多媒体或语 音室等等。 时间集合：t = t l ，t 2 ，t 3 ，t 4 ，t i ，t n ) ； 时间t 包含周次( z ，z e 【l ，2 6 】) ，星期( w ，w e 1 ，7 】) ，节次( j ，j 【1 ， 5 】) ，一般课程是两节连排，节次中1 表示1 、2 节，2 表示3 、4 节以此类推。z 、 w 、j 均可根据实际情况的需要确定取值范围。 系统执行课程编排之前，( b c s ) 都是一一对应的任务单元( t a s k ) ，排课 的目的就是为每一任务单元分别安排相应的时间与地点( r t ) ，同时必须满足一 定的约束条件【3 3 j 。 2 1 2 限制条件 课表编排是一个组合规划问题，它涉及到课程、教师、时间、学生、教室五 种因素【2 l ，其中时间是影响冲突的最主要因素。产生冲突的晟根本原因是约束条件 比较复杂、苛刻，而在这些约束条件中，有一部分属于必须满足的，称之为硬性 条件：另一部分约束条件属于尽量要求满足的，称之为软性条件。 一、硬性条件 对于课表编排问题需要遵循的基本原则如下： 同一时间，同一个自然班开课不能超过- f 3 ； 同一时间，同一个教师上课不能超过- - 1 3 ； 同一时间，同一个教室开课不能超过- - f l ； 6 湖北工业大学硕士学位论文 任何一门课程的学生总人数必须小于或等于对应编排教室的实际座位数。 排课的过程就是遵循上述基本原则，将待编排的任务单元一一赋予合理的教 室和时间，并且保证排课结果相互之间不产生冲突。 二、软性条件 除了遵循基本规则以外，为了达到更好的教学效果还需要尽量满足一定的要 求，具体如下： 优先考虑教师时间因素，最大限度满足它； 优先考虑编排大合班课程或是涉及学生较多的课程； 以课程类别和教学效果为先决条件，尽量编排最好的上课时间以保证课程效 果； 一周之内在同一班级开设同一课程时，若学时较多尽量保持一定间隔； 同一班级上课学生数大致相同的课程尽量编排到相对相同或相近的教室； 尽量考虑到个别教师特殊的教学时间要求： 除上述情况之外的其他指定资源的特殊要求。 2 2 算法研究 2 2 1 算法描述 动态规划并不是一种具体的算法，而是一种算法的设计思想，在具体运用当 中要根据实际问题遵循动态规划思想的原理来设计具体算法。 动态规划思想就是指先要找到要求问题最优解的性质，并按结构分类特征将 所求解问题分解成若干个子问题，首先找到子问题的解，然后从子问题的解中得 到所要求问题的解。其实质是分治思想和解决冗余。动态规划思想是寻求最优化 问题的一种全新的算法设计思想。在实际问题中，存在特殊问题的求解过程，受 到它本身特殊性的约束，可以将求解过程分成若干个相互联系的阶段，在它的每 一阶段均做出晟优化决策，从而使整个问题求解达到最优化的效果。因此各个阶 段决策的选取绝不是任意确定的，它必须依赖于当前面临的状态，又影响到后面 的发展。当各个阶段决策确定后，自然组成了一个决策序列，随之也就确定了整 个问题求解过程的一条发展路线。类似把一个问题看作是一个前后关联具有链状 结构的多阶段过程就称之为多阶段决策过程，这种问题称之为多阶段决策最优化 问题。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划 思想的设计方法需要具体问题具体对待，绝对没有一种通用算法设计。 动态规划思想的基本原理就是寻求最优化决策，具体描述为：对于具有1 1 个 7 湖北5 _ - 业大学硕士学位论文 输入的最优解问题，可将其活动过程划分成若干阶段，每一阶段的决策依赖于前 一阶段的状态，由决策所运用的动作使状态进行转移，成为后一阶段的决策依据。 早期5 0 年代就有人专门从事此项研究，他曾深入分析了一类多阶段问题的特 点，然后把多阶段决策问题通过某种合理划分将其转变成为了一系列相互关联的 单阶段问题，最后对其逐个加以解决。对于部分静态模型问题而言，只要我们人 为地引人“时间”因素，并将其有机拆分成各个时段，自然而然就实现了多阶段 动态模型问题的转化，从而利用动态规划思想的原理加以处理。与此同时，他总 结出了解决次类问题的最优化思想，即一个问题最优决策的性质：无论其初始状 态和决策为何，其之后所有策略对以第一个决策所形成的状态作为初始状态的过 程而言必须形成最优决策。概括起来就是，一个最优策略的子策略对于它的初态 和终态而言也一定最优的。使用数学语言来描述：假设需要解决一个具体优化问 题，首先要依次做出p l ，1 2 ，p n 决策，若此决策序列最优；则对于任何一个 整数k ( 1 删，无论之前k 个决策怎样，之后的最优决策仅取决于由前面决策所 确定的当前状态，同样之后的决策p k + l ，p n 是最优决策。 正是因为后一阶段的决策仅与前一阶段产生的状态有关，而与如何达到这种 状态的方式无关，我们才可以将任何一阶段都做为一个子问题来处理。决策过程 的每一阶段都可能有多种决策可以选取，但其中有且只有个决策是全局最优决 策。为此，假设某状态可以选择多种决策，每种决策都可能产生不同的状态。根 据最优化策略，对初始状态s o ，鼻2t a j ，p l 2 ，一p l ，一，是可能的决策值集合，由其产 生的状态6 - 2t 而j ，s t , 2 ，- ，r ，其中焉是对应于决策a ，产生的状态，目前还无法判 定最优决策，此时可将所有决策值集合作为子问题的解保存。同样如此，在状态 s l 上做出的决策值集合p 2 产生了状态s 2 集合，依次类推，对状态 墨一l2 s n 1 1 ，晶一l 2 ，一1 钿) 只= n j l ，见，1 ，p n , 2 l9 oo ，以，2 乜，见，卜1 1 ，p 。，似。) 县可 ，n 一 1 能的决策值集合，其中，决策值集合，- ”一y n , t 是依据状态j 川，t 所做出的可能的 决策。由只所产生的状态墨2 岛，1 1 ，与，& 2 l ，凡2 屯，抽l ，s n 钿) 。墨是最 终状态集合，其中只有一个最优状态。若假设是由决策“，所产生的j 哦。那么就 认为“ 是最优决策，而以 又是依据状态6 ，钿做出的，这样逐步回溯到初始状 态，从而得到最优决策序列t 只内p z 向，p 一，叫，而这个决策序列导致了状态转移序 列p o 一- 一z 恕。3 n v 。根据最优化策略，上述决策序列就是依据初始状态和初 8 湖北工业大学硕士学位论文 始决策_ 所产生的状态构成的最优决策序列。在上述决策过程当中，一直存在着 决策的策略或目标，我们将其称为动态规划函数，它随问题的性质和特点而变化， 并且发生在每一阶段的决策当中。整个决策过程既可以递归地进行又可以循环迭 代进行，同时，动态规划函数既可以递归定义又可以用递推公式来表达。最优决 策一般都是在最后阶段形成，然后依次向前倒推到初始阶段。但是，决策结果和 产生的状态转移是经过初始阶段计算，而后逐渐递归或迭代产生最终结果。 综上所述，最优化策略是动态规划设计思想的基础。所有需要使用动态规划 思想设计实现的问题都离不开最优化策略的支持。 动态规划又称线性规划，静态规划又称非线性规划，二者本质都是求解约束 条件下的极值问题。两种规划既有区别，又可以相互转换。前者可以看作是寻找 决策p l ，p 2 ，p i i 使目标函数v l 。( x l ，p l ，p 2 ，p 1 1 ) 达到极值，至于端点条件、允许状态 集、状态转移方程、允许决策集等均为约束条件，某种程度上都可以借助后者求 解。反之，后者某些时候在适当引入了阶段变量、状态、决策等因素时也可以利 用前者来求解。 但是，二者相比，动态规划的优越性比较明显，具体表现如下： ( 1 ) 全局最优解。在约束条件比较苛刻、复杂的情况下，使用非线性规划方 法很难求出全局最优解。线性规划方法则不同，它可以将全过程划分为若干个结 构相似的阶段，形成多个子问题。对于每个子问题而言，其变量个数大幅度减少， 约束集合也变得十分简单，较容易形成全局最优解。 ( 2 ) 一族最优解。静态规划所能得到的仅仅是整个问题的一个最优解，而动 态规划得到的是却是全过程以及所有子问题的一族最优解。这对于具体问题分析 最优策略或最优解，了解状态稳定性时十分具有参考价值。倘使由于特殊原因造 成最优策略无法实现，此时一族子问题的最优解可以为寻找次优策略提供帮助。 ( 3 ) 提高求解效率。因为动态规划思想充分体现了问题本身的动态特征以及 解决问题过程不断变化的前后关系，在解决实际问题过程中凭借丰富的经验可以 有效帮助提高求解效率。 动态规划作为一种程序设计思想，它不仅体现了广泛的应用价值，而且在解 决许多实际问题方面显得十分便捷、高效。比如就规模为n 的问题而言，若搜索 算法的时间复杂度为o ( n ! ) ，则动态规划思想的算法设计时间复杂度为o f n 2 ) 。由 此可见，动态规划思想的算法设计效率要远高于搜索算法。当然，动态规划思想 并不是任何时候都适用。它主要用于解决一定条件的最优策略问题。但是在实际 生活中类似问题却经常遇到，还有许多通过转化也可以变成类似问题。 9 湖北工业大学硕士学位论文 所谓一定条件，就是指状态必须能够满足最优化策略以及无后效性。无后效 性是指：某阶段的状态一经确定，则此后过程的演变不再受此前各状态及决策的 影响，也称之为“马尔可夫模型”。具体而言，若某个问题划分成多个阶段后，阶 段i 中的状态只能由阶段i + l 中的状态通过状态转移方程得来，与其他任何状态 没有关系，即满足无后效性。以图论的形式来看，若将问题中的状态定义为图的 项点，两个状态之间的转移定义为图的边，转移过程中的权值增量定义为边的权 值，则构成一个有向无环加权图，然后对图进行拓扑排序后就可以划分阶段。无 后效性的内涵就是无论状态出现在策略的任一位置，其地位均相同，均可实施同 样决策。 动态规划思想的其他特性：没有统一的标准模型、没有构造模型的通用方法、 没有判断一个问题能否构造动态规划模型的具体准则。在实际生活解决实际问题 只能具体问题具体分析，对症下药，构造问题模型。 2 2 2 算法模型研究 分治思想、去除冗余是动态规划思想的实质。分治策略在设计实际算法时经 常用到，其求解过程所需时间主要取决于分解后子问题的个数以及规模大小等因 素的影响。实际运用当中经常使用二分法，顾名思义：把原问题划分成两个子问 题，划分均匀、简单。最常用的是二分法检索和牛顿迭代法求方程的根。通常运 用分治策略寻求问题的解一般具有如下特点： ( 1 ) 原问题可划分成两个或两个以上的子问题，子问题的结构和求解方法与 原问题相同或相似； ( 2 ) 原问题进行分解时递归求解子问题，当子问题规模足够小时可直接求解； ( 3 ) 对于子问题的解可以通过某种方式构造原问题的解。 在分治策略中，由于子问题与原问题在结构和解法具有相似性，用分治法解 决问题时均采用了递归的方式。在时间复杂度为n l 0 9 2 “的排序方法中，堆排序、快 速排序、合并排序等都有分治思想。从数据结构角度来看，进行分治处理的过程 就是建树的过程。 动态规划思想与分治法类似的只是将原问题分解成若干个子问题，先求解子 问题，然后从子问题的解构造出原问题的解。与分治法不同的是，经分解的子问 题是相互关联的。若用分治法求解，容易造成重复计算。若可以保存已经解决的 子问题答案，在需要时再查找，这样就可以避免重复计算、节省时间，这个情况 正好符合动态规划思想的模式，它就是用一个表来记录所有已经求解子问题的答 案，在任何时候需要时都可以直接调用，避免重复计算。虽然动态规划思想的算 1 0 湖北工业大学硕士学位论文 法设计各式各样，但是填表方式却都是一致的。 动态规划思想的算法设计需要经历的步骤： ( 1 ) 原问题划分：根据问题的时间或空间特征，将其划分成若干阶段，并且 要注意划分后的阶段一定要是有序的或者是可排序的，否则问题无法求解。 ( 2 ) 确定状态及状态变量：将各阶段问题所处的不同客观情况用不同的状态 表述，确定状态变量，同时必须满足状态选择的无后效性。 ( 3 ) 确定决策及状态转移方程：决策和状态转移存在必然联系，状态转移是 根据前一阶段的状态和决策导出后一阶段的状态，因此决策一旦确定，状态转移 方程也就随之确定了。 ( 4 ) 确定边界条件：给出的状态转移方程仅仅只是一个递推方程式，还需要 根据实际问题确定一个递推的终止条件或是临界条件，否则程序无法终止。 ( 5 ) 程序设计 动态规划思想的算法设计求解步骤一般经过如下过程： ( 1 ) 找出最优解的性质，并描述其结构特征； ( 2 ) 递归地定义最优策略，构造出动态规划状态转移方程； ( 3 ) 以自底向上的方式计算出最优值； ( 4 ) 根据计算最优值时记录并保存的信息，构造出问题最优解。 如图2 1 所示。 图2 1 动态规划思想算法设计模式 湖北工业大学硕士学位论文 2 3 排课算法的设计 动态规划思想的算法设计其模型应结合实际问题进行构造，不是一成不变的。 在实际运用当中根据动态规划思想的最优化策略，并充分考虑应用的条件形成相 关的算法。 本文所研究的优先级自动排课算法就充分说明了这一点。首先，根据动态规 划思想将自动排课问题划分成确定时间和确定教室两个阶段，再将各个阶段所处 的客观情况用不同的状态表示出来，确定状态变量，同时，状态的选择满足无后 效性；然后，按照时间安排模式优先级选择最优时间，按照资源条件优先级选择 最优教室；最后，当出现时间、教室发生冲突时自动向上回溯到最近发生冲突的 一个任务单元，对其进行重新编排直到冲突不再出现为止。 根据实际算法的设计思路，可将其分成三个阶段并且每个阶段所使用的算法 各有不同。第一阶段，利用分治法完成自动排课两个子过程的处理；第二阶段， 在前一阶段的基础上，利用贪心法为每个子问题寻找局部最优化；第三阶段，排 课基本完成后，检查时间或教室重复所产生的冲突问题，利用回溯算法实现冲突 的局部调整。分治法和贪心法虽然易于利用，并且比较简单直观，但是发生冲突 后利用回溯法解决冲突就显得十分复杂。 首先简要介绍分治法、贪心法以及回溯法的原理： 一、分治法 它的基本思想以一个规模为n 的问题为例，首先将其分解为k 个规模较小的 子问题，这些子问题相互独立，同时又不脱离原问题；然后递归地解决这些子问 题；最后分析并有机合并子问题的解，从而构造出原问题的解【4 】。 二、贪心法 它有两个重要特征：一是贪心选择，二是最优子结构。贪心选择是指所求问 题的整体最优解可以通过一系列局部最优的选择来达到。它依靠不断的筛选寻求 个问题的解，它所做的任何选择都是当前状态下某种意义的最优选择，这就是 贪心选择法f 4 】。总是期望通过历次的贪心选择产生问题的一个最优解，虽然这种启 发式的策略并不总能奏效，但是往往在许多情况下能达到预期的目的【8 j 。贪心法思 想在排课问题中得到了充分利用，它能够逐步为当前任务单元寻找最优时间或是 最优教室，逐渐解决每个任务单元。 三、回溯法 回溯法俗称通用的解题法，它可以完成一个问题任一解的系统搜索，它还是 一个既带有系统性又带有跳跃性的搜索算法。它在包含所有解的解空间树中按照 1 2 湖北x - 业大学硕士学位论文 深度优先( d e p t hf i r s ts e a r c h ) 策略，从根结点出发搜索解空间树，算法搜索至解 空间树的任一结点时，先判断该结点是否肯定不包含问题的解，否则跳过对以该 结点为根的子树的系统搜索，