4

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

首先，一些背景。这是一个非营利组织，该组织为因任何原因住院的儿童宣传故事时间，因此他们依靠志愿工作来做到这一点。因此，由于他们依赖于人们的善意，他们给人们尽可能多的工作，人们可以/想做的事情，变化如下：

  • 有的人只能做上午，有的人只能做下午；
  • 有的人只能周一、周四去，有的人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

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

你怎么想，你会怎么做？

4

1 回答 1

15

这是一个调度/优化问题，所以关键问题是“你想最大化什么数量”？我猜想您希望最大限度地增加所有志愿者的工作总时数而不会发生冲突，这取决于每个志愿者的时间表限制。你还提到优先考虑有更多经验的志愿者，所以听起来你是在说“一些志愿者比其他志愿者更受欢迎”。

这就是一个经典的二分匹配问题。参见 Steven Skiena的算法设计手册（第 2 版）的 egp498。基本方法是构建一个图，其中的顶点代表志愿者集和您尝试填充的时间段集。边缘将志愿者链接到有效的时间段。最佳解决方案是最大可能的边缘集，其中没有重复志愿者或时隙。这是一个匹配。

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

如果你想实现志愿者的优先级，那么这有效地增加了每个边缘的权重，模拟了志愿者对该任务的体验。在这种情况下，如您所想，您将需要类似于匈牙利算法的东西。如果没有这个就可以逃脱，那么您可以将问题转换为等效流图，并应用网络流算法。下面是一个实现加权和非加权匹配的代码示例。

如果你想要更多细节，包括其他替代方案，以及更多实现链接，我强烈建议你自己获取一份算法设计手册——这是一个非常清晰和实用的参考。

于 2009-08-03T13:08:17.073 回答