匈牙利算法和多因素
我遇到一种情况，我需要将人员分配给多个事件。 如果我们只将价格作为一个因素，那就没问题，但是有很多因素需要考虑。
首先，一些背景。 这是为一个非营利组织提供的，该组织为因任何原因住院的儿童提供故事时间，因此他们依靠志愿工作来做到这一点。 因此，由于他们依赖人们的善意，所以他们给人们尽可能多的工作，人们可以/想要做，这些工作各不相同：
- 有些人只能做早上，有些人只能做下午；
- 有的人只能周一、周四去，有的人八月、十二月就不能去；
- 有些人每个月只能去一次，其他人可以去 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
这将是在所有操作之间进行相应分配的方法人，优先考虑那些可以多次完成此操作的人。
你怎么想？你会怎么做？
I have a situation where I need to allocate people to several events. If we just had a price as a factor, it would be fine, but there is a number of factors that come in.
First, some background. This is for a non-profit organization that promotes story hours for children that are hospitalized for any reason, so they depend on voluntary work to do so. So, since they rely on people's good will, they give people as much work as people can / want to do, which varies like:
- Some people can only do mornings, and some other people can only do afternoons;
- Some people can only do Mondays, and Thursdays, other people can't go on August or December;
- Some people can only go once a month, other people can go 4 times (and even other people are given "priority" in these actions because they're more experienced and can are available to do 10 times a month)
So, I kinda figured out the first two. Since the Hungarian Algorithm is about price, I'd give them a stupidly high price for the times they can't go. However, how would you do the others?
I thought about giving them some sort of score. Something along the lines of: one person who can do this once a month costs something like 1000 points. If someone can go 10 times a month, that person costs 100 points (1000 basis dividing by 10). Also, the way to distribute this would be to increase the price whenever a separate action would be done, like so (selected people have a * on their associated cost):
First iteration
| August 1st 2009
Person A | 1000
Person B | 500 *
Second iteration
| August 8th 2009
Person A | 1000 *
Person B | 1000
This would be the way to distribute accordingly between all the people, giving more priority to those that can do this several times.
What do you think and how would you do it?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是一个调度/优化问题，因此关键问题是“您想要最大化多少数量”？ 我猜您希望在不发生冲突的情况下最大化所有志愿者的工作总小时数，但要遵守每个志愿者的时间表限制。 您还提到优先考虑经验丰富的志愿者，所以听起来您是在说“某些志愿者比其他志愿者更受欢迎”。
这就是一个经典的二分匹配问题。 请参阅 Steven Skiena 的算法设计手册（第二版）的egp498。 基本方法是构建一个图，其中的顶点代表志愿者组和您尝试填充的时间段组。 边缘将志愿者与有效的时间段联系起来。 最佳解决方案是最大可能的边缘集，其中没有重复的志愿者或时隙。 这是一个匹配。
您的一些志愿者可能能够完成多个任务； 这可以通过多次复制该自愿顶点来建模。
如果您想对志愿者进行优先级排序，那么这会有效地为每个边缘添加权重，从而对志愿者执行该任务的体验进行建模。 在这种情况下，正如您所想的，您将需要类似匈牙利算法的东西。 如果您可以摆脱这个问题，那么您可以将问题转换为等效的流程图，并且应用网络流算法。 以下是实现加权和未加权匹配的代码示例。
如果您想要更多详细信息，包括其他替代方案以及更多实现链接，我强烈建议您获取一份《算法设计手册》的副本 - 这是一本非常清晰且实用的参考。
This is a scheduling/optimisation problem, so the key question is "what quantity are you trying to maximise"? I'd guess you are looking to maximise the total number of hours worked across all your volunteers without clashes, subject to each volunteer's timetabling constraints. You also mention prioritising volunteers with more experience, so it sounds like you are saying "some volunteers are preferred over others".
This is then a classic bipartite matching problem. See e.g. p.498 of The Algorithm Design Manual (2nd ed.), by Steven Skiena. The basic approach is to construct a graph with vertices representing both the set of volunteers, and the set of time slots you are trying to fill. Edges link volunteers to valid time slots. The optimum solution is then the largest possible set of edges where no volunteer or time slot is repeated. This is a matching.
Some of your volunteers may be able to do more than one slot; this can be modeled by replicating that volunteer vertex multiple times.
If you want to implement the prioritising of volunteers, then this effectively adds a weighting to each edge, modeling the experience of that volunteer for that task. In this case, as you thought, you will need something like the Hungarian algorithm. If you can get away without this, then you can transform the problem into an equivalent flow graph, and apply a network flow algorithm. Here is one example of code that implements both weighted and unweighted matching.
If you want more details, including other alternatives, and more links to implementations, I do strongly recommend getting yourself a copy of the Algorithm Design Manual - it is an amazingly clear and practical reference.