有效排课算法

Question

我已经得到了我被要求做这涉及编写一个程序，以确定不同的人都在某一天上班工作。

例如，输入可以是：
4-6pm，站点A
1-2pm，站点B
上午9至11 & 2-4pm站点A

本质上可以有许多网站和人可以在多个块中工作。我感觉到这种问题很早以前就已经得到解决，而不是重新发明轮子，我希望有人能够向我指出一个优雅的解决方案。

编辑：阅读类似的问题，我得到这个问题可能是NP完全的感觉。我不需要最有效的解决方案，只需要一些可行的解决方案，而且是合理的。

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

Answer 1

看起来你正在试图解决其中有相当专门的软件应用程序的问题。如果你的问题是足够小，你可以尝试做一个强力的办法是这样的：

• 确定问题的粒度。例如。如果这是一个学校时间表，你的粒度可以是1小时。
• 为每个时隙创建实例，并按粒度划分。因此，对于网站B将会有一个实例（1-2pm），对于大小A，将会有许多实例（下午4-5pm，5-6pm，9-10am，10-11am，...）。
• 为所有想要分配的人创建实例
• 然后迭代地将一个人分配到一个空闲时间段，并将所有约束条件考虑在内（例如假期，午餐休息时间，一次只能做一件事，每个网站的用户最大数量，...），直到：
  • 你有一个有效的解决方案（精细，打印出来并退出应用程序）
  • 你进入一个情况下，你仍然需要把人，但有不再是有效的时间段。然后回溯（撤消最后一个动作并尝试找到替代方法）。

如果你的问题不是太大，你会发现在合理的时间内解决。

但是，如果这个问题开始变得大了，找更专业的软件。需要注意的是“基于约束的优化”和“约束编程”。

E.g. 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）。