匈牙利算法和多种因素

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

这是一个调度/优化问题,因此关键问题是"您想要最大化的数量"？我猜你是想在没有冲突的情况下最大化你所有志愿者的总工作小时数,这取决于每个志愿者的时间限制.您还提到了具有更多经验的志愿者的优先顺序,所以听起来您说"一些志愿者比其他人更受欢迎".

这是典型的二分匹配问题.参见Steven Skiena的The Algorithm Design Manual(第2版)的egp498.基本方法是构建一个图表,其中顶点代表志愿者集合,以及您尝试填充的时间集合.边缘将志愿者链接到有效的时间段.然后,最佳解决方案是最大可能的边缘集合,其中不重复志愿者或时间段.这是一个匹配.

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

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

如果您需要更多详细信息,包括其他替代方案以及更多实现链接,我强烈建议您自己获取算法设计手册的副本 - 这是一个非常清晰和实用的参考.