[00043872]一种在多约束条件下高效分班、排课的方法
联系人： 贾永鑫
所在地：甘肃 武威市
- 服务承诺
- 产权明晰
-
资料保密
对所交付的所有资料进行保密
- 如实描述
技术详细介绍
1975年，S.Even等人论证了课程表问题是NP完全问题。由于课程表问题所涉及的信息较多，并且求解课程表问题最优解的时间复杂性是课程表规模的指数级，所以一般采用求近似最优解的算法。在具体工作应用中，人们只是要一个满足各种条件的近似最优解，或者说满意解。因此，对于课程表问题，关键不是如何找到最优解，而是如何提高解的满意度。
传统的人工排课，工作量巨大，最令人担心的就是出现教师资源冲突或场地资源冲突的问题，尤其是规模较大的中学排课时出现的问题更多。现有解决排课问题的方法主要是回溯法和遗传算法，其中回溯算法是所有搜索算法中最基本的一种算法，其采用一种走不通就返回的思想作为其控制结构，采用了先根遍历的方法来构造解答树，用于找解或所有解以及最优解；回溯算法对空间的消耗较少，当其与分枝定界法一起使用时，所求解在解答树中层次较深的问题有较好的效果，但在后继节点可能与前继节点相同的问题中使用，会产生循环。回溯法是一种穷举的办法，空间消耗虽然小，时间消耗却非常大，时间收敛慢，有时可能将好的课表错过。遗传算法从代表问题可能潜在解集的一个种群开始，在每一代，根据问题域中个体的适应度大小挑选个体，并借助代表于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程导致种群像自然进化一样，后生代种群比前代更加适应环境，末代种群中最优个体经过解码，可以作为问题的近似最优解。用遗传算法排课空间消耗大，其随机产生很多课表之后根据条件检查，不符合条件的放弃，留下来的再模仿遗传做随机改动，直到完成任务；其模拟自然选择和遗传，即优胜劣汰、适者生存，并没有主动依据条件生成课表，存在一定的盲目性，这也必然导致大量时间的浪费。
选修课排课解决方案，特别是学分制中学生自由选课后的排课问题没有办法解决。尽管目前有许多关于排课算法的研究,但是仍然没有一个能够被普遍接受的最优解决方案。各省新课程管理平台（b/s）中有选课模块，唯独缺少排课模块。针对现有技术中存在的技术缺陷，研究一种可在多个约束条件下，能够节省空间和时间，有明确目的，可主动的快速合理实现分班、排课任务的方法。技术模拟人工排课的方式开发，算法接近遗传算法，又不完全是遗传算法，与遗传算法相同的一点是“适者生存和优胜劣汰的原理”。
