algorithm - 匈牙利算法和多重因素

Question

我有一种情况需要将人员分配给多个事件。如果我们只将价格作为一个因素，那会很好，但还有很多因素会影响。

首先，一些背景。这是一个非营利组织，该组织为因任何原因住院的 child 宣传故事时间，因此他们依靠志愿工作来做到这一点。因此，由于他们依赖于人们的善意，他们会尽可能多地为人们提供工作/想做的工作，具体如下:

• 有的人只能做上午，有的人只能做下午；
• 有的人只能周一、周四去，有的人8、12月去不了；
• 有些人一个月只能去一次，有些人可以去 4 次(甚至其他人在这些行动中被给予“优先权”，因为他们更有经验，一个月可以做 10 次)<

所以，我有点想通了前两个。由于匈牙利算法是关于价格的，所以我会给他们一个愚蠢的高价，因为他们不能去。但是，您会怎么做其他人？

我想给他们打分。大概是这样的:一个人每月可以做一次这样的事情，大约需要 1000 点。如果某人每月可以去 10 次，则该人将花费 100 分(1000 基数除以 10)。此外，分配方式是在执行单独操作时提高价格，就像这样(选定的人在其相关成本上有 *):

第一次迭代

         | August 1st 2009
Person A | 1000
Person B | 500 *

第二次迭代

         | August 8th 2009
Person A | 1000 *
Person B | 1000 

这将是在所有人之间进行相应分配的方式，给予那些可以多次这样做的人更多的优先级。

你是怎么想的，你会怎么做？

Answer 1

这是一个调度/优化问题，所以关键问题是“你想最大化多少数量”？我猜你希望在不发生冲突的情况下最大限度地增加所有志愿者的工作总小时数，但要遵守每个志愿者的时间表限制。您还提到优先考虑具有更多经验的志愿者，所以听起来您是在说“一些志愿者比其他志愿者更受青睐”。

这就是经典bipartite matching problem .参见例如第 498 页 The Algorithm Design Manual (第 2 版)，史蒂文·斯基纳 (Steven Skiena)。基本方法是构建一个图，其顶点代表志愿者集和您要填补的时间段集。边缘将志愿者链接到有效的时间段。最佳解决方案是最大可能的边缘集，其中没有重复志愿者或时隙。这是匹配。

您的一些志愿者可能可以做不止一个空档；这可以通过多次复制该志愿者顶点来建模。

如果您想对志愿者进行优先排序，那么这会有效地为每条边添加权重，为该志愿者在该任务中的体验建模。在这种情况下，如您所想，您将需要类似匈牙利算法的东西。如果你不用这个就可以逃脱，那么你可以将问题转化为等价的 flow graph ，并应用网络流算法。这是 code that implements both weighted and unweighted matching 的一个例子.

如果您需要更多详细信息，包括其他备选方案和更多实现链接，我强烈建议您为自己准备一份算法设计手册 - 这是一份非常清晰和实用的引用。