匈牙利算法和多个因素

Question

5

我有一个情况需要将人员分配到多个活动中。如果只考虑价格因素，那就很简单了，但实际上还有其他因素需要考虑。

首先，提供一些背景信息。这是为一个非营利组织工作的，该组织致力于为任何原因住院的儿童推广故事时间。因此，他们依靠志愿者来完成任务。由于他们依赖于人们的好意，所以他们会给予志愿者尽可能多的工作，而这种工作量是不同的，例如：

所以，我已经解决了前两个问题。由于匈牙利算法是关于价格的，我会给那些不能参加的时间一个非常高的价格。但是，你会如何处理其他问题呢？

我想过给他们一些分数。例如：一个每月只能去一次的人的成本大约是1000分。如果有人可以每月去10次，那么这个人的成本就是100点（1000基数除以10）。此外，分配的方式是在每次单独行动时增加价格，例如（所选的人在其相关成本上带有*）：

第一轮迭代

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

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

这将是公平分配给所有人的方法，更优先考虑那些可以多次执行此操作的人。

你认为如何做到这一点？

- changelog

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ire_and_curses · Accepted Answer

这是一个调度/优化问题，所以关键问题是“你试图最大化什么数量”？我猜想你正在尝试在每个志愿者的时间表限制条件下，在没有冲突的情况下最大化所有志愿者工作的总小时数。你还提到要优先考虑有更多经验的志愿者，因此听起来你是在说“一些志愿者比其他人更受欢迎”。

这是一个经典的二分匹配问题。例如，请参见Steven Skiena的《算法设计手册（第2版）》第498页。基本方法是构建一个图形，其中顶点表示志愿者集合和您要填充的时间段集合。边将志愿者链接到有效的时间段。最佳解决方案是最大可能的边集合，其中没有志愿者或时间段重复。这是一个匹配。

你的一些志愿者可能能够做更多的时间段；这可以通过多次复制该志愿者顶点来模拟。

如果你想实现志愿者的优先排序，那么这将有效地为每个边缘添加加权，模拟该志愿者对该任务的经验。在这种情况下，就像你所想的那样，你需要类似匈牙利算法的东西。如果你可以不用它，那么你可以将问题转化为一个等效的流图，并应用网络流算法。这里是一个实现加权和非加权匹配的代码示例。

如果你想要更多细节，包括其他选择以及更多实现链接，我强烈建议你获取Algorithm Design Manual - 它是一个非常清晰和实用的参考资料。