Page 495 - 《软件学报》2025年第7期

3416 软件学报 2025 年第 36 卷第 7 期

同理, 为了对任务的数据进行剪枝, 有定理 6.
定理 6. 给定质量和重要性从大到小排序后的工人和任务集合, 从最小重要性的任务开始剪枝, 每次剪枝从做
了该任务最小质量的工人开始, 如果满足公式 (30), 则停止剪枝.
证明: 对于第 n U n , 那么对该任务来说总的误差为:
个任务, 做了该任务的集合为
 √ 
1 ∑  d 2 −d 1 2 1  

MAE n ≈    +    (30)
|U n |  ε/|M s | π w 2 
s
s∈U n
假设集合中工人质量最小的工人编号为 l, 排除掉第 l 个工人的总误差为:

 √ 
1 ∑  d 2 −d 1 2 1  

MAE n − ≈    +    (31)
|U n |−1  ε/|M s | π w 2 
s∈U n \{u l } s
d 2 −d 1
如果第 l 个值不被剪枝, 也就是说加上该值后误差变小, 那么令 MAE n ⩾ MAE n −, 同时引入辅助变量 z s =
ε/|M s |
√
2 1
+ , 那么:
π w 2 s
1 ∑ 1 ∑
MAE n − MAE n − = z s − z s
|U n | |U n |−1
s∈U n s∈U n \{u l }
|U n |−1 ∑ |U n | ∑
= z s − z s
|U n |(|U n |−1) |U n |(|U n |−1)
s∈U n s∈U n \{u l }
∑ ∑ ∑
∝ (|U n |−1) z s −|U n | z s = |U n |z l − z s
s∈U n s∈U n \{u l } s∈U n
 √ ( ) 
1 ∑  (d 2 −d 1 )(|M l |−|M s |) 2 1 1  

=    + −    (32)
|U n |  ε π w 2 w 2 
s∈U n l s
因此, 如果

 √ ( ) 
1 ∑  (d 2 −d 1 )(|M l |−|M s |) 2 1 1  

  ⩾ 0

 + − (33)
 
 2
|U n | ε π w w 2 
s∈U n l s
那么就停止剪枝.
(3) 自适应剪枝 (UAP) 算法流程
基于以上剪枝条件得到如下算法 2 流程. 首先进行初始化 (第 1, 2 行); 其次, 为每个任务分配至少一个值 (第
3–6 行); 再者, 优先给重要任务分配高质量的工人, 能提高真值发现的效用; 最后分别对工人 (第 7–9 行) 和任务
(第 10–12 行) 进行剪枝. 特别地, 由于某个任务不存在对应的提交值的话, 那么便无法得到该任务对应的“真值”,
进而导致真值发现失败. 因此采用本文算法能避免真值发现失败.
算法 2. 自适应剪枝 (UAP) 算法.
输入: 任务重要性矩阵 Y; 数据矩阵 X; 工人质量矩阵 W;
输出: X.
1) 对工人的质量 W 由大到小排序并对应更新 X;
2) 对任务的重要性 Y 由大到小排序并对应更新 X;
3) for (n=1 to N) do
t n 从 X 中从上到下选择最近一个值;
4) 对任务
5) 在 X 中保留相应的值;
6) end for
7) for (s=1 to M) do