算法计算给定的时间表限制 [英] Algorithm for computing timetable given restrictions

问题描述

我在考虑一个假设性的问题，并寻找指导如何处理解决问题，从一个算法问题。

I'm considering a hypothetical problem, and looking for guidance on how to approach solving the problem, from an algorithmic point of view.

的问题：

考虑一所大学。您有以下对象：

Consider a university. You have the following objects:

• 教学人员。每个工作人员教一个或更多的论文。
• 学生。每个学生需要一个或更多的论文。
• 客房。客房持有一定数量的学生，并含有某些类型的设备。
• 论文。要求每个周某种类型的设备，和一定量的时间。

有关入学率（即 - 有多少学生就读于各纸，什么工作人员被分配教每篇论文）所提供的信息，我怎么能计算出一个时间表，即遵循以下限制：

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:

1. 在工作人员只能教一次一件事情。
2. 学生只能参加一纸一次。
3. 在房间只能容纳一定数量的学生。
4. ，需要某种类型的设备只能在一个房间提供某种类型的设备被保持在论文。
5. 在营业时间是周一至周五，8-12和1-5。

讨论：

在现实中我不是太在意上述的情况 - 这是一般类的问题，我很好奇。乍一看，这似乎对我来说，非常适用于遗传算法，但适应度函数的这种算法是极其复杂的。

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.

推荐答案

住遗传算法，我不认为健身功能，这将是非常复杂的，恰恰相反。

Staying on genetic algorithms, I don't think the fitness function for this would be very complex, quite the opposite.

您基本上只是检查你的候选解决方案（无论编码）每个约束（你只有5），并分配一个权重给他们，这样，当一个约束没有满足重量加到总成绩，可以再present健身。

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.

在这种情况下，你只需最小化适应度函数（因为可能的最好的健身是0​​，这意味着所有的约束条件都满足），让GA紧缩的数字。

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 :)

这篇关于算法计算给定的时间表限制的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！