论文部分内容阅读
时间表问题是典型的组合优化和NP完全问题，时间表的实际应用非常广泛。排课问题是时间表问题的一个典型实例，在研究领域中，排课问题常常是时间表问题的代名词。针对排课问题，许多学者分别用遗传算法、模拟退火算法、贪婪算法及多Agent协商等算法进行求解，各种算法都从不同的模型和求解方法上入手并取得了一定成效。
回答集程序设计是一种新的知识表示与推理的方法，同时也是一个用于问题求解的工具，高效的回答集求解器在求解其它NP完全问题上取得了很好的效果。本文采用了回答集求解器来实现对排课问题的求解，是一种全新的实现方式。首先使用回答集程序设计的方法来描述排课问题中的事实，规则和约束，然后利用高效的回答集求解器实现对排课问题的求解，最后在Linux系统下用JAVA语言实现用户界面，以取得和用户的良好交互。实验表明，这种实现方式能适应排课条件的变化，具有灵活和可扩展的特点，在可接受的时间内能排出教师满意度较高的课表。