12.29 任务分配算法

下面介绍如何将合适的工作分配给正在请求任务的工人 W。采用的思路是首先对每一个任务，都考虑如果将 W 中的某些工人安排给它，它的准确率会有多少提升；然后选择为每个工人选择最优的 h个任务，以最大化地提升准确率。

准确率估算 : 在推断模型中，P(z t,k ) 被用来推断 l t,k 的真实结果。如果 l t,k 的真实结果是 1，那么推断的准确率就是 P(z t,k =1)；如果真实结果是 0，那么推断的准确率就是 P(z t,k =0)。因此，需就真实结果是 1 或者 0 两种情况考虑准确率。但两者相似，为简化描述，统一由 Acc t,k 来表示准确率。在任务分配过程中，如果任务 t 被安排给一组新的工人集合，记为 W(t) W，由于 t 的答案改变了，Acc t,k 就会产生改变。记 Acc t,k (W(t)) 为考虑加入工人 W(t)的答案后的改变的 t 准确率。 通过推断模型的公式演算，可以证明 W(t) 中任务被安排给工人的不同顺序对准确率不会产生影响，并且 Acc t,k (W(t)) 可以在线性时间内计算获得。

最优任务分配 : 对正在请求任务的工人集合 W，目标是寻找一个分配方法来最大化期望准确率的提升。即寻找分配以最大化 ∆Acc t,k (W(t))。可以证明这一最大化问题是 NP-hard 的，由此，采用贪心算法来进行任务分配。贪心的过程是每次选择能够最大化期望准确率的〈工人，任务〉，将任务安排给该工人，不停选择直到为每个工人分配 h 个任务。