结对编程的分配问题

现实世界:

公司高层学到了结对编程(pair programming)这个概念. 对于每一个任务, 要保证有两个程序员同时在编. 于是此高层下令任何任务必须有两个程序员同时在写. 一个任务要么两个程序员在做, 要么没有人做. 每个任务只能被分配给拥有解决这个任务的能力的程序员. 那么是否可以保证至少k个任务被分配出去呢?

可以得到下面的一个问题:

给一个二分图
. 找到一个”匹配”
, 使得在

里,

1. 每一个A的顶点 , . 且 的顶点至少有k个.

2. 每一个B的顶点 , .

t=1的时候, 是常见的二分图匹配问题.

t=2的时候, 就是我们要解决的问题.

t=3的时候, 这个问题是3-dimensional matching, 是NP-hard的. 所以还好没有什么trio programming…

那么t=2的时候问题可以多项式时间解么? 另一个同样的描述方法, 是找到k个的vertex disjoint的 , 使得center在A里面. 一般人会猜这个是NP-hard的问题. 因为如果同样的问题, 不要求center在A里面的话, 那就是NP-hard的 .

这个问题是可以多项式时间解答的. 可以规约到最大权值完美匹配.

方法如下.

创建一个新的图 . 假设 .

, 是一个有 个新顶点的集合.

对于每一个 , 有一个边 , 权值0.

对于每一个 , 有边 和 ,权值都为1.

对于每一个 , 有边 , 权值为0.

原来的问题有解, 有且仅有在 上的最大权值完美匹配的值为 .

原先的问题的有权值的版本也能用类似的方法做出来.

现实世界:

由于结对编程导致程序员强烈不满, 高层允许梨子编程(pear programming).

稿源:算法屠龙术 (源链) | 关于 | 阅读提示

本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 综合编程 » 结对编程的分配问题

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录