基于动态极大元素覆盖值的极小碰集求解算法
|
摘要
在基于模型诊断(model-based diagnosis,MBD)中,因为所有极小冲突集的极小碰集就是待诊断系统的诊断结果,所以利用所有极小冲突集构造极小冲突集合簇,并基于极小冲突集合簇计算极小碰集是诊断的关键步骤.提出一种基于动态极大元素覆盖值求解极小碰集的新算法.该算法按照元素的元素覆盖值从大到小的顺序依次处理元素,并在求解碰集的过程中加入启发式策略和剪枝策略,使得搜索空间极大减少;利用邻接链表存储输入的极小冲突集合簇,邻接链表相对于用矩阵作为存储结构有较好的空间开销且通过邻接指向能快速地找到元素可以覆盖的集合簇中的元素;每得到一个碰集便使用极小碰集判定规则进行筛选,因此算法结束时可以产生而且仅产生所有的极小碰集.实验结果表明该算法有较高的计算效率.
The minimal conflict set cluster is constructed by all the minimal conflict sets.The minimal hitting sets of all the minimal conflict sets are the faults of the system to be diagnosed.Therefore,computing all the minimal hitting sets according to the minimal conflict set cluster is an important step in model based diagnosis.In this paper,a new algorithm is proposed to obtain all the minimal hitting sets by using dynamic maximum element coverage value.The algorithm processes elements in turn according to the descending order of the element coverage value.The search space can be greatly reduced by joining the corresponding heuristic strategy and pruning strategy in the process of solving the hitting sets.Adjacency list is used to store the minimal conflict set cluster in the algorithm.Among the basic storage structures,adjacency list has better space cost than matrix.Besides,the adjacent pointer can quickly find the elements in the minimal conflict set cluster which can be covered by an element.When a hitting set is obtained,the minimal hitting set is obtained by using the minimal hitting set decision rule.Therefore,the algorithm can generate and only generate all the minimal hitting sets.Experimental results show that the proposed algorithm has better computational efficiency than other algorithms.
The minimal conflict set cluster is constructed by all the minimal conflict sets.The minimal hitting sets of all the minimal conflict sets are the faults of the system to be diagnosed.Therefore,computing all the minimal hitting sets according to the minimal conflict set cluster is an important step in model based diagnosis.In this paper,a new algorithm is proposed to obtain all the minimal hitting sets by using dynamic maximum element coverage value.The algorithm processes elements in turn according to the descending order of the element coverage value.The search space can be greatly reduced by joining the corresponding heuristic strategy and pruning strategy in the process of solving the hitting sets.Adjacency list is used to store the minimal conflict set cluster in the algorithm.Among the basic storage structures,adjacency list has better space cost than matrix.Besides,the adjacent pointer can quickly find the elements in the minimal conflict set cluster which can be covered by an element.When a hitting set is obtained,the minimal hitting set is obtained by using the minimal hitting set decision rule.Therefore,the algorithm can generate and only generate all the minimal hitting sets.Experimental results show that the proposed algorithm has better computational efficiency than other algorithms.
引文
[1]Reiter R.A theory of diagnosis from first principles[J].Artificial Intelligence,1987,32(1):57-96
[2]Li Lin,Lu Xianliang.An algorithm for detecting filters conflicts based on the intersection of bit vectors[J].Journal of Computer Research and Development,2008,45(2):237-245(in Chinese)(李林,卢显良.一种基于位向量交集运算的规则冲突检测算法[J].计算机研究与发展,2008,45(2):237-245)
[3]Greiner R,Smith B A,Wilkerson R W.A correction to the algorithm in Reiter's theory of diagnosis[J].Artificial Intelligence,1989,41(1):79-88
[4]Jiang Yunfei,Lin Li.Computing the minimal hitting sets with BHS-tree[J].Journal of Software,2002,13(12):2267-2274(in Chinese)(姜云飞,林笠.用对分-HS树计算最小碰集[J].软件学报,2002,13(12):2267-2274)
[5]Jiang Yunfei,Lin Li.The computation of minimal hitting sets with Boolean formulas[J].Chinese Journal of Computers,2003,26(8):919-924(in Chinese)(姜云飞,林笠.用布尔代数方法计算最小碰集[J].计算机学报,2003,26(8):919-924)
[6]Zhao Xiangfu,Ouyang Dantong.A method of combining SEtree to compute all minimal hitting sets[J].Progress in Natural Science,2006,16(2):169-174
[7]Zhang Liming,Ouyang Dantong,Zeng Hailin.Computing the minimal hitting sets based on dynamic maximum degree[J].Journal of Computer Research and Development,2011,48(2):209-215(in Chinese)(张立明,欧阳丹彤,曾海林.基于动态极大度的极小碰集求解方法[J].计算机研究与发展,2011,48(2):209-215)
[8]Wang Yiyuan,Ouyang Dantong,Zhang Liming,et al.A method of computing minimal hitting sets using CSP[J].Journal of Computer Research and Development,2015,52(3):588-595(in Chinese)(王艺源,欧阳丹彤,张立明,等.利用CSP求解极小碰集的方法[J].计算机研究与发展,2015,52(3):588-595)
[9]Jannach D,Schmitz T,Shchekotykhin K.Parallelized hitting set computation for model-based diagnosis[C]//Proc of the29th AAAI Conf on Artificial Intelligence.Menlo Park,CA:AAAI,2015:1503-1510
[10]Zhao Xiangfu,Ouyang Dantong.Deriving all minimal hitting sets based on join relation[J].IEEE Trans on Systems,Man,and Cybernetics:Systems,2015,45(7):1063-1076
[2]Li Lin,Lu Xianliang.An algorithm for detecting filters conflicts based on the intersection of bit vectors[J].Journal of Computer Research and Development,2008,45(2):237-245(in Chinese)(李林,卢显良.一种基于位向量交集运算的规则冲突检测算法[J].计算机研究与发展,2008,45(2):237-245)
[3]Greiner R,Smith B A,Wilkerson R W.A correction to the algorithm in Reiter's theory of diagnosis[J].Artificial Intelligence,1989,41(1):79-88
[4]Jiang Yunfei,Lin Li.Computing the minimal hitting sets with BHS-tree[J].Journal of Software,2002,13(12):2267-2274(in Chinese)(姜云飞,林笠.用对分-HS树计算最小碰集[J].软件学报,2002,13(12):2267-2274)
[5]Jiang Yunfei,Lin Li.The computation of minimal hitting sets with Boolean formulas[J].Chinese Journal of Computers,2003,26(8):919-924(in Chinese)(姜云飞,林笠.用布尔代数方法计算最小碰集[J].计算机学报,2003,26(8):919-924)
[6]Zhao Xiangfu,Ouyang Dantong.A method of combining SEtree to compute all minimal hitting sets[J].Progress in Natural Science,2006,16(2):169-174
[7]Zhang Liming,Ouyang Dantong,Zeng Hailin.Computing the minimal hitting sets based on dynamic maximum degree[J].Journal of Computer Research and Development,2011,48(2):209-215(in Chinese)(张立明,欧阳丹彤,曾海林.基于动态极大度的极小碰集求解方法[J].计算机研究与发展,2011,48(2):209-215)
[8]Wang Yiyuan,Ouyang Dantong,Zhang Liming,et al.A method of computing minimal hitting sets using CSP[J].Journal of Computer Research and Development,2015,52(3):588-595(in Chinese)(王艺源,欧阳丹彤,张立明,等.利用CSP求解极小碰集的方法[J].计算机研究与发展,2015,52(3):588-595)
[9]Jannach D,Schmitz T,Shchekotykhin K.Parallelized hitting set computation for model-based diagnosis[C]//Proc of the29th AAAI Conf on Artificial Intelligence.Menlo Park,CA:AAAI,2015:1503-1510
[10]Zhao Xiangfu,Ouyang Dantong.Deriving all minimal hitting sets based on join relation[J].IEEE Trans on Systems,Man,and Cybernetics:Systems,2015,45(7):1063-1076