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

摘要：

下一代自动测试系统中将实现测试资源的动态分配,我们使用婚姻稳定(Stable Marriage)算法来解决测试过程中测试资源与被测设备的匹配问题,本文中使用择偶倾向队列缩减模型对求解典型"婚姻稳定"问题的Gale-Shapley(G-S)算法进行优化.该模型中使用择偶倾向队列描述婚姻稳定问题中匹配优先顺序,该队列会随着算法进行逐渐缩短,在简化数据规模的同时优化了处理婚姻稳定问题的G-S算法处理流程,改进后算法实现无效匹配请求的预先清除,从而使用后来请求优先的原则对匹配请求进行处理机制,对原有算法的时间空间成本实现了优化,适应了测试资源匹配任务的需求.

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

所属期刊栏目：38

分类号：TP274(自动化技术及设备)

在线出版日期：2009-07-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：72-76