班级调度

Question

问题是这样的：

一所学校有不同的班级。每班有一个每周的时间表（英语8小时，数学6小时，艺术2小时等）。每个老师在班级中都有一定的小时数。 （我想学校几乎到处都是这样的）。

一些额外constraits可以加入，例如：

1. 老师X将不会在周一上班
2. 老师的Y某一类 等需要连续两小时。

目标是找到一个优化约束成本函数的计划。

最后，这是一个重要的NP问题，我猜。它可以使用空间状态搜索来解决（我们尝试所有可能的组合，使用一些聪明的搜索方式，并且我们选择可能的最佳解决方案）。

• 这可行吗？ （组合是巨大的，对于10个班级和每个班级30个小时，7个科目大约10^253，即使可能有一些实质性的修剪：我想SAT解决者可以处理类似的事情）。

• 即使近似，是否有任何替代项可以完成搜索？

Answer 1

这是一个 Constraint Satisfaction Problem。如链接所述，解决这些问题的方法之一是使用本地搜索方法，如min-conflicts或forward checking。您无法保证获得最佳解决方案，但您通常会在相对较短的时间内获得“良好”的解决方案。

如果您碰巧使用Prolog，clpfd库（有限域上的约束逻辑编程）功能非常强大。