匈牙利算法和多种因素

Question

我有一种情况，我需要分配给几个人的事件。如果我们只是以一个价格作为因素，那就没有问题，但是有很多因素可以进来。

首先，一些背景。这是一个非营利组织，它为因任何原因住院的儿童提供故事时间，所以他们依靠志愿工作来这样做。所以，因为它们依赖于人们的良好意愿，他们给人们尽可能多的工作，因为人们可以/想做的事，而变化，如：

• 有些人只能做早晨，和其他一些人只能做的下午;
• 有些人只能做星期一和星期四，其他人不能去八月或十二月;
• 有些人每月只能去一次，其他人可以去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。见例如由Steven Skiena撰写的The Algorithm Design Manual（第二版）的第498页。基本的方法是构造一个图表，其顶点代表志愿者集合，以及您尝试填充的时间段集合。 Edges将志愿者链接到有效的时间段。那么最佳解决方案是最大可能的一组边缘，其中不重复志愿者或时隙。这是一个匹配。

你的一些志愿者可能可以做多个插槽;这可以通过多次复制该志愿者顶点来建模。

如果您想实施志愿者的优先顺序，那么这将有效地为每个边添加权重，为该任务的志愿者的体验建模。在这种情况下，如你所想，你将需要像匈牙利算法之类的东西。如果没有这个可以逃脱，那么你可以将这个问题转换成等效的flow graph，并应用网络流算法。这里是code that implements both weighted and unweighted matching的一个例子。

如果你想了解更多细节，包括其他选择，以及更多的实现链接，我强烈建议你自己找一份算法设计手册 - 这是一个非常清晰和实用的参考。