高效排课算法

Question

我被要求编写一个程序，确定给定日期各个人员的工作地点。例如，输入可能是：
4-6pm，A场地
1-2pm，B场地
9-11am和2-4pm A场地

基本上可以有许多场地，人们可以在多个时间段工作。我感觉这种问题早就解决了，所以我希望有人能指引我找到一种优雅的解决方案，而不是重新发明轮子。

编辑：阅读类似的问题，我感觉这个问题可能是NP完全问题。我不需要最高效的解决方案，只需要能够运行并且相对可靠的解决方案。

编辑2：为了澄清，输出应该是一个时间表，其中分配了人员，使得间隙（没有人工作的情况）尽可能小。

- Chris

---

问题描述只定义了输入，没有说明程序需要解决什么问题。这里需要什么样的优化？ - Boris Pavlović

@Boris，对于这个行业的人来说，输入足以理解问题 :-) - Patrick

Answer 1

看起来你正在尝试解决一些需要专业软件应用的问题。如果你的问题足够小，可以尝试像这样采用蛮力方法：

- 确定你的问题的粒度。例如，如果是为了学校的时间表，你的粒度可以是1小时。 - 为每个被粒度分割的时间段创建实例。因此，对于B站点，将有一个实例（下午1-2点），对于A站点，将有许多实例（下午4-5点、下午5-6点、上午9-10点、上午10-11点等）。 - 为所有要分配的人创建实例。 - 然后迭代地考虑所有约束条件（如假期、午餐时间、只能同时进行一项任务、每个站点最多人数等），将一个人分配给一个空闲时间段，直到： - 你有一个有效的解决方案（好的，打印出来并退出应用程序）。 - 你进入了一个情况，在这种情况下，你仍然需要安排人员，但没有有效的时间段了。然后回溯（撤销上一个操作并尝试寻找替代方案）。

如果你的问题不太大，你可以在合理的时间内找到解决方案。

然而，如果问题变得更大，请寻找更专业的软件。需要寻找“基于约束的优化”和“约束编程”的软件。

例如，ECLIPSe工具是一个开源的约束编程环境。您可以在http://eclipseclp.org/examples/index.html上找到一些示例。您可以在那里找到一个不错的例子，即SEND+MORE=MONEY问题。在这个问题中，您有以下方程式：

    S E N D
+   M O R E
-----------
= M O N E Y

将每个字母替换为数字，以便总和正确。 这也说明了虽然可以使用暴力方法解决此问题，但还有更智能的解决方法（请参见http://eclipseclp.org/examples/sendmore.pl.txt）。

- Patrick