php - 如何实现大学讲座的座位分配算法

Question

我们大学的讲座有大约 1000 个免费座位，需要大约 2000 个座位(可能 500 名学生每人需要 4 个名额)。
我正在使用 CakePHP 开发一个网络应用程序，它可以让学生制作一个心愿单并在每个 block 中输入 4 个讲座，优先级从 1 到 4。(然后进入 MySQL 数据库)

现在，Web 前端已完成，管理操作(添加讲座、添加讲师等)也已完成。剩下的唯一事情就是编写分发算法。

我应该如何最好地做到这一点？一个 MySQL 脚本似乎很有用，但是当涉及到循环和 if 构造时，mysql 不是很友好，是吗？
将数据导出到某个地方并让另一种语言处理问题是否明智？

编辑:dnagirl 请求有关算法的更多信息: 我们没有算法的业务规则。我们从另一所大学的其他人那里改编了一个现有的(非常昂贵的)应用程序，它有我们刚刚改编的规则。
他正在做的事情(以及我正在尝试克隆的事情，以节省每学期的大笔费用)是这样的:

• 事件(讲座、练习等)都属于一个 block ( block 例如国际政治，可能有 4 或 5 个不同的事件)
• 学生每个区 block 最多可以申请 4 个事件，优先级为 1 到 4。
• 该算法按 block 工作。对于每个区 block ，根据排名将学生分成不同的组。 (排名“越高越好”，正常排名为0-20)
• 从排名最高的一组学生中，随机挑选一个。在他选择的优先级为 1 的事件中给他一个座位。如果此事件已满，则给他优先级为 2 的座位；等等，减少到 4。
• 选择下一个学生，重复同样的操作，直到这个排名的每个学生都有座位。然后，进入下一个较低的排名，重新做所有的事情。此 block 完成后，对下一个 block 再次执行所有操作，直到完成所有 block 。

我知道这个算法不是最好的解决方案，但我想我现在只是克隆它，然后可能会在逻辑/可能性方面进行改进。

Answer 1

您可能需要某种遗传算法:

• 在讲座中随机分配学生
• 计算分数(满足的愿望得分高，超额预订的讲座产生惩罚等)
• 进行更改(例如，将一名学生调到另一个类)。如果分数增加，则保持它，否则拒绝。
• 继续迭代，直到找不到可以增加分数的变化:您已找到局部最小值
• 将整个过程重复几次以找到其他局部最小值。然后选择得分最高的解决方案。

您必须运行一些测试并调整评分权重才能使其正确。

MySQL 不是很适合这个；你最好用 PHP 解决这个问题，然后坚持下去。如果性能不够好，你甚至可以考虑用 C++ 实现它，但我建议你先尝试 PHP，看看它是否足够快。您不会每 2 秒运行一次。