想象一下它是公元前 3000 年，我们正在建立一些异性恋、一夫多妻制的快速约会。有n_c男有n_s女（n_s > n_c）。快速约会将分n_r轮进行。在每一轮中，每个男人都会遇到一个女人。所以n_r*n_c插槽要填补。
此外，他们都填写了石碑问卷，我们从中构建了一个评分函数 ，
它给出了在其中一个插槽u(i,j)中配对男人i和女人的效用。j
目标是最大化所有时段的得分总和，在此约束条件下，没有男人会遇到同一个女人超过一次，并且每个女人最多会遇到
ceil(n_r*n_c/n_s)
男人。（也就是说，每个女人应该与大约相同数量的男人见面。）
你能画出一个算法来解决这个问题吗？可以假设男性和女性的数量在 100 人以下，可能在 50 人以下。哦，假设我们将现代硬件带到了公元前 3000 年。
可以表述为最小成本循环问题，然后使用许多算法之一解决（例如，循环取消、网络单纯形；这些多项式时间算法对于 50 个元素应该非常快）。
为每个男人和女人制作一个顶点。制作一个源/汇顶点。这些人有来自源/汇的弧线，流量n_c和容量最小n_c，成本为零。女性对容量的源/汇有弧线ceil(n_r*n_c/n_s)，成本为零。对于每个男人和女人，都有一条1从男人到女人的能力弧。这条弧线的成本是-u(i,j)，男人在哪里，i女人在哪里j。
现在我们必须安排事情。这个想法是重复构建一个男性-女性二分匹配（即，单轮时间表），以匹配所有需要安排这一轮的女性。这些是女性的学历与男性相同。通过平均论证（如果男性度数为 k，则 n 度数为 k 的女性必须与至少 n 个男性相邻，否则某些男性的度数会大于 k），霍尔定理适用，我们可以完美匹配这些女性。通过对男性的类似论证，我们可以反复增加这种匹配以匹配所有男性。删除所有匹配的边并重复。
我们刚刚找到了这篇论文：
http://i11www.iti.uni-karlsruhe.de/_media/teaching/theses/sa-strasser-10.pdf
这正是攻击这个问题。
（我很高兴他们似乎正在真正解决快速约会问题。我的表述，如果你不知道的话，只是与我们正在解决的实际问题同构。）
如果您想最大化分数，则假设您将在两轮之间评估问卷。这听起来像是一个相当标准的聚类问题。
从至少两轮随机分配的男性和女性开始，确保不要创建任何重复的配对。那时，你应该至少有两个男人见过同一个女人。
然后你可以使用典型的“如果 Jim 和 Joe 都喜欢橘子，而 Joe 也喜欢柠檬，那么 Jim 很可能喜欢柠檬”。
如果我要解决这个问题，我会尝试的第一个技术是cosine Similarity。与随机分配配对相比，这应该会给您更高的总分。
我在这个问题上的第一次通过只是使用总分来确定相似性。也就是说，我会比较男人 A 和男人 B 评估同一位女性的总分。这很容易实现，因为它只涉及一个维度。一旦我证明它有效并且确实给出了比随机分配更好的分数，我可能会通过在每个问题的基础上进行比较来扩展维度的数量。毕竟，虽然 A 和 B 可能都给女人 Z 相同的分数，但一个可能专注于身体属性，另一个专注于个性和智力等方面，而不考虑身体属性。扩展到多个维度更复杂，更真实，但它应该会显着提高分数。