应用于测试资源匹配的婚姻稳定算法改进第38卷Vl0l-38第3期NO.3河北工业大学JOURNALOFHEBEIUNIVERSITYOFTECHNOLOGY2009年6月June2009文章编号:1007.2373(2009)03—0072—05应用于测试资源匹配的婚姻稳定算法改进孙昱,付少波,张天培,李长安(1.军.j交通学院基础部,天津300161:2.天津三环电子仪器仪表有限公司研发部,天津300161)摘要下一代自动测试系统中将实现测试资源的动态分配,我们使用婚姻稳定(StableMarriage)算法来解决测试过程中测试资源与被测设备的匹配问题,本文中使用择偶倾向队列缩减模型对求解典型'婚姻稳定"问题的Gale—Shapley(G—S)算法进行优化.该模型中使用择偶倾向队列描述婚姻稳定问题中匹配优先页序,该队列会随着算法进行逐渐缩短,在简化数据规模的同时优化了处理婚姻稳定问题的G,s算法处理流程,改进后算法实现无效匹配请求的预先清除,从而使用后来请求优先的原则对匹配请求进行处理机制,对原有算法的时间空间成本实现了优化,适应了测试资源匹配任务的需求.关键词自动测试系统;通用性;稳定婚姻问题;算法4L4~;二部分图中图分类号TP274文献标识码AAnOptimizeforGale--shapleyAlgorithminStable--marriageProblemApplyinginATSResourceMatchingSUNYu,FUShao-b0,ZHANGTian.pei,LIChang—an(1.DepartmentofGeneralCourses,AcademyofMilitaryTransportation,Tianjin300161,China;2.TianjinTrilinkElectronicandInstrumentCompany,Tianjin300161,China)AbstractInthenextGenerationATSthetestingresourcewillbeallocateddynamically,wedescribethiswithStable-Marriage(S-M)problem,inthetextweoptimizetheGale—Shapley(G—S)algorithmwithamatesequencedeclinemode1.Thismodeldescribestherelationshipsofprobablemateswithamatesequence,andcharacteristicwithclearstructure.Thematesequencewilldeclineswhilerutming,alongwiththebriefsofdataitbringsoptimizationinG—Sprocession.Theimprovedmethodwilldeclinetheusethesequencereductionunablematchingrequest,andprocesstheS-Mwithalaterbe~erprinciple.ThisoptimizesmakesimprovementintimeandspacecostcomparedwithoriginalG—S,consequentlycontentthetaskofresourcematching.KeywordsATS;universal?-apply;stable--marriage;optimize;bigrcm0引言婚姻稳定问题是Gale和Shapley在1962年提出的一种解决二部分图匹配问题的模型.在婚姻稳定问题的数学模型中对匹配双方的匹配需求倾向分别予以描述.使用婚姻稳定问题进行匹配过程具有双向选择的特点,可以用于描述劳动力与工作岗位的问题,在自动测试领域测试仪器与被测设备的分配组合问题与之类似,因此我们将婚姻稳定问题应用其中.典型的婚姻稳定问题可以描述为,有Ⅳ位男性和Ⅳ位女性每个人对于异性的喜爱程度都有一个严格的顺序,二部分图匹配连接男性和女性,不稳定匹配是指在匹配M中某一男性m对某一女性的匹配倾向程度高于其当前配偶,同时对m的倾向程度高于其当前配偶.当M中不存在这样的不稳定匹配时M即为婚姻稳定问题的一个解….收稿日期:2009—02—28作者简介:孙昱(1978一),男(汉族),硕士第3期孙昱,等:应用于测试资源匹配的婚姻稳定算法改进Gale.Shapley(G—S)算法是解决婚姻稳定f.q题的一种典型方法,G—s算法通过求婚一拒绝的匹配请求处理方式来完成匹配,即每个男性按照自己择偶倾向程度由高到低依次向每个女性提出匹配请求直到被接受,女性则是根据自身的择偶倾向对男性的请求进行处理,未处于匹配之中的女性会接受任何一个男性提出的匹配请求,在女性处于匹配对中的情况下如果当前向她求婚的配偶比现有配偶的顺位更高则更换当前配偶,否则不予理睬.如此循环往复直到所有人都有配偶为止.通用测试端IZl适配器的设计过程中涉及到的信号数量众多,与之相对应的婚姻稳定算法需要处理的元素数量也随之增加,这就会出现算法处理速度慢,运行效率低的问题.因此需要对现有算法进行改进达到提高运算效率的目的H.注意到G.s算法中男性按照自己的择偶倾向由高到低向女性提出匹配请求,女性则是逐渐接受排序更高男性提出的匹配请求.最终匹配形成的时候男性的配偶顺位不会再降低,女性...