分配问题

来自计算思维百科
跳转至: 导航搜索
分配问题1.png

N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数最小?

解决方案

我们以3个人分配3个人为例,如下表格,对应着每个人分配不同任务时的成本;

 

任务A

任务B

任务C

人员1

9

2

7

人员2

6

4

3

人员3

5

8

1

方案1-穷举解决分配问题

思想:利用穷举法则是把三个人对应三个任务的所有组合列出来求总成本,然后找出总成本最小的。对于3人3个任务的情况,我们容易得到共有3!=3x2x1=6种分配方案:

Plan1: 人员1→任务A    人员2→任务B    人员3→任务C    cost=9+4+1=14

Plan2: 人员1→任务A    人员3→任务C    人员3→任务B    cost=9+3+8=20

Plan3: 人员1→任务B    人员2→任务A    人员3→任务C    cost=2+6+1=9

Plan4: 人员1→任务B    人员2→任务C    人员3→任务A    cost=2+3+5=10

Plan5: 人员1→任务C    人员2→任务A    人员3→任务B    cost=7+6+8=21

Plan6: 人员1→任务C    人员2→任务B    人员3→任务A    cost=7+4+5=16

因此,我们应该选择方案3,所花费的总成本最小。

方案2-分支界限法解决任务分配问题

我们以4个人分配4个人为例,如下表格,对应着每个人分配不同任务时的成本;

 

任务A

任务B

任务C

任务D

人员1

9

2

7

8

人员2

6

4

3

7

人员3

5

8

1

8

人员4

7

6

9

4

解法:

对于此例来说,我们可以求出最小的成本(不考虑约束条件时),那我们可以得到2+3+1+4=10,这个解不是合法的(3和1在同一列),可以肯定的一点是产生的所有合法解都不可能小于这个值。我们从人员1开始,计算出人员1选择不同任务时对应方案的最优边界值,如图:

开始start没有分配任务时,对应的最小成本为10;当人员1的任务确定时,求其他人的任务不可以与人员1的重复时的最优边界值即10;

分配问题2.png

确定了人员1的任务为B,我们继续确定人员2的任务在A、C、D中选择,求出三种选择对应的边界值,此时我们需要在1,、3、4、5、6、7分支中选择最有希望获得最优解的,即5分支,把任务B分配给2;

分配问题3.png

接下来,人员3和4就只有两种选择,

分配问题4.png

如下,我们可以得到最优分配方案,即

人员1→任务B     人员2→任务A    人员1→任务C    人员1→任务D

涉及到的计算思维

任务分配问题可以采用穷举法来解决,其中体现的就是计算思维的机械化特点;也可采用分支界限法来解决,分支界限法体现的则体现了计算思维中的优化特点。