Page 176 - 《软件学报》2020年第12期

3842 Journal of Software 软件学报 Vol.31, No.12, December 2020

18. End if
19. End for
20. 将 u 从中 U 移除
21. End For
22. End for
例 4:如例 3 中的出现序列和坐标,假设每个用户的等待时间为 2 个时间段,算法 1 的执行过程和匹配结果
如图 4 所示.首先,在 t 2 时刻,u 1 到达最长等待时间.此时可服务的工人为 w 1 和 w 2 ,算法执行的匹配元组是
(w 1 ,u 1 ,p 6 ),如图 4(a)所示.在 t 4 时刻,u 2 到达最长等待时间,此时可服务的工人为 w 2 和 w 3 ,p 6 是被占用状态,算法执

行的匹配元组是(w 2 ,u 2 ,p 1 ),如图 4(b)所示.在 t 6 时刻,u 3 到达最长等待时间,此时可服务的工人为 w 3 和 w 4 ,p 1 和 p 6
是被占用状态,算法执行的匹配元组是(w 3 ,u 3 ,p 2 ),如图 4(c)所示.在 t 8 时刻,u 4 和 u 5 到达最长等待时间,此时可服务
的工人为 w 4 和 w 5 , p 1 、p 2 和 p 6 是被占用状态.由于 p 1 和 p 2 都被占用,无论当前怎么组合,算法都无法找到稳定
元组,如图 4(d)所示.在 t 11 时刻,u 6 到达最长等待时间,此时可服务的工人为 p,w 5 和 w 6 ,p 1 ,p 2 和 p 6 是被占用状态,
算法执行的匹配元组是(w 6 ,u 4 ,p 5 ),如图 4(e)所示.图 4(f)描述了该算法最终的匹配结果,成功匹配 4 个稳定元组.
任务匹配率为 66.67%.
y y y
9 9 9
8 u 1 8 8 p 6
7 p 6 7 p 6 7 p 4
w 2 p 5 p 4 w 2 p 5 p 4 p 5
6 w 1 6 6
w 3 w 3
5 p 3 5 u 2 p 3 5 p 3
4 4 u 3 4 u 3
3 u 2 p 1 p 2 3 p 1 3 p 1 p 2
2 2 p 2 2 w 4 u 5
1 1 1
u 4
12 3 4 5 678 9 10 x 1 2 3 4 5 6 78 9 10 x 1 2 3 4 5 6 7 89 10 x
(a) t 2:u 1 到达最长等待时间 (b) t 4:u 2 到达最长等待时间 (c) t 6:u 3 到达最长等待时间
y y y
9 9 w 6 9
8 8 8 w 6 u 1
p 6 u 6 p 6 p 5
7 7 7 p 6
p 5 p 4 p 5 p 4 w 2
6 6 6 u 6 w 3 w 1
5 5 5 p 4
p 3 p 3 p 3
4 4 4 u 3
3 3 3 u 2
p 1 p 2 p 1 p 2 p 1
2 2 2
w 4 u 5 w 4 w 5 w 4 u 5
1 1 1 p 2
u 4 w 5 u 4 w 5
12 3 4 5 67 89 10 x 1 2 34 56 7 8 9 10 x 1 2 3 4 5 67 89 10 x
(d) t 8:u 4 和 u 5 到达最长等待时间 (e) t 11:w 5 到达最长等待时间 (f) 最终匹配结果
Fig.4 Execution process of the delay matching algorithm
图 4 延迟匹配算法的执行过程

算法复杂度分析:算法每个时刻需要执行一次,每次需要遍历用户集 U t 、工人集 W t 和工作点集 P,复杂度是
O(|U t |×|W t |×|P t |),最差情况的复杂度为 O(|U|×|W|×|P|).综上,延迟匹配算法的复杂度 O(|U|×|W|×|P|) .算法需要记录
3 种对象的信息,分别记录用户和工作点之间、工人和工作点之间的距离,空间复杂度为 O(|U|×|P|+|W|×|P|).

4 改进算法

在上一节中提出了延迟匹配算法.延迟匹配算法以距离为核心,优先查找相近的任务点和工人.虽然该算法
可以求出一定数量的稳定匹配,但是由于它无法预知将来时刻工人和用户的分布,仅根据当前到达情况进行匹