原创《基于参数矩阵逻辑运算求解极小碰集》
该文是关于矩阵方面论文范例和矩阵和逻辑和极小有关毕业论文题目范文。
一、引言
基于模型的诊断 (Model-based diagnosis, MBD) 作为一项灵活性高的推理技术,取代了基于专家诊断方法的缺点,极大地促进了人工智能向前发展[1].近年来,随着系统集成化、自动化程度日益提高,对系统的可靠性和可维护性需求也日益增加,基于模型诊断的应用也得到了广泛推广,并且向着可行性方向发展[2].目前,利用MBD 可进行电路系统故障查找和排除、医学诊断系统研究、网络通讯系统故障诊断,大型汽车、轮船故障诊断等,具有模型智能化、应用普遍性等特点[3-4].
候选产生即产生所有极小碰集的过程,被证明为NP-完全问题,许多学者为优化计算而进行了不懈的研究.如Reiter 最早提出了经典的HS-tree[5] 方法计算所有极小碰集,林笠等人对HS-tree 进行改进,提出了BHS-tree[6] 方法,赵相福等人提出的HSSE-tree[7] 算法,张立明等人提出的基于动态极大度求解极小碰集的算法[8],陈晓梅等融合了分支定界法和HSSE 法,提出BNB-HSSE 方法[9],王艺源等提出利用CSP 求解极小碰集[10].然而这些算法都有各自的不足之处,例如：由于剪枝可能丢失解,或者需要建树或图等较复杂的数据结构,或者需要递归而效率较差等.本文提出了基于参数矩阵逻辑运算计算极小碰集的改进算法,只需要通过比较存储集合簇元素的集合中剩余元素个数来决定算法是否继续执行,不必每次计算一个元素,将参数矩阵中该行删除,改变参数矩阵的大小,并且在输入参数矩阵时按元素度的大小自上而下排列,在计算碰集的过程中不必再比较元素度的大小,然后进行选择元素进行计算.优化了极小碰集计算过程,提高了计算效率.
二、基本概念
根据下文算法描述的需要,给出一些相关概念定义1[5]（系统）三元组(SD, COMPS, OBS) 可以用来表示一个待诊断系统,其中SD (System Description) 为一阶谓词公式（First-orderpredicate formula）描述的系统的结构、行为、功能、连接关系等；
COMPS（Components）为常量集合{c1, c2, …, cn} 表示的系统的所有组成元件.
OBS（Observations） 为一阶谓词公式（First-orderpredicate formula）表示的系统的观测集合.
定义2[5] （ 冲突集） 给定一个模型, 如果其满足SD ∪ OBS ∪ {?AB (c1), ?AB(c2), …, ?AB(cn)} 不相容,说明系统存在故障,则元件集{c1, c2, …, cn} 是系统的一个冲突元件集（Conflict Set, CS）,其中ci ? COMPS, AB(ci) 表示元件ci 当前工作不正常（Abnormally）.给定一冲突集C,如果C 的所有真子集都不是冲突集,那么C 为极小冲突集[4].
定义3[5] （碰集）设F 是集合簇,集合S 是F 的元素,如果存在集合H,使得H 满足：
（1）H ? S?FS∈ ；（2）S ∈ F,都有H ∩ S ≠ ?.
则称H 是F 的一个碰集（Hitting Set, HS）
三、算法描述
3.1 M-MHS 算法
基于参数矩阵(M-MHS) 求解极小碰集的算法,利用参数矩阵描述元素与集合是否有从属的关系,通过矩阵分解和按照剪枝规则对其进行有效的剪枝进行计算.
定义4[11] 用a?b 的参数矩阵来描述各个元素在冲突集簇各个集合中是否存在的关系,其中a 表示冲突集合簇中包含的元素数目,b 表示冲突集簇中集合数目,若某个集合中包含该元素,则在矩阵中对应的行和列用1 表示,例如矩阵中元素mij 为1 表示第j 个冲突集存在第i 个元素,若为0 表示第j 个冲突集不包含第i 个元素.
推论4.1[11] 若矩阵中某一行对应的元素是冲突集簇的一个极小碰集,当且仅当矩阵中该行的元素都为1.
推论4.2[11] 若参数矩阵中某一行全为0,说明剩下的集合簇中不包含该元素,则极小碰集中不可能出现该元素.推论4.3[11] 若参数矩阵中存在全0 列,则这个冲突集簇无解,若没有全0 列,那么此冲突集簇必定有极小碰集,反之亦然.
基于参数矩阵求解极小碰集的算法在计算的过程中,通过取出求解元素0 列所对应的元素将矩阵进行分解,使每次求解问题变成小问题.
3.2 基于参数矩阵逻辑运算求解极小碰集算法
基于参数矩阵逻辑运算求解极小碰集的算法先统计元素在集合簇中0,1 出现的次数,在求解过程中运用逻辑运算,通过依次查找扩展元素0 所对应的列中出现1 的元素,将大问题化成子问题,
Input：
冲突集合簇F 等于 {C1, C2, …, Cn},参数矩阵Mm×n；
Output：
存储计算结果的列表H；
具体步骤如下：
（1）分别统计集合簇中元素出现的频率,将元素按照出现频率的大小进行排序,得到储存元素的集合S；
（2）定义一个m×n 的参数矩阵,其中m 表示冲突集簇中元素个数,n 表示冲突集簇中集合个数,按照元素频率的大小的顺序排列元素在矩阵中的行数,从第一行到m 行,元素在集合簇中出现的频率依次递减；
（3）将矩阵中全0 行删除；
（4）从矩阵的第一行开始计算,找到该行0 所对应的列数,假设有K 列,则将该列为1 的元素加入到碰集中,删除集合S 中该行的元素；
（5）i+1,重复步骤4；
（6）若计算出的集合已包含S 中剩下的所有元素仍不能构成碰集,则无需再计算S 集合中剩下元素的碰集；
（7）返回H.
改进算法后,输入的初始矩阵中,各行元素度的大小是从上到下依减小的,根据集合S 中剩余元素的个数来判断此算法是否终止,且在计算过程中无需删除已求解完毕的元素在矩阵中的行.
四、实例验证
例：给定一个冲突集簇F等于{{A,C,D},{B,C,D},{C,D,E},{A,E,F},{B,E},{A,D,E}}, 计算出F 的所有极小碰集为：{{D,A,B},{D,E},{D,B,F},{E,C},{E,A,B},{A,B,C}},计算过程如下所述：
（1）去掉集合簇的真超集；
（2）计算集合簇中元素A,B,C,D,E,F 出现的频率分别为3,2,3,4,4,1,则集合S等于{D,E,A,C,B,F}；
（3）根据冲突集簇中元素在各个集合中有无出现的情况（根据元素频率大小排列）,得出初始矩阵为：
（4）i等于1：
1）首先扩展矩阵第一行元素D,D 所在的行为0 对应的列为第4 和第5 列,从i+1 行开始寻找,直到i>m（矩阵行数）,找到第4 列为1 的元素为E,A,F,将E,A,F加入到HD等于{{E},{A},{F}},由于元素E 的第4 列和第5 列都为1,则集合{D,E} 是碰集,加入到H 中,删除HD 中的E 元素,得HD等于{{A},{F}}；
2）查找第5 列为1 的元素为B,分别加入到HD 中,得HD等于{{A,B},{F,B}},合并HD 与D 元素得到{A,B,D},{F,B,D},加入到碰集列表中得到H等于{{D,E},{A,B,D},{F,B,D}}；
（5）删除S 中第i 个元素D,得到S1等于{E,A,C,B,F}；
（6）i等于i+1等于2：
1）扩展矩阵第二行元素E,E 所在的行为0 对应的列为第1 列和第2 列,从i+1 行开始寻找,直到i>m（m 为矩阵行数）.
找到第一列为1 的元素为A,C,加入到HE,HE等于{{A},{C}},由于元素C 的第1 列和第2 列都为1,则集合{E,C} 是碰集,加入到碰集列表中,H等于{{D,E},{A,B,D},{F,B,D},{E,C}}
2） 查找第2 列为1 的元素为B, 加入到HE 中, 得HE等于{{A,B}},合并HE 中的E 元素得到{A,B,E},加入到碰集列表中得H等于{{D,E},{A,B,D},{F,B,D},{E,C},{A,B,E}}（7）删除S 中第i 个元素E,得到S2等于{A,C,B,F}；
（8）i等于i+1等于3；
1）扩展矩阵第三行元素A,A 所在的行为0 对应的列为第2 列,第3 列,第5 列,从i+1 行开始寻找,直到i>m结束,找到第2 列为1 的元素为C,B,加入到HA 中得HA等于{{C},{B}}；
2）找到第3 列为1 的元素为C,与HA 中的集合合并得HA等于{{C},{C,B}}
3）找到第5 列为1 的元素为B,与HA 中的集合合并得HA等于{{C,B}}；
4）将HA 中的集合与元素A 合并得到碰集{A,C,B},加入到碰集列表中得到H等于{{D,E},{A,B,D},{F,B,D},{E,C},{A,B,E},{A,C,B}}；
（9）删除S 中第i 个元素A 得S3等于{C,B,F}；
（10）i等于i+1等于4：
1）扩展矩阵第4 行元素C,C 所在的行0 对应的列为第4,5,6 列,从i+1 行开始寻找,直到i>m 才结束寻找,第4 列为1 的元素为F,加入到HC 中得HC等于{{F}}；
2）查找第5 列为1 的元素为B,与HC 中的集合合并得HC等于{{F,B}}；
3）查找第6 列为没有为1 的元素,则HC 中的集合与元素C 合并得到{F,B,C},C 元素0 列所对应的元素不都是1,则该集合不能构成一个碰集；
（11）由于最后得到的集合{F,B,C}等于S3,但仍不能构成一个碰集,则无需再继续扩展；
（12）最终得到的极小碰集为{{D,E},{A,B,D},{F,B,D},{E,C},{A,B,E},{A,C,B}}.
五、结束语
在基于参数矩阵计算极小碰集的算法中,每计算包含该元素的碰集时,需要将该元素在参数矩阵中所对应的行删除,不再扩展出现次数小于等于当前扩展元素的其他所有元素.而改进算法中,虽同样需要输入一个参数矩阵,此矩阵代表各个元素在集合簇中各个集合的存在情况,1 代表存在,0代表不存在.
但是,不同的是改进算法中按照元素出现的次数大小顺序排列元素所在行,逐一生成极小碰集；且在计算极小碰集的过程中,并不需要删除已求解完碰集的元素所在的行,只需要在相关集合中删除该该元素即可；而且删除过程相对简单,同样可以将大规模问题分解成很多小的子问题.在计算极小碰集的过程中,从上至下查找0 所在的列,直到找到包含该元素所有极小碰集为止,无需进行删除矩阵的操作,从而使计算过程相对简单,计算效率相对较高.
矩阵论文参考资料：
上文结束语，此文为适合矩阵和逻辑和极小论文写作的大学硕士及关于矩阵本科毕业论文，相关矩阵开题报告范文和学术职称论文参考文献。
