| 应用于测试资源匹配的婚姻稳定算法改进 |
| |
| 引用本文： | 孙昱,付少波,张天培,李长安.应用于测试资源匹配的婚姻稳定算法改进[J].河北工业大学学报,2009,38(3). |
| |
| 作者姓名： | 孙昱 付少波 张天培 李长安 |
| |
| 作者单位： | 1. 军事交通学院,基础部,天津,300161
2. 天津三环电子仪器仪表有限公司,研发部,天津,300161 |
| |
| 摘 要： | 下一代自动测试系统中将实现测试资源的动态分配,我们使用婚姻稳定(Stable Marriage)算法来解决测试过程中测试资源与被测设备的匹配问题,本文中使用择偶倾向队列缩减模型对求解典型"婚姻稳定"问题的Gale-Shapley(G-S)算法进行优化.该模型中使用择偶倾向队列描述婚姻稳定问题中匹配优先顺序,该队列会随着算法进行逐渐缩短,在简化数据规模的同时优化了处理婚姻稳定问题的G-S算法处理流程,改进后算法实现无效匹配请求的预先清除,从而使用后来请求优先的原则对匹配请求进行处理机制,对原有算法的时间空间成本实现了优化,适应了测试资源匹配任务的需求.
|
| 关 键 词： | 自动测试系统 通用性 稳定婚姻问题 算法优化 二部分图 |
An Optimize for Gale-shapley Algorithm in Stable-marriage Problem Applying in ATS Resource Matching |
| |
| SUN Yu,FU Shao-bo,ZHANG Tian-pei,LI Chang-an.An Optimize for Gale-shapley Algorithm in Stable-marriage Problem Applying in ATS Resource Matching[J].Journal of Hebei University of Technology,2009,38(3). |
| |
| Authors: | SUN Yu FU Shao-bo ZHANG Tian-pei LI Chang-an |
| |
| Affiliation: | 1.Department of General Courses;Academy of Military Transportation;Tianjin 300161;China;2.Tianjin Trilink Electronic and Instrument Company;China |
| |
| Abstract: | 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 running,along with the briefs of data it brings optimization in G-S procession.The improved method will decline the use the sequence red... |
| |
| Keywords: | ATS universal-apply stable-marriage optimize bigrcm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
