有效分配“技能”到“企业”的算法 - 稳定婚姻问题

Question

游戏Tiny Tower里有各种各样的“Bitizens”（小市民），他们在不同的技能上评分从0到9不等：

Michael:  
 a) retail: 9
 b) creative: 2
 c) service: 7
 d) recreational: 4
 e) food: 6

每个Bitizens可以在三家商店工作。这些商店分为几类：零售、创意、服务、休闲和食品。商店的数量和Bitizens的数量不一定相等，但为了简单起见，我们可以假设每个商店都有一个职位，正好可以让每个Bitizens工作。

比如说，有一家帽子店，这是一家零售商店，所以那些在retail（零售）方面评分高的Bitizens更适合在这里工作。在上面的例子中，Micheal非常适合在零售商店工作。

我该如何用算法来把最合适的Bitizens安排到这些职位上呢？我试着解决这个问题，但总是觉得很难找到一个有效的方法。

Answer 1

如果你能把所有的属性归纳到一起，只留下一个需要最小化的目标，那么你就可以用一种叫做分配问题的方法来解决你的问题。否则，你的问题就像多重索引分配问题，这类问题是非常复杂的，解决起来很困难。

所以，请详细说明一下你的具体情况，这样我们才能找到一个合理的解决方案。

Answer 2

假设无论你把一个额外的“点”放在哪里，它的价值都是一样的。比如说，如果你有两个生意，一个是创意类的，另一个是食品类的，我们假设总的来说，创意类有20个点，食品类有3个点，总比两个生意各有11个点要好。

在这种情况下，你的问题就是一个叫做分配问题的例子。这个问题被认为是“简单”的，因为它可以在多项式时间内解决，具体来说是O(n^3)的时间复杂度。解决这个问题的标准方法是匈牙利算法。我不能比维基百科的页面解释得更好，那里有很详细的内容，但如果你在那上面遇到什么困难，随时可以问我。

如果你有大量的“比特市民”和生意，以至于这个算法无法使用，我觉得可以尝试一些近似的方法，比如模拟退火或者进化算法。

如果我最开始的假设不正确（比如说，可能至少需要有一个人手充足的每种类型的生意会更好），那么你几乎肯定应该尝试这些不精确的方法。重点是设计一个目标函数，能够反映任何给定的员工与生意的分配组合的价值。