算法：分发N个任务为k> n个人，每个人都可以执行这些任务的子集

问题描述：

我试图找到如下问题的一个有效的解决方案：算法：分发N个任务为k> n个人，每个人都可以执行这些任务的子集

问题：假设我有一些任务（A，A，B，B，C）和我有一些人谁可以执行这些任务中的一项或多项：

PERSON1：A，B（人1可以做任务A和任务B）
person2：A，C
person3：A
person4：B，C
person5：A，B

是否有可能放弃我所有的任务，这些人？一个人只能完成一项任务。

可能有多种解决方案，但我只想知道是否有解决方案。

我在有效地解决这个第一次尝试：

如果一个人所能做的只有1任务，该任务分配到人
如果任务需要完成n次，并有n可以执行此任务的人，将此任务分配给这n个人。

这足以解决上述问题。

2人可以做B，B需要做两次。
- 任务留给：A，A，C
- 人留下：[A，C]，[A]，[B，C]
2人能做到A.
- 任务左：C
- 者左：[B，C]

但它不足以解决像更复杂的问题：项工作：IGGGFFDDCCBBB 人数： ABCDEFG CEI BEI CEFGI CEGI ADGI CEGI CI ADG BEI DI BCDEFI ABDF ABEFG BCEGI ACDI BD ABE BCDEFGI

是有解决这个问题的有效方法吗？我明显可以用深度优先的搜索算法解决这个问题，但是我想知道如果我可以用多项式时间解决这个问题吗？我不禁相信这是一个众所周知的问题，但我一直无法在谷歌上找到它。

谢谢你的阅读:)

答

一种有效地解决这种方式是配制它作为一个maximum flow problem。

增加人与他们可以做的任务之间的边界（容量1）。

另外的开始，并且每个人（容量1）

以及任务和目标之间的边缘之间添加边缘（容量=要做的倍任务需要数）。使用NetworkX

例Python代码：

import networkx as nx 
from collections import Counter 

jobs = 'IGGGFFDDCCBBB' 
people = 'ABCDEFG CEI BEI CEFGI CEGI ADGI CEGI CI ADG BEI DI BCDEFI ABDF ABEFG BCEGI ACDI BD ABE BCDEFGI' 

G=nx.DiGraph() 
for person,tasks in enumerate(people.split()): 
    P = 'person'+str(person) 
    G.add_edge('start',P,capacity=1.0) # One person can do one thing 
    for task in tasks: 
     G.add_edge(P,'task'+task,capacity=1.0) # This person can do this task 

C = Counter(jobs) 
for task,count in C.items(): 
    G.add_edge('task'+task,'end',capacity=count) # Task appears count times in our job list 

print nx.max_flow(G,'start','end') >= len(jobs)

答

是的，这是一个有效的算法。这是最大二分配匹配问题的一个实例。你所做的是创建一个双向图，其中节点是人员和任务，并且每个人都有一条边连接他们可以执行的每个任务。将任务分配给任务将对应于该图的匹配。

的算法，这是不完全微不足道的，但它可以有效地执行，例如： http://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/matching.pdf

算法：分发N个任务为k> n个人，每个人都可以执行这些任务的子集

相关推荐