嗨,我正在建立一个项目,学生正在报名参加在全国几个城市进行的考试.虽然报名学生提供了三个城市的列表,他们希望按照自己的喜好进行考试.所以学生可能会说他对考试中心的首选是纽约,其次是芝加哥,其次是波士顿.
现在请记住,由于考试中心的能力有限,他们无法容纳每个学生的第一选择.但是我们会尝试为第一或第二选择的中心提供尽可能多的学生,并尽可能避免学生必须给出第三选择以学生为中心
现在任何一种排序算法的想法都会使这个过程更加有效.这样做的简单方法是首先通过尽可能多的第一选择的学生列表,然后通过第二选择列表并分配.然而,这可能会导致排名第一的学生获得他们的第一个中心,最后一个学生获得他们的第三选择,或者更糟糕的是没有他们的选择.任何可以提高效率的东西
听起来像是经典稳定婚姻问题或大学入学问题的变种.维基百科列出了线性时间(以喜好,O(数量ñ ²)人口数)算法的前; NRMP描述了后者的有效算法.
我怀疑如果你为学生随机生成考试地点的偏好(每个考试地点一个Fisher-Yates shuffle)然后应用稳定婚姻算法,你将得到一个非常公平和有效的解决方案.