大学考试安排算法/问题
我想知道如何安排1万名学生在两周内参加考试，并保证没有学生连续两期考试。我假设应用某种形式的启发式方法。
我们所知道的是：
- 学生人数以及他们各自注册的课程。
- 考试时段的数量。
I wonder how to schedule 10k students to do exams in 2 weeks and guarantee no student will have an exam in two consecutive periods. I'm assuming some form of heuristics be applied.
All we know :
- Number of students and the courses that they're each enrolled in.
- Number of exam period spots.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
这是一个著名的计算机科学问题（考试安排问题），已知为NP-hard。你可能无法在一个周末解决这个问题。
This is a famous computer science problem (the exam scheduling problem) which is known to be NP-hard. You might not be able to solve it over a weekend.
这是一个约束满足问题的例子，这是一类困难的问题。其中一些属于 NP 类。大型商业软件包的存在就是为了尝试解决此类问题（例如 CPLEX） - 一般来说，它们使用一些数学和大量启发式方法。
This is an example of a constraint satisfaction problem, which is a difficult class of problems. Some of them are in the class NP. Large commercial software packages exist for trying to solve problems like these (eg CPLEX) - and in general, they use some mathematics and lots of heuristics.
我在硕士期间使用了禁忌搜索。这个想法并不太复杂：
，如果您被阻止，您可以通过对初始解决方案进行重要更改来“访问”其他解决方案。
I used the tabu search during my master. The idea is not too complicated:
if you're blocked, you can "visit" other solutions by making important changes to the initial solution.
这个问题实际上可能比这更普遍一些。例如，在我的学校，考试是按课程安排的时间安排的 - 即学期内通常在同一时间上课的所有课程都安排在考试周的某个时间段进行考试（不一定与考试时间相同）然而，例行班会）。因此，冲突通常不存在，因为出于明显的原因，学生不会在同一会议时间参加两门课程，因此不会同时进行两场考试。
然而，这意味着您仍然需要安排课程，以免它们发生冲突。 :)
The problem can actually be a bit more general than that. For instance, at my school, exams are scheduled by when the class is scheduled - i.e. all classes which meet at the same time normally during the semester, have an exam scheduled in a certain block of the exam week (not necessarily the same time as the regular class meeting, however). Thus, conflicts generally don't exist since students wouldn't be attending two classes in the same meeting time for obvious reasons, and thus wouldn't have two exams at the same time.
However, this means that then you still need to schedule classes so that they don't conflict. :)
当我大学四年级时，我们在人工智能课上做了一个与此类似的期末项目。我们编写了一个（勉强）工作系统来在适当的时间安排建筑物中的课程。某些规则不能被违反：如果教授。需要一间多媒体教室，他得到了一间。如果是CS课的话，就不应该安排在艺术楼。教授的课间时间不应超过 2 小时，等等。
我们使用了遗传算法。
When I was a senior in college, we did a final project in our AI class similar to this. We wrote a (barely) working system to schedule classes in buildings at appropriate times. Certain rules could not be violated: if the prof. needed a multimedia classroom, he got one. If it was a CS class, then it shouldn't be scheduled in the Art building. Profs shoulnd't have more than 2 hours between a class, etc.
We used a genetic algorithm.
有几件事可以让问题变得更简单。通过查看参加同一组考试的人，您可能可以将“要安排的单元”的数量从数万个减少到数百个。如果您有 300 人，他们都参加“计算机科学概论”和“计算机科学学生数学”课程，您可以将所有 300 人安排为一个单元，因为他们都有相同的限制，而您（可能）不希望完全相同考试在多个时段进行。
A few things to make the problem simpler. You can probably shrink the number of "units to schedule" down from tens of thousands to a few hundred, by looking at people who are sitting the same set of exams. If you have 300 people who all are sitting "Introduction to Computer Science" and "Maths for CS students", you can schedule all 300 as a single unit, because they will all have the same constraints and you (probably) do not want identical exams to be given in multiple slots.
这是图形着色问题的应用。这个问题可以表示为一个图，其中每个顶点都是一门课程，两个顶点之间的边意味着有一个共同的学生注册了两门课程。因此，这是一个图着色问题，其中最小时隙数等于对图的顶点进行着色所需的最小颜色数，使得没有两个相邻顶点共享相同的颜色。
This is an application of the graph coloring problem. This problem can be represented as a graph where every vertex is a course and an edge between two vertices mean there is a common student enrolled in both courses. So this is a graph coloring problem where minimum number of time slots is equal to the minimum number of color required for coloring the vertices of the graph such way that no two adjacent vertices share the same color.