计算课程表的算法（考虑限制条件）

Question

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

问题如下：考虑一所大学，你有以下对象： - 教职员工。每个职员教授一个或多个课程。 - 学生。每名学生参加一个或多个课程。 - 教室。教室可容纳一定数量的学生，并包含某些类型的设备。 - 课程。需要特定类型的设备，并且每周需要一定时间。

给定关于报名信息的信息（即每门课程中有多少名学生报名，并分配哪些工作人员来教授每门课程），如何计算遵守以下限制的时间表： 1. 工作人员一次只能教授一门课程。 2. 学生一次只能参加一门课程。 3. 教室一次只能容纳一定数量的学生。 4. 需要特定类型设备的课程只能在提供该类型设备的房间中举行。 5. 营业时间为周一至周五，上午8点至12点，下午1点至5点。

讨论： 实际上，我不太关心上述情况，我只是对这一类问题感到好奇。乍一看，这似乎是适合使用遗传算法的好题目，但是这种算法的适应函数将非常复杂。

在尝试解决这种约束满足问题时，有什么好方法呢？

我猜可能没有完美的解决方案，因为学生可能会选择一些课程组合，导致出现不可能的情况，特别是当学生和课程数量增加时。

- Thomi

Answer 1

留在遗传算法上，我认为这个适应度函数不会非常复杂，恰恰相反。

你基本上只需要检查每个约束条件（你只有5个）的候选解（无论编码方式如何），并对它们进行加权，以便当一个约束条件未被满足时，该权重将被添加到可以代表适应度的总分数中。

在这种情况下，你只需要最小化适应度函数（因为最佳适应度可能是0，意味着所有约束条件都得到满足），然后让遗传算法来计算数字。

编码需要一些思考，但一旦完成就应该很简单，除非我漏掉了什么，当然 :)

- JohnIdol

---

虽然只有5个限制条件，但可能有成千上万的学生、数百篇论文、数百个房间和数百名工作人员。检查所有这些约束条件之间的复杂性是问题的根源，我认为我们现在只是把它推迟了。 - Thomi

我的观点是，我不会仅仅因为适应度函数复杂就抛弃遗传算法，因为无论如何你都必须处理这种复杂性（通过利用给定的形式方法或其他方式），无论是否使用遗传算法。 - JohnIdol

Answer 2

这个问题的一个非常受限制的版本是NP完全问题。

考虑只有一个学生可以参加考试的情况。现在，对于给定的时间段（比如说整天都在考试），你可以构造一个三分图，其中包括教室、试卷和学生三部分，如果一个学生想要参加某张试卷，则试卷和学生之间连边；同时还需在试卷和可能使用该试卷的教室之间连边。

现在我们可以看到 三维匹配问题 是你所面临问题的一个实例：你需要为该特定时间段选择一个不重叠的（学生、试卷、教室）组合。

对于一般问题，你可能最好使用一些启发式方法。很抱歉我无法在此提供帮助。

希望对你有所帮助。

- Aryabhatta

---

我猜有些人不喜欢NP难问题 :-) - Aryabhatta