排课算法，以显示最佳匹配的标准？

Question

我希望创建一个系统，您可以输入课程(3-7课程)，你想在大学里，然后选择偏好(早上，白天，晚上，晚上/ M，T，W，TR，F)。

我需要一种方法，以便当程序查询数据库(MySQL)时，它返回根据这些参数制定的最佳可能计划。我是用php写的。

有人知道做这件事的最好方法吗？或者链接到一些我可以理解它的示例代码？

Answer 1

您可能想尝试一些约束编程( constraint programming，CSP)库...在CSP中，你陈述问题(通常是NP困难)，库使用一些启发式(模拟退火，禁忌搜索)或使用一些技巧(弧一致性，搜索空间削减)的穷举DFS来解决它。它可以解决数以千计的variables...but的鼻咽癌问题设置黑匣子系统的“精细”参数有点棘手……

Answer 2

它是NP完全的。

如果你想要一些简单和快速的东西，可以编写一个像First Fit Decreasing这样的构造启发式。简单地说，它根据难度对课程进行排序(学生人数，...)并在最好的剩余时间段和房间中一次分配一个。在PHP中可以很容易地做到这一点。

如果你想做正确的事情，就像@malejpavouk说的那样，使用CP库。它首先会使用启发式构造，然后像禁忌搜索，模拟退火，……Here's a open source course scheduling implementation in Java.寻找一个很好的metaheuristics CP库。

Answer 3

这是一个困难的优化问题。这是一个建议的启发式方法(具有随机跳跃)。

1. 获取一组约束(首选项)。
2. 和一系列课程。
3. 使用MySQL查询获取所选课程的可能时间。
4. 选择一组可行的课程。
5. 根据
6. 对该组课程进行评分。如果成绩足够好，请停止。否则，请在random.
7. return中将一个课程的学时更改为
8. 。