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

李博扬 等:新型时空众包平台中的在线三维稳定匹配问题 3841

是永远存在的 [22] ,但是这个算法的解是不公平的.文献[23−25]提出了多种稳定婚姻的衡量指标,以此来求得更
公平的解.文献[26]提出算法来研究如何求出稳定婚姻的个数.稳定婚姻问题具有多种扩展版本,在其中一类扩
展中,男人和女人之间的偏序可以是不完整的 [27] 、或者偏序中存在并列 [28] 、或者既不完整又存在并列 [29] .虽然
这些研究都可以获得稳定匹配的结果,但这些问题都关注与二维的稳定匹配,不能推广到三维匹配问题,且不具
备处理在线场景的能力.

3 基础算法

本节中,我们提出一个基于贪心的基础算法.由于不能准确获知工人和用户的到达顺序和地理位置,我们采
用延迟匹配的思想,当用户提出的任务到达最长等待时间时,开始对任务进行处理.对于用户来讲,合适的工人
可能出现在任务发布之后的某一时刻,所以当任务过期之前的所有时刻,都可能出现合适的工人.因此在延迟匹
配的过程中,尽可能为用户扩大候选的工人集合,从而提高匹配的效果.在匹配过程中,根据用户到工作点的距
离由近及远地遍历每个闲置的工作点;对于每个工作点,再根据距离遍历每个未匹配的工人.一旦找到满足稳定
的元组,那么将该元组作为用户的匹配结果.
延迟匹配算法的伪代码如算法 1 所示.算法的输入是动态到达的用户集 U 和工人集 W 以及静态的工作点
集 P,算法的输出是任务的匹配结果集 M,其中的每一个元素都是稳点元组.在初始状态,匹配结果 M 为空(第 1
行),将所有工作点设置为闲置状态(第 2 行).对于时刻 t,取出已经到达最长等待时间的用户集 U t 和已经到达且
未被分配任务的工人集 W t (第 3 行、第 4 行).对于 U t 中的每个用户 u,根据 D u 由近及远地查找每个闲置工作点
p,再根据 DW p 由近及远地查找 W t 中的工人 w,一旦(w,u,p)构成一个稳定元组,那么将(w,u,p)作为一个分配结果
加入到 M 中,将 w 从 W t 和 W 中移除,并将 p 被更新为占用状态,也将从 P t 中移除(第 5 行~第 19 行).每个被处理
过的用户,不论是否被匹配,都将从 U 中移除(第 19 行).因为如果这个用户没有被匹配,也到达了最长等待时间,
用户的任务也会过期.当循环结束时,当前时刻需要被匹配的用户都已被处理,算法将为下一时刻的用户进行匹
配(第 21 行).
算法 1. 延迟匹配算法.
输入:用户集 U,工人集 W,工作点集 P;
输出:全局任务匹配结果集 M.
1. M=∅;
2. 所有工作点处于闲置状态
3. For (当前时刻 t)
4. 取出到达最长等待时间的用户集 U t 、当前未分配任务的工人集 W t 、当前闲置的工作点集 P t
5. For (每一个在 U t 的用户 u)
6. For (每一个工作点 p∈D u 并且 p∈P t )
7. For (每一个工人 w∈DW p 并且 w∈W t )
8. If ((w,u,p)是稳定的)
9. 将(w,u,p)加入到 M
10. 将 w 从 W t 和 W 中移除
11. 更新 p 为占用状态
12. break;
13. End if
14. End for
15. If (p 被更新为占用状态)
16. 将 p 从 P t 中移除
17. break;