问一种求解资源分配问题的算法

EN

听起来像是经典的stable marriages problem或college admission problem的变体。维基百科为前者列出了线性时间(在偏好数量中，在人数中为O(n²) )算法；NRMP为后者描述了efficient algorithm。

我怀疑，如果您随机为学生生成考试地点的偏好(每个考试地点一个Fisher–Yates shuffle )，然后应用稳定婚姻算法，您将获得一个相当公平和有效的解决方案。

这个问题可以表述为minimum cost flow的一个实例。设N为学生人数。让每个学生都是一个容量为1的源顶点。让每个考试中心都是一个容量为1的汇点。从每个学生到他的第一个、第二个和第三个选择画一条弧线。将第一个选择弧的成本设置为0；将第二个选择弧的成本设置为1；将第三个选择弧的成本设置为N+ 1。

找到一个能移动N个单元的最小成本流。假设你的求解器返回一个完整的解(它应该是；流LP是完全单模的)，每个学生流一个单元到他分配的中心。成本最小化了第三选择任务的数量，通过第二选择任务的数量打破了平局。

有一类算法可以解决这种有限资源的分配问题，称为拍卖。基本上，在这种情况下，每个学生都会得到一定数量的钱(一个他们可以花费的数字)，然后你的软件将在这些学生之间进行出价。您可以使用基于首选项的公式。

一个例子就是教程时间。如果你放下你的偏好，那么你将有效地为这些时间出价更多，而为你不想要的时间出价更少。因此，如果你没有得到你的偏好，你就有更多的“钱”来竞标其他教程。