／ 开发案 ／
—————— ———————————————————————————————— —————————— —————————————————．———．——— —————————————————————————————————————． ——— ———．————————————————————．—————— —————————————————————————
基于贪婪算法的排课系统的探讨与实现
聂小东 ， 李振坤 ， 陈平华
（广东工业大学，广州５１００９０）
摘要：在实际项目案例中，针对开发排课系统难度较大，根据客户排课的实际需求，提出基于
贪婪算法．以资源匹配为基础，用内存动态分区分配的最佳适应法为依托进行研发。 关键词：贪婪算法；教学管理；排课
０ 引言
计算机排课系统的研究是当前各大高校数字化
教学改革中面临的一个比较突出的问题 笔者参加了
广东工业大学与深圳大学成人教育学院合作开发的
教学管理系统项目，负责排课系统的需求分析、设计
和实施等大量实际工作。在排课算法中运用了贪婪算
法．通过一系列的贪婪选择——当前状态下的最优选
择，逐步逼近给定的目标．以尽可能快地求得更好的
解 这样根据学校实际需求设计和实现系统．达到较
满意的效果
１ 项目案例概述
根据深圳大学成人教育学院的排课要求．采用手
动排课和自动排课相结合的排课方案．为了适应学分
制的要求．先预排课．确定上课时间．然后在网上公布
课程让学生进行选课．当选课完确定上课人数后再最 终排课，调整上课地点．让人数多的在大课室上课
在算法方面本文采取以下方案：
（１）融合Ｓｅｌｉｍ［ 】嘲【引和Ｌｏｏｔ 】 的思路，在对课程科
目进行处理时。先对已经指定时间的科目进行安排．
然后再对没有指定时间的科目进行处理：
（２）为了提高排课速度．并不一味追求结果的最
优化，而是基于贪婪算法，以资源匹配为基础。用内存
动态分区分配的最佳适应法为依托。把教室的可用资
２００７年第６期 （总第１０１期） 福建金融管理干部学院学报 Ｊｏｕｒｎａｌ ｏｆ ＦｕｊＪａｎ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｆｉｎａｎｃｉａｌ Ａｄｍｉｎｉｓｔｒａｔｏｒｓ Ｎｏ．６ ２００７ Ｓｅｒｉａｌ Ｎｏ．１０ｌ
贪婪算法在高校排课系统中的运用
曾光清 （福建金融职业技术学院，福建福州３５０００７） 擅要：贪婪算法在解决诸如排课等ＮＰ完全问题中具有实用价值。本文通过描述排课问题及其数学模型， 分析了基于优先级的贪婪算法在高校排课系统中的运用。利用该算法，既可以简化排课过程，缩短排课所花费 的时间，同时也能提高排课结果的满意度。 关键词：排课问题；教学模型；优先级；贪婪算法 中圈分类号：０２３ 文献标识码：＾ 文章编号：１００９－４７６８（２００７）１２－００４５－０５
一、引言 排课是高校教务管理中一项十分重要的工作。它直接关系到全校的教学工作能否有序地按计 划进行。同时，排课又是一项相当复杂的工作，其复杂性源于排课中资源约束条件和特殊要求对 有限时空目标的制约。随着我国教育体制改革的不断深入，高校办学规模连年扩大，在校学生人 数、教师人数、课程门类都显著增加，这对高校教务排课工作提出了更高的要求。研究开发一个 实用的排课系统具有十分重要的现实意义。 排课问题的本质是多维资源的冲突与争夺。它是一种典型的组合规划和目标不确定性调度问 题。早在２Ｏ世纪７Ｏ年代，美国人Ｓ・Ｅｖｅｎ等就证明了排课问题是一个ＮＰ完全问题，其算法的 时间复杂度呈指数增长。目前，除了使用“穷举法”获得近似最优解外，数学上还没有一个通用 的算法能获得ＮＰ完全问题的最优解。然而由于“穷举法”时问长，成本高，并无实际的应用价 值。因此，降低解决ＮＰ完全问题的算法复杂度便成为研究课题，即利用～个近似算法，建立一 个简约的模型，使解决问题的算法复杂度从指数增长简化为多项式增长，便于程序运行。在实际 的应用中，很多研究者都提出了各种解决排课问题的算法，包括遗传算法、动态规划法、回溯法、 模拟退火算法等，其中基于优先级的贪婪算法是一种简便有效的解决最优化问题的基本方法。根据 贪婪算法设计的排课系统，可以简化排课过程，在实际的运行中再通过少量的人工干预，在资源条 件充足的前提下，基本可以解决排课过程中的冲突和死锁问题，使排课系统具有实用价值。
np难问题常用算法
NP难问题是计算机科学中一个重要的概念，指的是一类问题，其解决方案的验证可以在多项式时间内完成，但要找到解决方案却需要非多项式时间。NP难问题常常需要借助一些特定的算法来解决，这些算法在计算复杂度上可能并不高，但在实际应用中却起到了至关重要的作用。下面将介绍一些常用的算法，用于解决NP难问题。
1. 贪婪算法（Greedy Algorithm）
贪婪算法是一种常用的近似算法，用于解决优化问题。它的基本思想是每一步都选择当前最优的解决方案，希望最终得到全局最优解。虽然贪婪算法不能保证得到最优解，但在一些问题中却表现良好，比如最小生成树问题、背包问题等。
2. 动态规划算法（Dynamic Programming）
动态规划算法通常用于解决具有重叠子问题和最优子结构性质的问题。其基本思想是将原问题分解为若干个子问题，先求解子问题，再利用子问题的解逐步推导出原问题的解。动态规划算法在解决NP难问题中有着重要的应用，比如最长公共子序列问题、背包问题等。
3. 分支定界算法（Branch and Bound Algorithm）
分支定界算法是一种用于解决组合优化问题的算法。它通过逐步分解问题，将问题空间划分为若干个子问题，再利用上下界信息剪枝，最终找到最优解。分支定界算法在解决NP难问题中有着广泛的应用，比如旅行商问题、背包问题等。
4. 遗传算法（Genetic Algorithm）
遗传算法是一种模拟生物进化过程的优化算法，用于解决复杂的组合优化问题。它通过模拟遗传、突变、选择等过程，逐步优化问题的解。遗传算法在解决NP难问题中有着独特的优势，比如图着色问题、旅行商问题等。 5. 模拟退火算法（Simulated Annealing Algorithm）
模拟退火算法是一种基于统计力学原理的全局优化算法，用于解决组合优化问题。它通过模拟固体退火过程，逐步降低系统能量，最终找到全局最优解。模拟退火算法在解决NP难问题中表现优异，比如图着色问题、背包问题等。
c语言算法--贪婪算法---0/1背包问题
在0 / 1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即n ?i=1pi xi 取得最大值。约束条件为n ?i =1wi xi≤c 和xi?[ 0 , 1 ]
( 1≤i≤n)。
在这个表达式中，需求出xt 的值。xi = 1表示物品i 装入背包中，xi =0 表示物品i 不装入背包。0 / 1背包问题是一个一般化的货箱装载问题，即每个货箱所获得的价值不同。货箱装载问题转化为背包问题的形式为：船作为背包，货箱作为可装入背包的物品。 例1-8 在杂货店比赛中你获得了第一名，奖品是一车免费杂货。店中有n 种不同的货物。规则规定从每种货物中最多只能拿一件，车子的容量为c，物品i 需占用wi 的空间，价值为pi 。你的目标是使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。这个问题可仿照0 / 1背包问题进行建模，其中车对应于背包，货物对应于物品。
0 / 1背包问题有好几种贪婪策略，每个贪婪策略都采用多步过程来完成背包的装入。在每一步过程中利用贪婪准则选择一个物品装入背包。一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=[100,10,10], p =[20,15,15],
c = 1 0 5。当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。
另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20],
