我正在编写一个具有困难编程问题的调度程序。有几个事件，每个事件都有多个会议时间。我需要找到一个会议时间安排，以便每个日程安排只包含一次任何给定的事件，使用每个事件的多个会议时间之一。
显然我可以使用蛮力，但这很少是最好的解决方案。我猜这是一个相对基本的计算机科学问题，一旦我能够开始学习计算机科学课程，我就会了解这个问题。与此同时，我更喜欢任何我可以阅读的链接，甚至只是一个我可以谷歌的名字。
问问题
23335 次
4 回答
11
我认为你应该使用遗传算法，因为：
- 它最适合大型问题实例。
- 它以不准确的答案为代价降低了时间复杂度（不是最终最好的）
- 您可以通过调整未满足的健身惩罚来轻松指定约束和偏好。
- 您可以指定程序执行的时间限制。
解决方案的质量取决于您打算花多少时间解决程序。
于 2010-05-01T12:17:50.480 回答
5
做这件事有很多种方法
一种方法是进行约束规划。这是feanor建议的动态规划的一个特例。使用可以为您进行边界和分支的专门库是有帮助的。（谷歌“gecode”或“comet-online”查找库）
如果你有数学倾向，那么你也可以使用整数规划来解决这个问题。这里的基本思想是将您的问题转化为一组线性不等式。（谷歌“整数规划调度”可以找到许多现实生活中的例子，谷歌“Abacus COIN-OR”可以找到一个有用的库）
我的猜测是约束规划是最简单的方法，但如果你想在某个时候在你的问题中包含实变量，整数规划是有用的。
于 2010-06-09T10:13:53.070 回答
3
您的问题描述并不完全清楚，但是如果您要做的只是找到一个没有重叠事件的时间表，那么这是一个简单的二分匹配问题。
您有两组节点：事件和时间。从每个事件到每个可能的会议时间画一条边。然后，您可以使用增强路径有效地构造匹配（节点之间最大可能的边集）。这是有效的，因为您始终可以将二分图转换为等效的流图。
于 2010-04-30T17:28:12.507 回答