给定限制条件下计算时间表的算法

Question

我正在考虑一个假设性问题，并寻求有关如何从算法角度解决该问题的指导。

问题:

考虑一所大学。您有以下对象:

• 教职员工。每位工作人员教授一篇或多篇论文。
• 学生。每个学生拿一篇或多篇论文。
• 房间。房间可容纳一定数量的学生，并包含特定类型的设备。
• 论文。需要某种类型的设备，每周需要一定的时间。

根据有关注册的信息(即每篇论文注册了多少学生，以及分配给每篇论文的教职员工)，我如何计算遵守以下限制的时间表:

1. 员工一次只能教授一件事。
2. 学生一次只能参加一篇论文。
3. 房间只能容纳一定数量的学生。
4. 需要特定类型设备的论文只能在提供该类型设备的房间内举行。
5. 工作时间为周一至周五、8 点至 12 点和 1 点至 5 点。

讨论:

实际上，我并不太关心上面概述的情况 - 这是我很好奇的一般问题类别。乍一看，在我看来，它很适合遗传算法，但这种算法的适应度函数会非常复杂。

尝试解决此类约束满足问题的好方法是什么？

我想可能没有办法完美地解决这个问题，因为学生很可能会把论文组合起来导致不可能的情况，尤其是随着学生和论文数量的增长。

Answer 1

继续使用遗传算法，我认为适应度函数不会非常复杂，恰恰相反。

您基本上只需检查每个约束(您只有 5 个)的候选解决方案(无论编码如何)并为它们分配权重，以便在不满足约束时将权重添加到总分中代表健身。

在这种情况下，您只需最小化适应度函数(因为可能的最佳适应度为 0，这意味着满足所有约束条件)并让 GA 处理数字。

编码需要花点功夫，但一旦完成，它应该很简单，除非我遗漏了什么，当然 :)