database - 排序多个用户计划的算法或脚本

Question

我有一个可能看起来像这样的数据集:

user_name
time_1
time_2
time_3

在给定日期的时间不同的地方，它们是免费的。每周有 22 个时段，用户可以从三个时段中选择并提交。我将有大约 100-150 个用户，我想知道如何以最好的方式对他们进行排序，以便在每个时间段内平均分配人数。我对开始方法的最佳猜测是，如果所有用户都被放入他们的第一个插槽 (time_1)，然后是 2 和 3，然后比较哪个给出最好的结果，然后从那里开始，看看会发生什么如果在插槽中添加或删除用户，这将如何影响整体性能。任何帮助将不胜感激，因为我没有做过很多优化算法。

问候，

Answer 1

我之所以回答，是因为在许多人选择同一个广告位而许多广告位没有选择者或选择者很少的情况下，以前的答案显然会崩溃。例如，如果所有用户都按顺序选择插槽 (1,2,3)，则拓扑排序将无济于事。

在理想情况下，每个人都会选择一个插槽，并且所有插槽都有相同数量的选择者 (+/- 1)。如果我自己处理这个问题，我会尝试使用实时在线服务器的先到先得制度，这样人们只能从他们登录时保持开放的插槽中进行选择。

如果在线先到先得不可行，我会 使用一种激励人们选择不同插槽的方法，可能带有随机性元素。这是一种这样的方法:

让一共有U个人，争夺H个时段。 (H=22.) 假设每个人都被分配到一个位置。令 P = [U/H](即，U/H 截断为整数)为每个时段的名义人数。 (U mod H 插槽将有 P+1 人。)对于插槽 j，令 D_j 为 3*R1j + 2*R2j + 1*R3j，其中 Rij 是插槽 j 被请求作为选项 i 的次数。对于更多期望的槽，D_j 更高。给每个用户k一个分数W_k = 1/D_{C1k} + 2/D_{C2k} + 3/D_{C3k}，其中Cik是用户k的第i个选择。也就是说，用户选择 D 值较低的插槽会获得更多分数，并且第二或第三选择的选择比第一选择的权重更大。

现在将插槽按 D_j 升序排序。 (“最繁忙”的槽将首先被填充。)将用户按 W_k 分数降序排列，并将此列表称为 S。

然后，对于每个槽j:当j未满时，{找到S中第一个选择槽j作为选择1的人k；如果找到，将 k 从 S 移动到槽 j。如果没有找到，则在 S 中找到第一个选择时隙 j 的人 k 作为选择 2；如果找到，将 k 从 S 移动到槽 j。如果没有找到，则在 S 中找到第一个选择时隙 j 的人 k 作为选择 3；如果找到，将 k 从 S 移动到槽 j。如果没有找到，将 S 中的最后一个人 k 添加到槽 j，并从 S 中删除 k。

在前面提到的糟糕情况下，所有用户都按顺序选择插槽 (1,2,3)，此方法会将随机的一组人分配到所有插槽。考虑到问题陈述，这和预期的一样好。

更新 1:首先完全填满最繁忙的位置可能会使一些人进入他们自称的第二或第三选择位置，而他们本可以被安置在他们的第一选择位置而不会发生冲突。最忙优先填充有利有弊，博弈论分析可能会解决这个问题。如果没有这种分析，在我看来现在最好通过以下(更简单的)方法来填充:和以前一样，创建排序的用户列表 S，按 W_k 分数的降序排列。现在按顺序浏览列表 S，将人们放入他们选择并适合的第一个可用位置，否则放入仍然有空缺的最受欢迎的位置。例如，如果用户 k 选择了插槽 p、q、r，如果 p 有空间，则将 k 放入 p，如果 q 有空间，则放入 q，如果 r 有空间，则放入 r，否则 j，其中 j 位于有空位的插槽中，并且 D_j 最大.

这种方法更容易向用户解释，是 更容易编程，并且通常可能更接近最佳。如果可以在不诉诸第三名选择的情况下填补空缺，它就会这样做。