应用于测试资源匹配的婚姻稳定算法改进  

An Optimize for Gale-shapley Algorithm in Stable-marriage Problem Applying in ATS Resource Matching

作　　者：孙昱[1] 付少波[1] 张天培 李长安[1] 

机构地区：[1]军事交通学院基础部,天津300161 [2]天津三环电子仪器仪表有限公司研发部,天津300161

出　　处：《河北工业大学学报》2009年第3期72-76,共5页Journal of Hebei University of Technology

摘　　要：下一代自动测试系统中将实现测试资源的动态分配,我们使用婚姻稳定(Stable Marriage)算法来解决测试过程中测试资源与被测设备的匹配问题,本文中使用择偶倾向队列缩减模型对求解典型"婚姻稳定"问题的Gale-Shapley(G-S)算法进行优化.该模型中使用择偶倾向队列描述婚姻稳定问题中匹配优先顺序,该队列会随着算法进行逐渐缩短,在简化数据规模的同时优化了处理婚姻稳定问题的G-S算法处理流程,改进后算法实现无效匹配请求的预先清除,从而使用后来请求优先的原则对匹配请求进行处理机制,对原有算法的时间空间成本实现了优化,适应了测试资源匹配任务的需求.In the next Generation ATS the testing resource will be allocated dynamically, we describe this with Stable- Marriage （S-M） problem, in the text we optimize the Gale-Shapley （G-S） algorithm with a mate sequence decline model. This model describes the relationships of probable mates with a mate sequence, and characteristic with clear structure. The mate sequence will declines while rttrming, along with the briefs of data it brings optimization in G-Sprocession. The improved method will decline the use the sequence reduction unable matching request, and process the S-M with a later better principle. This optimizes makes improvement in time and space cost compared with original G-S, consequently content the task of resource matching.

关 键 词：自动测试系统 通用性 稳定婚姻问题 算法优化 二部分图 

分 类 号：TP274[自动化与计算机技术—检测技术与自动化装置]