匈牙利算法和多因素 [英] Hungarian Algorithm and multiple factors
问题描述
我有一个情况我需要分配人几个事件。如果我们只是有一个价格的一个因素，这将是罚款，但有一些是进来的因素。
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:
- 在有些人只能做早晨，和其他一些人只能做下午;
- 在一些人只能做星期一和星期四，其他人不能再继续下去八月或十二月;
- 在有些人一个月只去一次，其他人可以去4次（甚至其他人都给予优先权的这些行动，因为他们更有经验，可以提供给做了一个月10次）
所以，我有点想通了第2位。由于匈牙利算法是关于价格，我想给他们一个愣神高的价格时候，他们不能去。但是，你会怎么做别人？
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?
我想过给他们某种得分。线沿线的东西：一个人谁可以一个月做一次，费用有点像1000点。如果有人能去10次一个月，那个人花费100分（1000分的基础由10）。此外，分发这种方式是增加每当一个单独的行动将完成，像这样（所选择的人有一个*在其相关的成本）价格：
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):
| August 1st 2009
Person A | 1000
Person B | 500 *
第二迭代
| 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?
推荐答案
这是一个调度/优化问题，所以关键的问题是你想最大限度地发挥多少数量？我猜你正在寻找最大化，而不冲突在所有的志愿者工作时间，受到每个志愿者的时间表限制的总数。你还别说有更多经验的优先考虑志愿者，所以它听起来像你说：一些志愿者的 preferred 比别人。
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.
如果要实现志愿者的优先次序，那么这有效地增加了一个权重，以每条边，造型的志愿者为这项任务的经验。在这种情况下，你想，你就需要像匈牙利算法。如果你能逃脱如果没有这个，那么你就可以把这个问题转化为等价流图，并应用网络流算法。这里是 code同时实现加权和不加权匹配的一个例子。
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.
这篇关于匈牙利算法和多因素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
