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

Question

游戏Tiny Tower有各种各样的“bitzen”，它们在不同的属性中是熟练的0-9：

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

然后它就有了三个比特人可以工作的业务。每一项业务都分为零售、创意、服务、娱乐和食品。企业数量和员工数量之间从来没有任何匹配，但为了使事情更简单，我们可以假设职位数量与员工数量匹配。在

例如，零售店的价值很高。在上面的例子中，Micheal非常适合从事零售业务。在

从算法上讲，我怎么能用最有相关技能的比特人来填补空缺呢？我试着试着解决这个问题，但我很难用一种能有效解决问题的方式来解决问题。在

Answer 1

如果您能够将所有属性聚集在一起，使得只有一个目标要最小化，那么您就可以用assignment problem来解决您的问题。否则你的问题就像multi-index assignment problem，这是NP难的。在

所以，请详细说明你的具体情况，以便找到一个合理的解决办法。在

Answer 2

让我们假设一个额外的“点”无论你放在哪里都同样有价值。例如，如果你有两个企业，创意和食品，我们假设总有20个创意和3个食品，而不是每个有11个。在

在这种情况下，您的问题是Assignment problem的一个例子。这是众所周知的“容易”，因为它可以在多项式时间内求解：特别是在时间O（n^3）中。Hungarian algorithm是解决这个问题的标准方法。我无法解释比维基百科页面更好的解释了，这个页面非常详细，但是如果你有什么问题，尽管问。在

如果你有大量的bitzen和business，所以这个算法是不可行的，我认为这个问题很容易被simulated annealing或{a4}之类的近似方法攻击。在

如果我最初的假设是不正确的（例如，如果每种类型至少有一个人员充足的企业可能更好），你几乎可以肯定地尝试这些不精确的方法。集中精力设计一个目标函数，它反映任何给定的工人业务分配排列的价值。在