最佳适应调度算法
有多个活动，每个活动都有多个会议时间。我需要找到会议时间的安排，以便每个日程表仅包含任何给定事件一次，使用每个事件的多个会议时间之一。
我可以使用暴力，但这很少是最好的解决方案。我更喜欢任何可以阅读此内容的链接，甚至只是一个我可以谷歌搜索的名称。
There are several events, each with multiple meeting times. I need to find an arrangement of meeting times such that each schedule contains any given event exactly once, using one of each event's multiple meeting times.
I could use brute force, but that's rarely the best solution. I'd prefer any links where I could read up on this, or even just a name I could Google.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我认为您应该使用遗传算法，因为：
解决方案的质量取决于您打算花费多少时间来解决该程序。
遗传算法定义
遗传算法教程
GA 排课项目
I think you should use genetic algorithm because:
The quality of solution depends on how much time you intend to spend solving the program..
Genetic Algorithms Definition
Genetic Algorithms Tutorial
Class scheduling project with GA
有多种方法可以做到这一点，
一种方法是进行约束规划。这是 feanor 提出的动态规划的一个特例。使用可以为您完成边界和分支的专门库很有帮助。 （谷歌搜索“gecode”或“comet-online”来查找库）
如果您有数学倾向，那么您也可以使用整数规划来解决问题。这里的基本思想是将您的问题转化为一组线性不等式。 （谷歌搜索“整数编程调度”可以找到许多现实生活中的例子，谷歌搜索“Abacus COIN-OR”可以找到有用的库）
我的猜测是约束编程是最简单的方法，但是如果你想包含实数，整数编程是有用的在某些时候你的问题存在变数。
There are several ways to do this
One approach is to do constraint programming. It is a special case of the dynamic programming suggested by feanor. It is helful to use a specialized library that can do the bounding and branching for you. (Google for "gecode" or "comet-online" to find libraries)
If you are mathematically inclined then you can also use integer programming to solve the problem. The basic idea here is to translate your problem in to a set of linear inequalities. (Google for "integer programming scheduling" to find many real life examples and google for "Abacus COIN-OR" for a useful library)
My guess is that constraint programming is the easiest approach, but integer programming is useful if you want to include real variables in you problem at some point.
您的问题描述并不完全清楚，但如果您想做的只是找到一个没有重叠事件的时间表，那么这是一个简单的 二分匹配问题。
您有两组节点：事件和时间。从每个事件到每个可能的会议时间绘制一条边线。然后，您可以使用增强路径。这是可行的，因为您始终可以将二分图转换为等效的流程图。
执行此操作的代码示例是 BIM。标准图形库，例如 GOBLIN 和 NetworkX 也有双向匹配实现。
Your problem description isn't entirely clear, but if all you're trying to do is find a schedule which has no overlapping events, then this is a straightforward bipartite matching problem.
You have two sets of nodes: events and times. Draw an edge from each event to each possible meeting time. You can then efficiently construct the matching (the largest possible set of edges between the nodes) using augmented paths. This works because you can always convert a bipartite graph into an equivalent flow graph.
An example of code that does this is BIM. Standard graphing libraries such as GOBLIN and NetworkX also have bipartite matching implementations.
这听起来像是动态编程解决方案的一个很好的候选者，特别是类似于间隔调度问题。
这里有一些视觉效果专门针对间隔调度问题，这可能会使概念更清晰。 这里总体上是关于动态规划的一个很好的教程。
This sounds like this could be a good candidate for a dynamic programming solution, specifically something similar to the interval scheduling problem.
There are some visuals here for the interval scheduling problem specifically, which may make the concept clearer. Here is a good tutorial on dynamic programming overall.