偏好序阈值约束下的三边单向非循环稳定匹配  

A Three-sided Unidirectional Acyclic Stable Matching with Thresholds of Preference Order

作　　者：杨洋[1,2] 赵晓冬[1] YANG Yang;ZHAO Xiaodong(College of Economics and Management,Yanshan University,Qinhuangdao 066004;Liren College,Yanshan University,Qinhuangdao 066004)

机构地区：[1]燕山大学经济管理学院,秦皇岛066004 [2]燕山大学里仁学院,秦皇岛066004

出　　处：《系统科学与数学》2020年第8期1420-1431,共12页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金青年科学基金(61403335);教育部人文社会科学青年基金项目(19YJCZH234);河北省社会科学基金年度项目(HB19GL009);河北省自然科学基金资助项目(F2018203370)资助课题。

摘　　要：文章针对单向非循环偏好下的三边匹配问题,提出了一种基于偏好序阈值约束条件下的匹配算法.首先,基于单向非循环偏好结构,给出了三边单向非循环匹配及其稳定性的有关定义,并建立了一对一情形下满足系统稳定性需求的数学模型;然后,通过设置偏好序阈值对模型进行约束限制,提出了偏好序阈值约束下的两阶段逐边优选算法,并分别对该算法的时间复杂度及输出匹配的稳定性进行了计算和证明.最后,通过一个算例验证文章所提算法的可行性和有效性.Aiming at three-sided matching problems with unidirectional acyclic preferences,a matching algorithm based on thresholds of preference order is proposed in this paper.First,based on the unidirectional acyclic structure,the definition of threesided unidirectional acyclic matching and its stability are given,and the mathematical model to meet the stability requirements of the system is established.Second,thresholds of preference order are set to constrain the model,an edge-by-edge optimization algorithm in two stages with thresholds of preference order is proposed,and the time complexity of the algorithm and the stability of the output scheme are calculated and proved respectively.Finally,an example is given to verify the feasibility and effectiveness of the proposed algorithm.

关 键 词：三边匹配 非循环偏好 稳定性 偏好序 时间复杂度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]