基于二叉知识树推理的可扩展智能排课系统

王运成，周春华，陈楚湘，吴善明，陈 冰

战略支援部队信息工程大学 信息作战指挥系，郑州450001

随着我国高等教育的快速发展，高等院校规模快速扩大，教师、教室、课程数量和需求大量增多，课程排列组合方案也成几何数级增加。以郑州信息科技学院为例，假如每天上课时段dno∈{1,2,…,5}，每周上课天数d∈{1,2,…,5}，每学期上课周数w∈{1,2,…,20}，教室数量r∈{1,2,…,150}，总学时数为N=12 000，则排课的规模为：

对于如此规模的问题，使得大学排课变成一项具有现实需求的复杂的系统工程。早在1976年，Even等人已经证明了此类问题本质上就是一个NP完全问题[1]。

当前，研究排课问题的算法主要有模拟人工手动排课算法、贪心算法、遗传算法、退火算法、回溯算法、蚁群算法和禁忌搜索求解排课算法等。其中，模拟人工手动排课算法更人性化，排课满意度较高，适合小规模教学单位排课；柴婷婷等研究了贪心排课算法[2]，算法运行效率高、空间复杂度低，然而其求局部最优解的前提是要找到正确的贪心思路和计算断点，贪心思路难找且断点选择存在缺陷，这给贪心算法在排课问题的使用带来了很大的困难；刘斌等提出了一种基于属性重要性的贪心算法[3]，改进算法解决了在无法判断断点的情况下，如何有效地区分断点，求得最小的断点集，但算法的复杂度大大增加，因此，对问题的求解提出了更高的要求；徐锦国基于遗传算法提出了排课算法[4]，它是一种全局优化算法，可进行并行分布处理，具有较强的鲁棒……