1

我正在尝试为以下问题找到有效的解决方案：

问题：假设我有一些任务（A、A、B、B、C）并且我有一些人可以执行以下一项或多项任务：

  • 人1：A，B（人1可以做任务A或任务B）
  • 人2：A，C
  • 人3：A
  • 人4：B，C
  • 人5：A，B

是否可以将我所有的任务交给这些人？一个人只能完成一项任务。

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

我第一次尝试有效地解决这个问题是：

  • 如果一个人只能完成一项任务，则将该任务分配给该人
  • 如果一项任务需要完成 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

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

感谢您阅读：）

4

2 回答 2

1

一种有效解决此问题的方法是将其表述为最大流量问题。

在人员和他们可以完成的任务之间添加边界（容量 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)
于 2013-10-16T19:00:41.183 回答
0

Yes, there is an efficient algorithm for this. This is an instance of the maximum bipartite matching problem. What you do is you create a bipartite graphs where the nodes are people and tasks, and there is an edge connecting each person with each task they are able to perform. An assignment of people to tasks will correspond to a matching of this graph.

The algorithm for this isn't completely trivial, but it can be performed efficiently, for example: http://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/matching.pdf

于 2013-10-16T18:54:25.227 回答