不一致术语集最小基数诊断的分支限界  

Branch and bound for computing the cardinality-minimal diagnosis of incoherent terminology

作　　者：欧阳丹彤[1,2] 高杰 OUYANG Dan-tong;GAO Jie(Collge of Computer Science and Technology,Jilin University,Changchun 130012,China;Key Laboratory of Symbolic Compualion and Knorwledge Engineering,Ministry of Education,Jilin Universiy,Changchun 130012,China)

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学符号计算与知识工程教育部重点实验室,长春130012

出　　处：《吉林大学学报（工学版）》2020年第4期1449-1454,共6页Journal of Jilin University:Engineering and Technology Edition

基　　金：国家自然科学基金项目(61672261,61502199,61872159)。

摘　　要：针对不一致术语集的最小基数诊断,提出了一种分支限界的方法,该方法根据不相交极小不一致保持子术语集(MIPS)覆盖来定义诊断的一个下界,并且使用分支技术将大问题分解为多个可并行执行的子问题。实验结果表明,该方法能够快速有效地计算出一个最小基数诊断。For minimal cardinality diagnosis of incoherent terminology,this paper proposes a branch and bound method to calculate a cardinality-minimal diagnosis. This method defines a lower bound of diagnosis based on the disjoint Minimal Incoherent Preserving-Subset(MIPS) cover. Then,it uses branching technique to break a large problem into multiple sub-problems that can execute in parallel. The experimental results show that the method can quickly and efficiently calculate a cardinality-minimal diagnosis.

关 键 词：计算机应用 最小基数诊断 极小不一致保持子术语集 分支 限界 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]