什么类型的算法可以用于课程表安排？

Question

是的，在stackoverflow上有许多类似的问题。我看到遗传算法是最常见的答案。

制作时间表：Making a timetable schedule和创建学校时间表的算法：Algorithm for creating a school timetable 但是，我担心遗传算法具有以下特点：

• 很难定义程序的终止条件
• 很难轻松地逃脱局部最大值

我希望该程序被推向冲突标准和不可能的解决方案太容易。

因此，我想要一种方法：

• 是果断的 - 保证达到接近最优的状态或者报告算法无法达到解决方案
• 可以同时考虑硬（不可侵犯）限制和软限制
• 优雅地接受用户输入的约束条件；如果用户输入无效，则可以将其添加到代码中而不会破坏它

共有100,000个详尽的时间表。

我搜索了一些信息，并发现元启发式算法，如模拟退火是一个不错的选择。动态规划算法怎么样？

对于这样的数据集，暴力方法可行吗？

有什么好的算法可以符合这些标准呢？

- Jesvin Jose

---

如果只有100,000个可能的时间表，那么直接使用暴力算法来检查所有时间表并不太难。当可能的时间表数量非常多（有时达到数十亿）时，通常会使用遗传算法或其他人工智能工具。对于100,000个可能的时间表输入，暴力解决方案不会花费太长时间，并且显然可以得到最优结果。 - amit

Answer 1

对于仅有 100,000 种可能性的 小输入，我建议采用简单的 暴力破解 解决方案：检查所有可能性，并选择最佳解。对于现代计算机来说，对 100,000 大小的输入运行评分函数并不难，很可能只需要几秒钟。

GA 和其他 AI 算法通常用于 更大 的输入 [数十亿甚至更多种可能性]，因此它们可能不是您的最佳解决方案。

与任何其他解决方案不同，暴力破解解决方案将确保您获得最优解，并在耗尽所有可能解时终止。

(*)注意：您可以通过在解决方案连续 k 步未改进时强制 随机重启 来修改 GA 和陡峭上升 爬山，以克服您提到的第二个问题 [逃避局部最大值]，但是 - 您将不知道每个点距离最优解有多近。

- amit

---

通过分支界定算法（Branch and Bound），可以改进蛮力搜索，通过放弃那些不可能比您已拥有的最佳解决方案更好的解决方案来提高搜索效率。 - DataWraith

100,000个可能性实际上非常少。如果您有10节课在2个房间的5个时间段内，您将有10,000,000,000个可能性。看看暴力破解是多么无用（也许Brand and Bound也是如此）。 - Geoffrey De Smet

@GeoffreyDeSmet：OP明确要求列举出少量可能性。虽然在一般情况下并不实用，但在这个具体问题中，暴力解法是最适合的。在OP指定的小数据集上使用GA或其他AI算法（如爬山算法）会过度设计，这是我的看法。 - amit