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

Question

在我们的大学里，我们有大约1000个免费的座位，大约有2000个座位(大约500个学生，每个要求4个名额)。

我正在用CakePHP开发一个webapp，它可以让学生生成一个愿望列表，每个区块输入4个讲座，优先级从1到4。(然后进入MySQL数据库)

现在，网络前端已经完成，管理操作(增加讲座、增加讲师等)已经完成。唯一剩下的就是编写分发算法。

我该怎么做才好呢？mysql脚本似乎很有用，但是mysql在循环和if-构造方面不是很友好，是吗？

将数据导出到某个地方并让另一种语言来处理这个问题是否明智呢？

编辑: dnagirl要求更多关于算法的信息:我们没有算法的业务规则。我们从另一所大学的其他人那里改编了一个现有的(非常昂贵的)应用程序，它有我们刚刚修改过的规则。

他在做什么(我试图克隆，以节省高额的每学期费用)，是这样的：

• 活动(讲座、练习等)
• 的学生每组最多可以申请4个事件，优先级为1~4个。
• 算法每个块都适用。对于每个区块，根据学生的排名将他们分成不同的组。(排名是“越高越好”。正常排名从0到20)
• 从一组排名最高的学生中随机选出一位。在他选择的活动中给他一个优先1的位置。如果这个活动已经满了，给他他选择的第2优先的座位；等等，降低到4。
• 选择下一个学生，并做同样的事情，直到每个有这个排名的学生都有一个席位。然后，进入下一个较低的排名，再做每一件事。当该块完成后，再次使用下一个块执行所有操作，直到所有块都完成为止。

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

Answer 1

你可能想要某种遗传算法：

lectures

• Calculate
• 随机分配学生一个分数(满足愿望得分高，讲课超额产生惩罚等)
• 做出改变(例如将一个学生转移到另一个讲座)。如果分数增加，保持它，否则拒绝。
• 继续迭代，直到找不到增加分数的更改为止:您已经找到了一个本地最小值
• ，重复了整个过程几次，以找到其他的局部极小值。然后用最好的得分解决方案。

你必须进行几次测试，调整得分权重才能使之正确。

MySQL并不非常适合这一点；您最好用PHP解决这个问题，然后坚持一次执行。如果性能不够好，您甚至可以考虑在C++中实现它，但我建议您先尝试PHP，看看它是否足够快。你又不是要每两秒钟运行一次。