（计算机软件与理论专业论文）一种基于概率动态分布选课算法的研究与应用.pdf

摘要 随着i n t e r n e t 的飞速发展和普及，在我国高校学分制的实行以 来，越来越广泛的要求学生进行自主选课，学生选课系统也从原始的 手工填表过渡到网络选课。本文在综合考虑以往的选课系统中主要应 用的算法的基础上，提出了一种对于选课学生来说相对公开、公平、 公正合理的选课算法基于概率动态分布选课算法。 该算法主要是以学生选课的公平性为出发点，所要解决的问题就 是要使得在整个选课过程中，绝大多数学生都能够在选课时间内尽可 能的拥有均等的概率选中某个课堂，同时尽可能的使参加选课的学生 在第一时间( 即实时性) 里得知是否选中。本文首先对已有的选课算 法进行了比较研究，随后对选课人数随时问的分布进行了分析，并进 行相关算法研究，按照选课样本的大小提出了相应的算法；最后综合 上述算法，提出了一种改进的基于概率动态分布的选课算法思想，使 得整个选课过程中，实时性与概率动态分布有了很好的结合与体现， 既实现了实时选课( 即时间效益得到保证) ，又能后使得参选人尽可 能的拥有相等的机会( 即实现选课过程中的公平合理性) 选中某个课 堂。 关键字：选课算法选课系统概率动态分布 a b s t r a c t w i t ht h ef a s td e v e l o p m e n ta n dg e n e r a l l yu s i n go ft h ei m e m e t ，t h e s t u d e m sa r ew i d e l yd e m a i l d e dt os e l e c tt h ec o u r s ei n d e d e n d e n n ya f t e r t h ec r e d i ts y s t e mi sp u ti np r a c t i c ei n l ec o l l e 2 e si nc h i n a t h e c o l l r s e s e l e c t i o ns y s t e mi s 仃a n s f 色r r e df o n nm a n n e df i l l i n gt a b l et o s e l e c t i n gm ec o u r s e si nt h e 、e b b a s e do nm em e m o d su s e di no t h e r c o l l r s e s e l e c t i o ns y s t e m s ，o i l c 虹n do fc o u r s e s e l e c t i o na l g o r i t l l mo nt l l e b a s eo fd y n a m i cp r o b a b i l i t yd i s t r i b u t i o n ，w h i c hc a nb em o r eo p e n ，m o r e e q u i t a b l e ，m o r cr a t i o n a lf o rm o s to f t h e 咖d e n t s ，i sp r o p o s e d t m sa l g o r i t h ms t a r t sf r o mt h ee q u i t yf o rt l l es t u d e n t st os e l e c tt h e c o u r s e s i tc a nm a k em o s to f 也es t u d e m sc a nc h o o s es o m ec o u r s e sw i t h a l m o s tt h es 锄ep m b a b i l i t y ，a i l dc a nm a k ea l lt l l es t u d e n t sc a nk n o wi f t h e yp i t c h e do n 也ec o u r s ei n 廿l et i m ea ss h o r ta sp o s s i b l e f i r s t l ym e a l g o r i t sp m p o s e db yo t l l e r sa r ec o m p a r e da i l ds t u d i e d 。t h e nt l l e d i s t r i b u t i o no ft h es t i l d e n t sd u r i n gm ep e r i o di sa 芏l a i y z e da n dt h e a l g o r i t h i ni sp m p o s e da c c o r d i n gt ot h es i z eo ft h et o t a ls t u d e n t ss a m p l e f i n a l l yb a s e do nt h er e s e a r c ha b o v e ，am o d i f i e dd y n 锄i cp r o b a b i l i t y d i s t r i b u t i o na l g o r i t h mi sp r o p o s e dt om e e t 恤e 1 er e a l t i m ea i l de q u i t y d e m a i l d0 ft l l ec o w s e s e l e c t i o ns y s t e m c o m p a r c d 、v i t hm ek r l o w n a l g o r i 血m s ，m i sa l g o r i t l l mc a np u ti np r a c t i c er e a l - t i m ec o u r s e s e l e c t i o n a tm es 咖et i m en l ea m i c i p a l _ o rc a ns e l e c tt 量1 ec o u r s ew i t ht h es 姗e p f o b a b i l i t y k e yw o r d s ：c o u 舟e _ s e k c t i o na i g o r i t h m c o u r s e - s e l e c t i o ns y s t e m d y n 墨m i cp r o b a b i l i t yd i s t r i b u t i o n 长春理工大学硕士学位论文源刨性声明 本人郑重声明：所呈交的硕士学位论文一种基于概率动态分布选 瀑冀法瀚硬究与建躅蹩本入在籀警羲舞翁攒鼯下，独立避行磺突工佟 所取得的成果。除文中已经注明引用舸内容外，本论文不包含任何其它 个人域攥体已经发懑或撰写的作晶成果。对举文的研究做出重要贡献的 令人帮檠薅，翡已在文中爨露璃方式标羲。本夫完全纛谈劐零声骧鹭法 律结粜由本人承担。 j 痒者签名必礁! i _ 年胃率爨 长卷璞工大学学僚论文驻投使爱爱毅攀 本学位论文撵学及指导教嫦糍垒了解“长嚣理工大学鞭士、博学 褪论文舨粳痿翔蕊宠”，露意长资瑷工大学操窝著商蓍家蠢美熬门或筑褥 送交学位论文的复印件和电子版，允许论文被套阅和借阅。本人授权长 春理工大学可以将本学位论文戆众部或部分邀密壤入鸯关数据库述嚣检 索，擞酉采瑶影臻、缩印或努撩等复裁手段深存帮茳编学靛论文。 、 作者签名：，：! l j 艺廷巫年袅一足尘醚 捂导导彝麓名瑙避碰年童一嚣毕器 第一章绪论 1 1 引言 本课题主要来源于长春理工大学计算机学院开发的高校教务教学 管理平台项目。该项目推出的是一整套能够适应新的教学体制、能够最 大程度满足高校现代管理要求的教务管理系统。在学生选课模块中需要 一个有效算法，在开发和实际应用中能够实现选课过程中的公平合理， 通过该教务管理系统的不断完善，使之能够服务于更多的高校。 选课系统是学分制教学改革的一个重要措施，它允许学生给自己安 排课程、时间以及任课教师，充分发挥学生的主观能动性，调动学生的 学习积极性，拓宽知识面，同时也在教师队伍中引进竞争机制，有利于 促进教学质量的提高。但是，在选课过程中，一方面由于师资、时间、 教室有限，而学生的选课往往又有很大的倾向性；另一方面学生对于选 课结果能否在最短时间内得到答案，这种需求也是不断在增加。 在以往的选课系统中，主要应用以下几种算法来实现：先来先服务 ( f c f s f i r s tc o m ef i r s ts e r v i c e ) 的算法、抽签算法和分志愿筛选 算法。但是这几种算法都存在很多不足之处：在先来先服务算法中，对 于参选数量较小的选修课来说这种算法的弊端还不是很明显，但随着学 校招生规模的扩大，参加选课人数的增加，使得排在后面的学生几乎没 有机会选到自己满意的课程，经常会给教务管理工作带来许多不必要的 麻烦，公平合理的进行选课这一原则得不到体现；而抽签算法的弊端在 于需要对整个学生选课操作结束后才进行后台处理，虽然有一定的公平 性，但是时间效益得不到保证；分志愿筛选算法是采用实时选课处理和 后台批处理相结合的方法来实现的，由于该算法是在所有学生选课结束 后，才进行后台处理的，这样虽然避免了先来先服务的不足，但当后台 处理完之后，仍有可能会有少量的学生3 个志愿都未选中，需要作一些 人工干预等处理，最终产生学生课程表，这种算法虽然一定程度上达到 了公平选课的要求，并且运行处理速度较快，但是，由于该算法仍需要 后台处理才能产生最终的学生课程表，并没有实现学生选课的实时处 理，以人为本的理念也没有得到完全体现。 总的来说，以往采用的选课机制对学生的选课要求不可能全部满 足，以人为本的理念根本得不到体现。鉴于这个原因，对学生选课是否 能够作到进行公开、公平、公正合理以及是否能够在最短时间内得到是 否选中某门课的问题都已经成为判定选课系统性能是否具有优越性的 一个重要指标。 在选课过程中我们采用的是基于概率动态分布的选课算法，可以根 据概率值和平均分布概率算法产生随机数的方法使在选课时间内所有 想选某个课堂的学生尽可能的拥有均等的概率选中该课堂，从而打破了 以前的那种先来先选中的不公平合理的选课机制。同时，根据随机数来 判断是否选中某个课擞并给出相应信息，w 以使参选的学生尽可能早的 焱第一薅阕里知道怒露逡串，瞧就是我嬲羧说懿算法邸时性。巍然，在 熬个逡潆结索嚣仍蠢砑缒存在少数学生选不主谋戆现象，蔫癸彀一些久 工干预等处理，产生最终的总课表。 总之，能够作到进行公开、公平、公难合理以及能够在最短时间内 得到是否选中某门课这些问题的解决便都能成为优化整个选课系统的 羹舞因素。 ，2 国内外袋究璃状 在我国高校学分制的实行以来，越来越广泛的要求学生翻主选课， 学生可以根据自己的窳际情况，通过选课来自由的安排自融的学习计 划，随着i n t e r n e t 的飞速发展和普及，举生选课系统也从原始的手工 填液过度到网络选谍，从最开始的雏形不断的走向成熟。目前器大高校 也簧遍开发了适应予爨蠢学校实际情况逡谍系统。 就嚣蓑嚣痰意授熬逸谖系统发震状掇来谤，营邃采震戳下冗穗葵 法；先来先服务( f c f s ) 的算法、抽签葬浚和分志愿筛选算法。在先来 先服务算法中，对于参选数量较小的选修课来说这种算法的弊端还不是 很明显，但随着学校招生规模的扩大，参加选课人数的增加，使得排在 聪砸的学生几乎没有机会选到自己满意的课程，经常会给教务管理工作 帮米许多不必要的麻烦。现在，许多高校逐步意识到了这个闷题，也采 敬了鞠应靛掊慈撼签算法，鞠在爨蠢学叟选漂络泰轰，辫予选漾天 数怒过限定久数静漾豢来说，采弱l 鑫签懿形式裁浃选中与否，缀然菜释 稷度上具有一定的公警性，但是这种算法的弊端在于需要对熬个学生选 课操作结束后才进行厥台处理，时间效益得不到保证。目前，又出现一 萃申采用实时选课处理和后台批处理相结合的分志愿筛选算法，该算法是 猩所有学生选课结束厩，才进行后台处理的，就避免了先来先服务的不 怒，也在一定程度上达到了公平选课的簧求，劳且运行处理速度较快。 熬楚，崮予该霎法仍爨要磊台楚理方熊产惫最终黎学生漂程袭，著浚套 实现学生逸课静实辩然理，以人为本的瀑念也没有褥囊完全体瑷。 总之，不管郦一种措施都将问题盼菜一方面作为侧重点采加以考虑 的。从大量的文献中，猩不同选课系统中愈，煦用有很多不同的选课算法， 例如；暨南大学，南京河海大学都采用类似填写高考志愿的方法使得选 课系统更加公平合理；桂林电子工业学院贝n 采用马尔可夫过瑕、烟台师 2 范学院则采用矩阵模型来确定选课人数。但是我们发现不管选课算法的 名称是多么的不同，其主要得选课思想不外乎以下几种算法的体现：先 来先服务( f c f s ) 的算法、抽签算法和分志愿筛选算法。现将其选课思 想分别总结如下： 先来先服务( f c f s ) 的算法：它的实现思想就是“排队买票”的办 法，是最简单的一种调度算法，这个算法也是在选课系统中最早应用得 一个很普遍得算法。现以3 0 0 学生选容纳2 0 0 人的某一课堂为例，在 3 0 0 学生中前2 0 0 人进行选课几乎都可以被选中，而后1 0 0 个想选这个 课堂的学生就不能选中。这个算法虽然在时间上可以有一定的时间效益 保证，但是严重的违背了高校中学生自主选课的原则，并不能够做到公 平合理的安排选课。 抽签算法：它的实现思想就是在整个选课过程中，学生先进行选课， 在髂个选课结束后进行后台处理来判断选中是否。当某个课堂的选课的 人数超过容纳人数时，就要对所有参加该课堂选课的学生进行抽签的方 式来决定最终的选课结果。这个算法虽然在原则上具有公平合理性，但 是在时间上却得不到保障，因为最终结果是在对整个学生选课操作结束 后才进行后台处理的。 分志愿筛选算法：在具体实现上，采取类似于高考录取的方法，由 学生在选课时确定3 个志愿，分级处理第l 志愿的优先级最高，最有可 能被选中如果课程第1 志愿已选人数大于限选人数，则不再处理第2 志愿，并将从第1 志愿中按照选课的优先权或通过抽签筛选出多余人员。 对于未选满的课程，进行第2 志愿的处理。处理完毕后，还有课程未满 且有落选人员，再进行第3 志愿处理。这样一来，落选机会少，分布均 匀，基本上做到了公平公。但是，由于该算法仍需要后台处理才能产生 最终的学生课程表，并没有实现学生选课的实时处理，以人为本的理念 也没有得到完全体现。 总而言之，不管是采用哪种思想的选课算法都不能将问题的全方面 来加以考虑的，对学生的选课要求都不可能全部满足，以人为本的理念 根本得不到体现。我们需要的是一种公开、公平、公正合理的选课算法。 1 3 本课题的研究内容 在长春理工大学计算机学院研究开发的高校教务教学管理平台这 个项目中，我们把选课模块里应用到的主要算法作为本论文的主要研究 内容： l 、理论上，进入选课页面后进行选课操作，系统会及时反映是否 选中并给出提示信息。对于可能存在一个课堂选择的人比较多的情况来 说，并不是每个人都能选中。此时系统会根据选择情况动态的更改当前 课堂的选择概率，用系统( 平均分布概率算法) 来确定随机数的产生； 运用概率动态分布方法与随机数相结合，判定课程选中与否并给予提 示，因此，并不是每次的选课都能选中。最后，系统通过“选修审核” 来判断选课是否通过，最终产生已选课程列表。 2 、实践上，我们主要选用完全面向对象的可视编程语言c # 作为开 发语言，采用的数据库是易于安装、使用和管理的m i c r o s o f ts q l s e v e r 2 0 0 0 数据库，我们同时还运用在断开连接的世界里可以进行操作 的a d 0 n 盯技术作为数据访问的方法来实现与m i c r o s o f ts q ls e v e r 2 0 0 0 数据库之间的数据访问，使整个选课系统更加利于开发设计与实现。通 过研究和总结，我们将上述的以数学中概率理论为基础的选课算法应用 于实践中，并对这种选课算法与其他的算法进行比较、归纳和总结。 总而言之，在整个选课过程中，我们所要做的就是使得每个学生都 能够在选课时间内尽可能的拥有均等的概率选中该课程，同时能够使参 加选课的学生尽可能的在第一时间里得知是否选中，使整个选课过程， 真正做到以人为本的理念，在时间效益得到保证的同时，公平合理的选 课原则得以体现。在以后的研究中我们将搜寻一种数学理论作为奠基， 以此来进一步优化选课算法，使算法更加公平合理。 4 第二章现有选课算法分析 2 1 选课系统分析 2 1 1 选课系统“1 概述 随着计算机技术和网络技术的发展，各高校相继建成了自己的校园 网，并充分利用校园网提供的新环境、新手段为学校的教学、科研和教 务管理服务。近年来，学校的招生规模不断扩大，在校学生人数明显增 多，加之学生分校区管理，给原本繁杂的院级选修课的人工选课工作增 加了不少教务工作量。网上选课系统”3 的推出，使得选修课程的设置维 护、学生选退课及成绩查询、任课教师的学生名单打印及成绩录入 统计等工作均能在互联网上完成。这不仅减轻了教务人员的工作负担， 也大大方便了全校师生对选课信息的维护、查询。 在高校教学管理的规范化、系统化以及计算机网络化的实施过程 中，网上选课系统已成为教学教务管理的关键部分。当前高等学校已从 学年制逐步向学分制。1 过渡。学分制重要的特点是只要学生按照选定专 业的培养计划修完规定的课程并获得相应的学分即可取得相应的学位 或学历，而对学习年限没有规定。实行学分制管理，学生可以在允许的 范围内选择适合自己需要的课程，有利于培养学生的个性化发展。 选课系统是学分制教学改革的一个重要措施，它允许学生给自己安 排课程、时间以及任课教师，充分发挥学生的主观能动性，调动学生的 学习积极性，拓宽知识面，同时也在教师队伍中引进竞争机制，有利于 促进教学质量的提高。但是，在选课过程中，一方面由于师资、时间、 教室有限，而学生的选课往往又有很大的倾向性；另一方面学生对于选 课结果能否在最段时间内得到答案，这种需求也是不断在增加。 2 1 2 选课系统中应用的主要技术 选课系统采用的是基于w e b 的三层c s ( 客户机服务器) 结构模型 ”。( 如图2 1 ) ，这种三层结构是在原二层c s 结构的基础上将服务器端 进一步分解成一个应用服务器( w e b 服务器) 和一个数据库服务器：浏览 器用于接收用户输入并显示从w e b 服务器返回的信息；w e b 服务器用于接 收从浏览器传来的用户信息，向数据库服务器提出操作请求并将操作结 果返回给浏览器；数据库服务器主要完成数据的定义、查询和更新等操 作，并维护数据的安全性和完整性。 客户机 浏览器 ： 基于w e b 应用的服务器 ： l 数据艨鼹务器s 瓯s e r v e r 图2 ，l 三层c s 结构模型 选用这样懿缕枣冬模型主婺滋于以下凡方疆魏考虑：( 1 ) 选谍系绕怒 瑟翔全校繇生懿，蠢三屠c s 结构对客户淹没有将豫蠡孽爨求，疆户廷霭 在任何一台能上网的计算机上操作就行。( 2 ) 系统的应用逻辑需要调熬 时，只要对w e b 服务器进行升级，对客户端和数据库服务器几乎没有影 响，这保证了选课系统的可维护性。( 3 ) 数据库服务器可根据具体嚣骚 瑟霪爨一台或多套镌理爨务潞土，在数爨爨不大嚣，慧楚可戳与b 缀 务器台堵一台主祝( 目前本系统帮采用这样的方案) ，这不仅提高了系统 的执行效率，也增加了系统的安全性和灵活性。 在选课过程中，主要选用究全面向对象的可视编程谱畜c # 作为开发 谗富”“，采用熬数据疼是翳予安装、搜瘸纛管理的麓i e r o s o f ts 熊 s e v e r 2 o 数据艨，我稍阅嚣窖还运用在辩稽连接懿邀彝鬃可 美迸幸亍攥作 的a d o n e t 技术作为数据访问的方法来实现与m i c r o s o f ts 0 l s e v e r 2 0 0 0 数据库之间的数据访问，使整个选课系统更加利于开发设计 与实现： l 。e 舞程葶潞鸯楚一稳由漆 孛驱交戆、完全嚣彝簿象瓣哥视缓程语言 “”，程序用一个i d e ( 集成开发环境) 来创建。它汲取了c ，c + + 的很多 优点，通过i d e ，程序员可以方便的创建、运行、测试和调试c # 程序。 有了i d e ，将大大缩短创建一个能实际运行的程序所需的时间。而用i a v a 瑕疹语言编程，爨然饯玛黪逡嚣速度毙较快，占有系绫瓷添魄较少纛薤 怒弼戳跨平台滋行操作，毽怒在运行时篱溪有一个虚羧机j 硼( j a v a v i r t u a lm a c h i n o ) 对其代码溅行解释，再加上对j a v a 的学习比较复杂和 开发周期比较长，所以我们选用c # 程序语言作为编程语京。 2 ，凇e r o s o f ts 旺s e v e r 2 o 是一季申典溅的具有客户聿j 服务器体系 6 架构的关系数据库管理系统，它使用t r a n s a c t s q l 语句在服务器和客户 机之间传送请求和回应。m i c r o s o f ts q ls e v e r 具有可靠性、可伸缩性、 可管理性、可用性等特点，为用户提供了完整的数据库解决方案。从工 具软件方面讲，m i c r o s o f ts q ls e v e r 2 0 0 0 数据库较易于安装、使用和 管理，即为“操作简单”，这也是一个减少成本的关键因素。s q ls e r v e r 与w i n d o w s 操作系统无缝集成，m i c r o s o f t 公司总是尽可能将所有的软 件功能捆扎在一起，除非用户还需要其他用处的操作软件包，否则功能 已足够使用了。 3 a d o n e t 是一种全新的数据访问方法“，是m i c r o s o f t 推出的一种 数据访问技术。a d 0 n e t 适用于使用连接的以及断开连接的i n t e r n e t 世 界。就a d 0 n e t 而言，其性能与价格成正比，价格比较合理，它充分利 用了托管数据提供者，从而提高了应用程序的总体速度和性能。此外 a d o n e t 还可同时在使用连接的和断开连接的环境中工作：在连接状态 时，用户可以直接连接到数据库，在读取数据的同时保持与数据库的连 接；在断开连接的世界里，a d o n e t 通过把数据访问这个方面的问题移 到断开连接模型上，把希望编辑或修改的数据从服务器发送到客户，在 客户机上进行本地缓存，然后可以在客户机上进行编辑，在更新数据库 时，可以把数据发回到服务器，从而可为我们解决任何冲突。在a d o n e t 中，读取数据时，使用被称为d a t a r e a d e r 的对象。编辑和更新处理断 开连接的数据时，在d a t a s e t 关系数据结构中本地缓存数据，d a t a s e t 可以在内存缓存中以表格地形式保存大量数据( d a t a t a b l e 对象) ，它 们地关系( d a t a r e l a t i o n 对象) 和约束条件，接着，可以把它们导出 到外部文件或者另一个d a t a s e t 对象。 2 2 现有选课算法分析 学分制允许学生跨系、跨专业、跨年级选课，学生也可以自由选择 上课时间和自己喜欢的教师。但教学资源有限不能满足所有学生的修读 要求，因此需要有选课条件来限制学生选课，即对部分课程设定一些限 制条件或优先条件。对选课人数超过预定的开课人数的教学班要进行筛 选，目前培养计划中学生修读的课程大致分为公共基础课、学科基础课、 专业必修课、专业选修课、全院综合选修课等5 大类。对于不同类的课 程应用不同的算法进行筛选，下面分析几种常用的选课系统的公平算 法： 2 2 1 先来先服努( f c f s ) 的冀法 先来先服务( f c f s ) 的算法“：它的实蕊思想就是“摊队买票”的 办法，是最简单的种调度算法，这个算法也是在选课系统中最早应用 得一个很普遍得算法。 舞法滚程鳃躅2 + 2 瑟示： 图2 2 兔来先服务( f e 鹳) 静算法 这种算法虽然实行比较容易，在时间上也有一定的时间效益保证， 健憝只要选课的澡堂人数已满，对后面任何参照选课的学生来说都没蠢 瓿会选择这f j 谦疆。铡魏：鸯3 0 0 学生参热容辅2 0 0 夫瓣深堂选漾，巍 3 0 0 学生中前2 0 0 入迸行选课几乎都可以被选中，而后1 0 0 个想选这个 课堂的学生就不能选中。这严嫩的违背了掰校中学生自主选课的原则， 并不能够做到公平食理的安排选课。 8 2 2 2 抽签算法 抽签算法o ：它的实现思想就是在整个选课过程中，学生先进行选 课，在整个选课结束后进行后台处理来判断选中是否。当某个课堂的选 课的人数超过容纳人数时，就要对所有参加该课堂选课的学生进行抽签 的方式来决定最终的选课结果。 在抽签算法里，应用抽签的方式“”也很多，主要有随机抽取、按权 重高低抽取和各种优先排列抽取等。 用随机抽取方式的抽签算法，我们仍用3 0 0 学生参加容纳2 0 0 人的 课堂选课为例子作以说明，用抽签算法的思维就是在3 0 0 名学生选课之 后，进行随机抽签的方式来抽出2 0 0 人作为这门课的最终选中名单。 按权重高低抽取方式的抽签算法“”比较简单，就是要求学生在选修 每门课程时投入一定权重分。权重分越高则选中的机率越大，但学生的 每学期权重分总数基本相同。 算法流程图如下所示： 图2 3 按权重高低算法 目前有的高校还应用专业优先算法和成绩优先算法“7 1 等各种优先 排列抽取方式的抽签算法，其中专业优先的算法比较适用专业选修课的 数据处理；成绩优先也就是在前台选课结束后，对选课人数大于预置人 数的课程进行筛选，即将已选某门课程学生的学分积按降序排列，由高 9 分刭低分筛选，从中选出一定数量的学生。现以专业优先算法为例，流 襁如下图所示： 1 0 图2 4 专业优先算法 这个算法虽然在原则上具有公平合理性，但是在时间上却得不到保 障，因为最终结果是在对整个学生选课操作结束后才进行后台处理的。 2 2 3 分志愿筛选算法“” 此算法用于同一门课程有多个课堂的情况下，学生可有几个优先级 不同的志愿，最多为3 个。计算机按不同的志愿进行处理，首先满足第 一志愿，若第一志愿的人数超过最大上课人数，则采用平均分布概率算 法进一步处理，筛选出多余的人数，不再处理第二志愿。若第一志愿的 人数小于总人数，全部选中。当第一志愿遍历一遍后，再遍历第二志愿； 并将第一志愿该课堂不足的人数作为第二志愿的最大可选人数。处理方 法同第一志愿，以此类推。第一志愿优先级最高、机会最大，最有可能 选中。第二志愿处理对象为：第一志愿处理后该课堂所剩可选人数( m 2 ) 及该课堂的第二志愿所有人数( n 2 ) ，若n 2 m 2 ，则全部选中，否则处理 类似第一志愿，第三志愿处理方法同第二志愿。 处理流程如图： 图2 5 平均分布概率处理流程 1 l 图2 6 第一志愿处理流程 此算法是采用实时选课处理和后台批处理相结合的方法来实现的。 由于该算法是在所有学生选课结束后，才进行后台处理的，这样就避免 了先来先服务的不足。当后台处理完之后，有可能会有少量的学生3 个 志愿都未选中，需要作一些人工干预等处理，最终产生学生课程表。在 经过一段时间的使用后，发现分级筛选算法能够实现公平选课的要求， 并且运行处理速度较快，是性能较为优越的选课算法。但是，由于该算 法仍需要后台处理才能产生最终的学生课程表，并没有实现学生选课的 实时处理，以人为本的理念也没有得到完全体现。 2 2 4 一种基于线性不等式组的选课模型。2 选课是大学学习的重要组成部分。如何合理的选课，不但是学生顺 利完成学业的必要条件，而且可避免在学习过程中前序课和后继课之间 的矛盾。一般情况下，可供选择的课程有许多，每门课程都能使学生在 某些方面获得知识，然而，针对某个学生而言，选择适合自己的课程受 到各方面的限制。现在抛开学生本身的素质( 学习能力、学习兴趣) ，也 忽略课程的难易程度，仅仅考虑在现有资源下，组建有限门课程可选性 的数学模型”，通过求解这个数学模型，现以给出计算机学院某个学期 的计算机类课程可选方案为例，从结果分析该模型的合理性和实际意 义。然而在实际学习过程中，学生则必须结合自身情况，选择最适合自 己的一套方案。 l 、数学模型的建立 1 ) 决策变量的选取 由于课程之间的不可分性，以某门课程x - 为决策变量，其取舍只存 在两种情况：选修和不选修，数学表达式为 i = 1 该课程被选修 i = 0 该课程被拒绝 所以该问题的决策变量只能取o 或1 。 2 ) 指定条件 根据国家的有关规定和学校的培养计划，由于某些课程是学习其他 相关后续课程的基础，如果缺少对它的学习，那么后继课程将无法继续 进行( 比如理工类高等数学) ，因而被直接指定为必修课( 必选) ，用 数学语言描述为 _ 2 1 ，7 2 1 ，2 ，珂j 其中n 为开设课程的总数。 3 ) 相互依存关系 从知识结构来讲，学习是一种系统性的社会活动，课程之间是紧密 联系、环环相扣的，如果前期末学习某门或某些课程，那么后期与之属 于同一个系统的相关课程就不能选修，即后续课的学习是以前期课学习 为基础，两者之间存在依存关系。它们之间应该满足逻辑关系式： t = l jx j = 1 ( f ，) 4 ) 学分限制 健全的系统具有条理性和合理性的特点，在学生的实际学习过程 中，必须形成一个完整地封闭系统。无论是从遵循学校的培养计划，还 是从自己将来的发展方向来讲，都有一定的限度，即要形成完整的知识 结构，必须取得一定的学分。在有限的课程中选择一门课，意味着可能 要放弃其他可选课，但同时要能够完成一定的学分。即 y ，x 6 其中t ，表示第f 门课程的规定学分，6 为学校规定该学期 省 内必须完成的最低学分。 5 ) 上界条件 从式争t ，6 可以看出，学生要达到学分要求，选足够多的课程 磊 就行。然而在实际学习中，它们之间存在一定的上界约束关系，即考虑 到学生的承受能力，学校必须控制学生在本期内选课的上限，即 y x ，口其中d 为该学期内最多能选举的课程门数。 材 6 ) 互斥条件 系统各嚣素之阙不是一些零教部终瓣罐舔，焉是互衽铡豹瓣，也就 怒说，菜些课程之阉簸多哭笺遥释其一。根据教学诗翔鹣安穰 ，这些谋 程是同时开课的，由于上课时间发生冲突，势必造成这些谍程不能同时 选学，表述为数学中的互斥关系，其袭遮式为 x 女+ x f = 1( 七毋，) 7 ) 自有条件 缓设只考惑叛上主要霞素，霹逡谖过程中磋到豹英恁瓣素( 客震蕺 主管原透) 不予瑷考虑，耽鲡课程是否开设，学生是否寿兴趣瑷及学生 怒否愿意选该老师所任的课等等。 定义指标集，= 1 ，2 。 ，w2 舱，弹，f ，。话，。 综合上述讨论，其数学模型为： 惫。t 矗 f e 如 t 墨d f e j n x 口= lp j 羔；= x j ，歹) 静 z 女+ 一l 如，) w x ，= o 或1 f 2 、模型的求解 1 ) 决策变量约柬矩阵 该线性不等式组属于o 一1 线性不等式组，其解法很多，对予规模较 小问题我们采用隐戏枚举鲍方法。出决策变量的系数构成约束矩阵，根 1 4 据决策变量为o 或l 的情况进行判断。由于计算机不能识别课程之间的约 束，约束的判定必须人工进行。因此，约束条件主要采用人机交互式输 天，一定程度上悫壤热了掇侔人受翡主动蛙翻灵活性。 2 ) 选谦实铡横瓣 现以计算机学院某个学期的计算机类课程w 选方案为例，学分要不 低于3 0 学分，最多只能选1 0 门课程，其课程设鼹和学分如表所示： 表2 一l 漂程没釜嚣学势设嚣 上述条 牛中，我们设定课程4 、5 、9 、l o 棚嚣依存，课瑕1 5 、1 6 、 1 8 程互辕存；课程5 、? 、8 、l l 夏蓐，| 2 、1 3 、l 垂、1 7 互斥。 用詹，表示第f 门谦程的学分，那么数学模烈如下： l s 女，一3 0 j 玷 ( 蒽学分控制) x 4 = l 冷砘= l 砖= l 潞南= l屯= l 等_ o = l ( 互存条件) 鼍，= l ：辛x 体然l工f s = l = x 1 8 = 1 而= 并2 = 屯= l ( 必修条件) 屯+ 砖+ 十x | l # l墨2 + x 1 3 + 篁l + 7 = l ( 聂斥条传) ( 课程数目控制) 将上述不等式缝避行优亿得到的结果如下图表所承： 褒2 2 不等式爨遴符後纯缝莱 ( 选择控制) 选课方案所得学分 l ，2 ，3 ，4 ，基雏1 9 ，1 2 ( 1 影l 彰1 7 ) ，1 5 l ，2 ，3 ，4 ，5 ，6 ，9 ，1 0 ，1 5 ，1 6 ( 1 8 ) 1 ，2 ，3 ，4 5 ，9 ，1 0 ，1 2 ( 1 3 1 4 1 7 ) ，1 5 ，1 6 ( 1 8 ) l ，2 ，3 ，4 ，5 ( 影影王圭) ，承1 2 ( 1 影i 影l ) ，1 5 ，l & 1 8 1 ，2 ，3 ，4 ，5 ( 7 8 1 1 ) ，乱1 2 ( 1 3 1 4 1 7 ) ，l 甄1 6 ，掩 l ，2 ，3 ，4 | 9 ，1 2 l 影l 影1 7 ) ，l 磊l 趣1 8 3 l 3 1 3 c 1 5 熬5 胬 没；其中5 ( 7 8 1 1 ) 表示在该方案中，即可以选择课程编号为5 豹谍稷，迄霹选择编譬必7 、8 绫ll 戆谍程，英德夔蔹次类推。 3 、结熙分析 从上述优化结果可以得到以下结论： ( i ) 霹镶攀生选择豹方寨有5 0 秘，劳慧每一耱方案鬈缓逡箨l e 门 或9 门课程，也就是说不会发生某位同学选择很少的几门课就可以取褥 规定的学分，这符合均衡的目标； ( 2 ) 掰霉霉攀分綦本撩等，楚舅瞧不会过大，群扶攀铰懿角度来漭， 1 6 沁 嫒酚删 规章制度对每个人都是公平的： ( 3 ) 结果还反映了数学基础课的培养计划。结果显示选修课程4 古主导地位，表明了学院以算法为主要学科的学科建设计划。 因此选课模型不但给学生提供了选课方案，同时反映学校课程设置 的一些侧重点，有推广的价值。然而上述模型也存在着不足： ( 1 ) 问题规模小，有待于考虑全校的选课情况； ( 2 ) 只考虑课程的相互依存，而忽略了学生在学习过程中的半途 而废，如数学建模入门和最优化计算方法修完之后而放弃数学建模实践 的学习。 通过上述分析看到，基于线性不等式组的选课模型合理可行，并且 课程门数、学分等具有可调节性，实例有效的解决了学校基础课的选课 问题。 2 3 本章小结 在选课过程中不管是采用哪种思想的选课算法都不能将问题的全方 面来加以考虑的，对学生的选课要求都不可能全部满足，以人为本的理 念根本得不到体现。我们需要的是一种公开、公平、公正合理的选课算 法。 先来先服务这种算法虽然实行比较容易，在时间上也有一定的时间 效益保证，但是只要选课的课堂人数已满，对后面任何参加选课的学生 来说都没有机会选择这门课程。这严重的违背了高校中学生自主选课的 原则，并不能够做到公平合理的安排选课。 就抽签算法而言，这个算法虽然在原则上具有公平合理性，但是在 时间上却得不到保障，因为最终结果是在对整个学生选课操作结束后才 进行后台处理的。 分志愿筛选算法是采用实时选课处理和后台批处理相结合的方法 来实现的。由于该算法是在所有学生选课结束后，才进行后台处理的， 这样就避免了先来先服务的不足。但是，由于该算法是与后台批处理相 结合才能产生最终的学生谋程表，并没有实现学生选课的实时处理，以 人为本的理念也没有得到完全体现。 对于基于线性不等式组的选课模型来说，虽然对于问题规模较小的 选课范围来说有着一定意义，但是这种选课模型只是在学生选课时提供 了不同的选课方案，具有一定参考价值，而在实际的选课过程中并没有 解决使得每个学生都能够在选课时间内尽可能的拥有均等的概率选中 某个课堂和使参加选课的学生尽可能早的得知是否选中这一核心问题。 总而言之，我们所需要的选课算法应该是尽可能的使得每个学生都 能够在选课时间内尽可能的拥有均等的概率选中该课程，同时又能够使 参加选课的学生尽可能早的得知娥甭选中。我们需要在整个选课过程 孛，在辩趣效益褥到绦涯熬霹对，公乎合理静逡谍琢萋| j 尽可戆熬褥激髂 现。 1 8 第三耄基予概率动态分布选课算法 3 1 基于概率动态分布选课算法的提出 要实现实时选课，使得繇个学生都能够在选课时间内尽可能的拥商 均等的概率选中该课程，同时能够使参加选课的学生尽可能的在第一时 间罩得知是否选中，真正做剜以人为本的理念，我们提出了基于概率幼 态分布的选课算法，使得时间效菔得到保证的同时，公平合理的选课艨 则也能够得以体现，真正做到公开、公正、公平。而这种算法中概率选 取的是否得当是决定整个算法优越性的关键因素。 为了在选课过程中实现公开、公正、公平，并且满足课程安排的鼗 求，在选课的过程中，需要隧瓣根据实际情况对每个想选该课程的人途 中静凝奉送行诞整。在整个逡漾过程孛，如果参选人数小于或等于掰选 课堂窖缓夔夭鼗，那么全部德孛。孬粥，我鞠藏要采矮稳应翡算法寒鼹 选漂蓬程送行控割。当憨逡该漾程豹久数过多薅，要簿低选孛赘凝攀， 以便绘螽选豹入蜜出适当静梳会，警想选该课程豹入数过少时，簧摄辩 选中的概率，使选中该谖程的人数能够满足开课要求。这样在选课的避 程中就要运用动态概率分稚的方法，随时调整选中课程的概率，从而实 现公平合理的选课原则。 3 2 基于概率动态分布选课算法的实现 3 2 1 选谋人数分布预测 在选漂过程中，如栗能够怼憨熙选课籁舞凌遥漂天数随时闻静分凑 终窭难碜颈溺，郡么我爨黢霹以辩蘩往嚣霹肉邃孛谈涤程翡入数逡 爹按 裁，驮覆实理不同时裁参选入逡争该瀑程瓣辊会基本一致，豫 蠹逸漾豹 公平往。及现有资料来番，途漾避程开始爱单位对闻蠹参翻选漂静人数 随时闯平稳变纯，具有嘲驻魏舰镣性，可以利用某些函数来拟合这种规 律性的变化。 l 、参选人数随时间对应分布的曲线拟合 在科学研究与其他许多实际问题中，常常有函数不便于处理或计算 1 9 的情形。有时候函数关系没有明显的解析表达式，需要根据实验观测或 其他方法来确定与自变量的某些值相对应的函数值”；有时函数虽然有 明显的解析表达式，但是使用很不方便。因此，我们希望对这些问题中 的函数建立一个简单的便于计算和处理的近似表达式，即用一个简单的 函数来近似代替复杂的函数。近似代替有叫做逼近。所谓简单函数，一 般指可以用四则运算进行计算的函数，例如多项式、有理分式等。 逼近的方式可以是多种多样的，可以根据问题的性质与要求来选 择。当然，我们所提出的对逼近方式的要求必须合理，这样才能有确定 的解答，不恰当的要求会导致问题无解或解不唯一。在解为唯一的前提 下，还必须考虑求解的方便性。常用的逼近方式有：插值、一致逼近、 均方逼近等。 插值法就是根据函数f ( x ) 已有的数据表格来计算f ( x ) 在一些新的 点x 处的函数值，但是它只能是在给定的函数表中间插入一些所需要的 新的函数值，无法对以后的函数值进行预测；一致逼近与均方逼近解决 问题时，函数f ( x ) 都是在区间 a ，b 上考虑的，如果对于给定函数f ( x ) 在一些离散点xo ，x ，x 一( 各x ，互不相同) 处考虑其逼近问题，则称 之为曲线拟合。 显然，曲线拟合问题与函数插值问题不同，它不要求曲线通过所有 已知点，只要求得出的近似函数能反映数据的基本关系。因此，曲线拟 合的过程比插值过程得到的结果更能反映客观实际。在对给出的观测数 据( x ，y ) ( f _ 0 ，l ，2 ，n ) 作拟合曲线时，怎样才算“拟合的最 好”呢? 一般总是希望使观测数据与拟合瞌线的偏差的平方和最小，这 样就能使拟合曲线更接近于真实函数。这个原理称之为最小二乘原理。 用最小二乘原理作为衡量“曲线拟合优劣”的准则称之为曲线拟合的最 小二乘法。 我们采用适用于一般函数拟合问题的多项式拟合。考虑一个m 次多 项式 m y ( x ) 2ao + a l x + a 2 x 2 + + a 。x “= 口j x ， ( 1 ) = 0 来拟合n 个观测数据点 其中m 远小于n 。 做误差的平方和 n f 瓴，d ，口卅) = y ( 坼) 一儿】2 = l 再分别对ao ，a l i “，a m 求偏导数，并使之为零，得 若2z 争吼州- o ，j = o ，卜”，m 弧 n + 口i + + x ? 一y t m 2 0 女；l 亦即系数ao ，a ，a m 应满足如下方程组 月nn月 口。x ! + 口。x f “+ + 辟。x f + ”= y 。x f * 1 女= l 2 = it = 1 由于方程组( 2 ) 的系数矩阵是一个对称矩阵，并且是正定的。由 此可以唯一的解出ao ，a - ，a m ，然后带入m 次多项式( 1 ) 便可以得 到由观测点所确定的近似多项式。 由于高次多项式的拟合会引起数值的不稳定，在工程中没有实用价 值。所以在此我们试用三参数二次多项式和四参数三次多项式来拟合选 谋过程中的参选人数随时间的对应分布情况。 具体图表如下： 时间( 秒) 图3 1 参选人数随时间的对应分布情况一 一翻 加鲫舯蚰加加0 一 o ，有： ! 鳃尸慨斗s ) = ， 伯努利大数定理表明事件发生的频率”“加依概率收敛于事件的概 率p 。这个定理以严格的数学形式表达了频率的稳定性。就是说当一很 大时，事件发生的频率与概率有较大差别的可能性很小。有实际推断原 理，在实际应用中，当实验次数很大时，便可以用事件发生的频率来代 替事件的概率。 由调查统计表明，在选课过程中，参加选课的人数比较多