按优先级分配资源的算法

Question

我的问题如下:我和我的团队要搬到办公室的另一个地方，我们必须决定每个人的座位。但是，每个人都有优先事项。我想找到一种算法来帮助我们以每个人都满意的方式分配座位。 (或者至少是其中的大部分。)

我已经开始实现我自己的算法，我向每个人询问 3 个首选选项(团队由 10 个人组成，有 10 个位置)并考虑“资历”(他们在该团队中花费的时间长度)团队)作为他们之间的排名。

然而，我一直没有任何运气，试图浏览互联网寻找解决类似问题但没有找到的算法。

解决这个问题的最佳方法是什么？有没有解决这个问题或类似问题的广为人知的算法？

谢谢!

Answer 1

我首先想到的是稳定的婚姻问题。这是原始算法的问题陈述:

Given n men and n women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable.

请阅读 Gale–Shapley algorithm ，这就是我将针对此问题进行的调整。

让每个 worker 列出他们对所有地点的排名。这些将是“人”。届时，各名额将以资历排名作为“男”的排名。这些 Blob 将是 Gale-Shapley 算法中的“女性”。

您将获得没有“不稳定婚姻”的座位分配。不稳定的婚姻是这样的:

1. There is an element A of the first matched set which prefers some given element B of the second matched set over the element to which A is already matched, and

2. B also prefers A over the element to which B is already matched.

在这种情况下，不稳定的婚姻意味着在 W1 和 S1 分配之间有一个 worker-seat，这样另一个 worker，W2 , S1 排名更高。不仅如此，S1 的排名也比W2 高。由于席位是根据资历列表列出的，这意味着 W2 具有更高的资历。

实际上，这意味着您将获得一个座位分配，这样就没有工作人员拥有比资历更高的其他人想要“更多”的座位。

那篇 Wiki 文章的底部提到了 R 和 Python 中的包，它们已经实现了该算法，因此您只需输入首选项列表即可。

免责声明:这可能不是最有效的算法。所有的座位都有相同的排名表，所以可能有什么捷径。但是，如果大炮已经用 R/Python 为您编写，则使用大炮杀死苍蝇会更容易。此外，这是我记得的唯一一个 uni 算法，所以这是我唯一能用的锤子。