最佳适配调度算法

Question

有几个事件，每个事件都有多个会议时间。我需要找到一种会议时间的安排，使得每个日程表都恰好包含每个给定的事件一次，并使用每个事件的多个会议时间之一。

我可以使用蛮力方法，但那很少是最佳解决方案。我更希望能够阅读相关资料的链接，或者只是一个我可以在谷歌上搜索的名字。

- stillinbeta

---

调度问题通常是NP完全的，这意味着你不能比暴力算法更好（我们认为）。不过我对于这个更具体的问题不太确定。 - BlueRaja - Danny Pflughoeft

这些问题通常是NP完全的，因此没有有效的算法可以得到最佳解决方案，但有一些高效的算法在大多数情况下可以得到相当不错的答案。关键词可能会涉及“装箱问题”，虽然不完全正确。您还可以尝试搜索“班级排课算法”并查看结果。 - Dale Hagglund

“每个日程”？所以你想找到参加所有活动的所有可能方式吗？ - Beta

@Beta 那是最理想的，但如果只找到一个并且速度显著更快，那也可以。@BlueRaja 是的，没错。 - stillinbeta

@stillinbeta 我不完全理解问题描述。您是在尝试将尽可能多的事件安排到日程中，给出了一个带有相应时间的事件列表吗？ - Anderson Green

Answer 1

我认为你应该使用遗传算法，因为：

• 它最适合解决大问题实例。
• 以牺牲精确答案为代价，可以降低时间复杂度（不是终极最优解）。
• 你可以通过调整未满足偏好的适应度惩罚来轻松指定约束和偏好。
• 你可以指定程序执行的时间限制。

• 解决问题的质量取决于你打算花多少时间解决程序。

  遗传算法定义

  遗传算法教程

  使用GA进行课程安排项目

- Betamoo

Answer 2

有几种方法可以做到这一点。其中一种方法是使用约束编程。它是feanor建议的动态规划的一个特例。使用一个可以为您执行边界和分支的专业库很有帮助。(搜索“gecode”或“comet-online”以查找库)

如果你数学倾向，你也可以使用整数规划来解决问题。基本思想是将问题转化为一组线性不等式。(搜索“整数规划调度”以找到许多实际示例，搜索“Abacus COIN-OR”以获得有用的库)

我猜约束编程是最简单的方法，但整数规划在某些时候如果你想包含实数变量是有用的。

- nielsle

---

顺便说一句：我不会在这样的任务中使用遗传编程：1）遗传算法有点慢；2）它们有点难以调试，因为它并不总是收敛到全局最优解。 - nielsle

Answer 3

您的问题描述不是很清楚，但如果您只是想找一个没有重叠事件的日程安排，那么这就是一个简单的二分图匹配问题。

您有两组节点：事件和时间。从每个事件到每个可能的会议时间都要画一条边。然后，您可以使用增广路径有效地构造匹配（节点之间最大可能的边集）。这是可行的，因为您始终可以将二分图转换为等价的流图。

一个做到这一点的代码示例是BIM。标准的图形库，如GOBLIN和NetworkX也有二分图匹配实现。

- ire_and_curses

Answer 4

这句话的意思是：“这似乎是一个很好的动态规划解决方案的候选者，具体来说类似于区间调度问题。这里有一些区间调度问题的可视化内容，可能会使概念更清晰。这是一个关于整个动态规划的好教程。”

- Feanor