偏好序阈值约束下的三边单向非循环稳定匹配
A Three-sided Unidirectional Acyclic Stable Matching with Thresholds of Preference Order
文章针对单向非循环偏好下的三边匹配问题, 提出了一种基于偏好序阈值 约束条件下的匹配算法. 首先, 基于单向非循环偏好结构, 给出了三边单向非循环匹 配及其稳定性的有关定义, 并建立了一对一情形下满足系统稳定性需求的数学模型; 然后, 通过设置偏好序阈值对模型进行约束限制, 提出了偏好序阈值约束下的两阶段逐 边优选算法, 并分别对该算法的时间复杂度及输出匹配的稳定性进行了计算和证明. 最 后, 通过一个算例验证文章所提算法的可行性和有效性.
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 three-sided 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.
/
〈 | 〉 |