给定限制的计算时间表的算法
我正在考虑一个假设的问题，并从算法的角度寻找如何解决问题的指导。
问题：
考虑一所大学。您有以下对象：
- 教学人员。每位工作人员教授一篇或多篇论文。
- 学生。每个学生需要一篇或多篇论文。
- 房间。房间可容纳一定数量的学生，并包含一定类型的设备。
- 文件。需要特定类型的设备，以及每周一定的时间。
给定有关注册的信息（即每篇论文注册了多少学生，以及分配了哪些教职员工来教授每篇论文），我如何计算遵守以下限制的时间表：
- 教职员工一次只能教一件事。
- 学生一次只能参加一篇论文。
- 房间只能容纳一定数量的学生。
- 需要某种类型设备的论文只能保存在提供该类型设备的房间中。
- 营业时间为周一至周五、8点至12点和1点至5点。
讨论：
实际上，我不太关心上面概述的情况 - 这是我好奇的一般问题。乍一看，在我看来，它非常适合遗传算法，但这种算法的适应度函数将非常复杂。
尝试解决此类约束满足问题的好方法是什么？
我想可能没有办法完美地解决这个问题，因为学生很可能会组合不同的论文，从而导致不可能的情况，尤其是当学生人数和学生数量都超过一定比例时。论文增长。
I'm considering a hypothetical problem, and looking for guidance on how to approach solving the problem, from an algorithmic point of view.
The Problem:
Consider a university. You have the following objects:
- Teaching staff. Each staff member teaches one or more papers.
- Students. Each student takes one or more papers.
- Rooms. Rooms hold a certain number of students, and contain certain types of equipment.
- Papers. Require a certain type of equipment, and a certain amount of time each week.
Given information about enrollments (i.e.- how many students are enrolled in each paper, and what staff are allocated to teach each paper), how can I compute a timetable that obeys the following restrictions:
- Staff can only teach one thing at once.
- Students can only attend one paper at once.
- Rooms can only hold a certain number of students.
- Papers that require a certain type of equipment can only be held in in a room that provides that type of equipment.
- Hours of operation are Monday to Friday, 8-12 and 1-5.
Discussion:
In reality I'm not too concerned with the situation outlined above - it's the general class of problem that I'm curious about. At first glance It seems to me like a good fit for a genetic algorithm, but the fitness function for such an algorithm would be incredibly complex.
What's a good approach for trying to solve this kind of constraint-satisfying problem?
I guess there's probably no way to solve this perfectly, since students may well take a combination of papers that leads to impossible situations, especially as the number of students & papers grows.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
继续遗传算法，我认为适应度函数不会非常复杂，恰恰相反。
您基本上只需检查每个约束（您只有 5 个）的候选解决方案（无论编码如何）并为其分配权重，以便在不满足约束时将权重添加到可以代表适应性的总分中。
在这种情况下，您只需最小化适应度函数（因为最佳适应度可能为 0，这意味着满足所有约束）并让 GA 处理数字。
编码需要一些时间来弄清楚，但是一旦完成，它应该很简单，除非我遗漏了一些东西，当然:)
Staying on genetic algorithms, I don't think the fitness function for this would be very complex, quite the opposite.
You basically just check your candidate solution (whatever the encoding) for each of the constraints (you only have 5) and assign a weight to them so that when a constraint is not satisfied the weight is added to a total score that could represent fitness.
In such a scenario you just minimize the fitness function (because best fitness possible is 0, meaning all the constraints are satisfied) and let the GA crunch the numbers.
The encoding will take a bit of figuring out, but once that's done it should be straightforward, unless I am missing something, of course :)
这个问题的一个非常受限的版本是 NP 完全问题。
考虑只有一个学生可以完成一篇论文的情况。
现在，对于给定的时间段（假设全天教授论文），您可以构建一个 3 部分图，其中包含房间、论文和学生，如果学生想要参加，论文和学生之间有一条边。还要在纸张和可能的房间之间添加边缘。
我们现在看到 3 维匹配问题 是您的问题的一个实例：您需要为该特定时间段选择一个不重叠的（学生、论文、房间）组合。
对于一般问题，您可能最好采用一些启发式方法。抱歉，我帮不了你。
希望有帮助。
A very restricted version of this problem is NP-Complete.
Consider the case when exactly one student can take a paper.
Now for a given time slot (say the paper is taught all day), you can construct a 3-partite graph, with Rooms, Papers and Students, with an edge between a paper and a student if that student wants to take it. Also add edges between a paper and it's possible rooms.
We now see that the 3 Dimensional matching problem is an instance of your problem: you need to pick a non-overlapping (student, paper, room) combination for that particular timeslot.
You are probably better off with some heuristics for the general problem. Sorry, I can't help you there.
Hope that helps.