一种最优校准的分组算法  

A Grouping Algorithm of Optimal Alignments

作　　者：田银花[1,2] 杜玉越[1] 

机构地区：[1]山东科技大学信息科学与工程学院,山东青岛266590 [2]山东科技大学信息工程系,山东泰安271000

出　　处：《山东科技大学学报（自然科学版）》2015年第1期29-34,共6页Journal of Shandong University of Science and Technology(Natural Science)

基　　金：国家自然科学基金项目(61170078;61472228);教育部高等学校博士学科点专项科研基金博导类项目(20113718110004);青岛市科技计划基础研究项目(13-1-4-116-jch);山东科技大学科研创新团队支持计划项目(2011KYTD102)

摘　　要：为了选取最优校准的代表项简化迹与模型的一致性检查,提出一种基于质数权值的分组算法,实现对所有最优校准的分组。给不同的偏差分配互异的质数权值,将权值之积作为最优校准的代价。包含相同移动多重集但移动出现位置不同的相似最优校准具有相同的代价。证明了分组算法的正确性,应用实例描述了分组的具体执行过程。算法首次明确简洁地实现了相似最优校准的分组,时间复杂度为O(m2 n2)。In order to select the representatives from optimal alignments and simplify the conformance checking be- tween the trace and the model, a grouping algorithm based on prime weights was presented to group all the optimal alignments. The different prime weights were allocated to the deviations,and the products of the weights were taken as the costs of optimal alignments. Thus the similar optimal alignments with the same multiset of movements but dif- ferent ordering shared the same cost. The correctness of this algorithm was proved and the specific implementation process was illustrated. The explicit and succinct grouping of similar optimal alignments was realized for the first time and the time complexity proves to be O（m2n2 ）.

关 键 词：迹 PETRI网模型 最优校准 质数权值 分组算法 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]