A method of combining SE-tree to compute all minimal hitting sets

In model-based diagnosis, the candidate diagnostic results are generally characterized by all minimal hitting sets for the collection of all conflict sets. In this paper, a new method is proposed to judge a hitting set by the number of conflict sets corresponding to components, and the computing procedure is formalized by combining revised SE-tree (set enumeration tree) with closed nodes to generate all minimal hitting sets. Results show that because closed nodes are added into SE-tree, the search efficiency is highly improved. Furthermore, the proposed method is easy to be understood and implemented. Compared with other effective algorithms with completeness in some experimental tests, the diagnosis efficiency of our proposed method is higher, particularly for single- and double-fault diagnosis.     

一次性求解多个SAT问题

在实际应用中通常需要求解对应CNF(Conjunctive Normal Form)公式之间仅相差几个子句的一系列SAT(Satisfiability Problem)问题,但目前绝大多数SAT求解算法都是针对单一SAT问题设计的。为此,基于DPLL提出了nDPLL算法,并在随机问题上对该算法的效率进行测试。实验结果表明,nDPLL算法能一次性求解多个SAT问题,对于特定范围的CNF公式集具有较高的效率,CNF公式集的规模越大、相近因子越高、子句数和变量数的比值越大,则nDPLL算法的效率越高。     

基于CNF权重学习求解3-SAT问题的进化算法

SAT（Satisfiability）可满足性问题研究具有很广的应用价值,是计算机和人工智能领域内的一个重要问题,也是第一个被证明为NP完全的问题。随着对SAT问题的深入研究,已经提出了很多高效的算法,其中随机算法（WalkSAT）、进化算法等启发式算法是今年来研究的热点。进化算法是遗传算法的一种,通过对生物组织进化的学习,形成的一种高效算法。针对CNF（Coniecture Normal Formula）权重和生物进化算法相结合,提出一种有效求解难SAT问题的不完全算法WOSAT．     

Kernel model-based diagnosis

The methods for computing the kemel consistency-based diagnoses and the kernel abductive diagnoses are only suited for the situation where part of the fault behavioral modes of the components are known. The characterization of the kernel model-based diagnosis based on the general causal theory is proposed, which can break through the limitation of the above methods when all behavioral modes of each component are known. Using this method, when observation subsets deduced logically are respectively assigned to the empty or the whole observation set, the kernel consistency-based diagnoses and the kernel abductive diagnoses can deal with all situations. The direct relationship between this diagnostic procedure and the prime implicants/implicates is proved, thus linking theoretical result with implementation.     

两种新的基于扩展规则#SAT问题求解算法

提出一种新的基于扩展规则的#SAT求解算法NCER,该算法在#ER的基础上加入启发式策略.该策略每次选择当前子句集的最长子句来减小极大项空间,使得递归调用的次数减少,从而加快求解效率.为解决基于扩展规则的#SAT求解器在互补因子较小的样例上的不良表现,结合NCER和CDP的优点提出混合#SAT求解算法NCDPER.实验结果表明:NCER较先前的#ER在所有85个随机SAT测试用例上有了显著的提高.通过与目前最好的基于扩展规则的#SAT求解器的比较,该求解器具有更好的性能.     

基于粒计算Rough集模型的逻辑推理应用研究

讨论了粒计算理论信息粒子的构成,结合Rough集知识模型给出了信息决策系统不确定性推理的粒计算公式及其过程.针对水产养殖中鱼病诊断信息的模糊性、随机性等不确定特点,通过鱼病症状集形成条件属性粒子、疾病集形成决策粒子而构成的模糊信息决策表,描述出主要逻辑推理算法,即鱼病诊断的规则获取过程,促进粒计算理论应用,同时也为鱼病诊断领域提供了新方法.     

基于逻辑的一种诊断方法

基于逻辑的故障诊断方法中一个没有解决好的问题就是如何求得所有极小冲突集。讨论了如何由极小不协调子集求得极小冲突集，然后经出了求所有极小不协调子集的一种方法。对如何应用该算法求得所有的极小冲突集，给出了求诊断的一个过程，最后与相关工作进行了比较。     

基于第一原理的实用故障诊断算法

根据基于第一的多故障诊断理论,针对具有固定测量点的连续物理系统,提出一种实用诊断算法,算法分３步：（１）根据系统的结构和测量点分布等不变知识,离线识别最小冲突集候选;（２）测量数据,在线确定最小冲突集合组;（３）由系统的部集合组求出诊断集,算法可大大节省时间资源,便于实时故障诊断。     

一种稀疏非线性多元多项式的线性化算法

在有限域上非线性多元多项式的解集可以是任意向量集，在该向量集所属的空间上能够找到最小数量的陪集，并覆盖该向量集，用该最小数量的陪集来线性化原有多项式成为了可能。文章以《有限域上向量子集中的陪集及最小陪集覆盖》一文中提出的理论和算法为依据，提出了利用最小陪集覆盖线性化非线性多元多项式的算法，并给出具体实例加以说明。     

一种识别最小冲突集的实用方法

应用Ｒｅｉｔｅｒ提出的基于第一原理的诊断方法解决连续系统多故障诊断问题的难点是有效地识别最小冲突集合组。文章针对工业过程控制系统的特点,提出一种实用算法。首先根据系统的结构和传感器分布等不变知识,离线识别最小冲突集候选;然后根据测量数据,使用约束悬挂和约束传播技术,在线确定最小冲突集合组。算法是完备的,且大大节省时间资源,便于实时故障诊断     

可满足性问题的充分必要条件

可满足性问题是计算机和人工智能领域内的一个重要的问题,是第一个被证明是NPC的问题。本文主要把子句集进行分类,给出翻转定义、简单集定义,翻转同构定义,并且证明翻转同构不改变子句集的可满足性。论文证明了可满足子句集的三个充要条件。并且这些充要条件可以用于判断可满足问题的完全搜索和不完全搜索算法。     

可满足性问题的充分必要条件

可满足性问题是计算机和人工智能领域内的一个重要的问题,是第一个被证明是NPC的问题。本文主要把子句集进行分类,给出翻转定义、简单集定义,翻转同构定义,并且证明翻转同构不改变子句集的可满足性。论文证明了可满足子句集的三个充要条件。并且这些充要条件可以用于判断可满足问题的完全搜索和不完全搜索算法。     

一个求解SAT问题的随机算法

本文中引入了一个求解满足性问题的随机算法。在该算法中,利用CNF公式转换为其对偶式——DNF公式,通过对满足DNF公式的真值赋值数Y作出估计。根据Y与2n比较结果,对CNF公式的可满足性进行估计并对其满足性进行判断。     

有限策略集全序解及其生成算法

根据策略之间的两两比较结果,将策略集中的所有策略排出顺序是人们在决策时的一个基本依据。本文提出最小全序解的概念,并分别给出偏序策略集、预序策略集以及任意关系策略集最小全序解的表示及其生成算法。     

基于模型诊断的贝叶斯解释及应用

在基于模型诊断的基础上，建立了贝叶斯模型．该模型首先假设系统的所有状态都是可能发生的，并对系统中的各个元件设定一个先验概率．当系统的观测与预期不符合时，利用最小冲突集的概念得到系统可能的状态．之后根据各个系统状态的对应概率计算出元件发生故障的后验概率，该后验概率本质上是一个边缘概率分布，它在数值上表示了元件发生故障的可能性，确定了故障查找顺序．用一个数字故障电路的实例验证了该方法的有效性，井对其存在的问题进行了讨论．     

带有时态约束的多层次关联规则的挖掘

为了适应现实世界数据中数据具有多层次性和时态性的客观情况，在以往关联规则挖掘算法的基础上，提出上具有时态约束的多层次关联规则的挖掘算法，该算法在核心思想是利用统计分析方法，根据用户给定的最小支持度和最小可信度，确定出用户感兴趣的关联规则，实例分析结果表明，该算法与单层次的无时效性的数据挖掘算法相比更有应用价值。     

可用于诊断产生的计算碰集的新方法

提出一种利用与元素相关联的冲突集个数计算碰集的新方法, 并结合带有终止节点的集合枚举树SE tree形式化地表达计算过程, 逐步生成所有的极小碰集. 由于在SE tree中添加了终止节点, 因而能够较大提高搜索效率. 实验结果表明, 该算法程序容易编制, 且效率较好, 对于复杂的被诊断对象系统可以满足实时性.     

完全分配格上的一种对偶关系

在完全分配格中引入了一种“＊”运算,利用这一运算,证明了对任一完全分配格中任一元素都可利用不小于等于它的元素的极小族来直接构造该元素的一个极大族,从而给出了极大族与极小族理论之间的内在联系．利用前面的结果,给出了完备集环上完全并素元之集与完全素元之集间的一一对应关系．     

有限域上向量子集中的陪集及最小陪集覆盖

在有限域上多元非线性方程的解集可以是任意向量集，在该向量集所属的空间上如果找到最小数量的陪集，并覆盖该向量集，那么用这组陪集来线性化该方程成为了可能。文章提出了在多元非线性方程的解集中算出陪集的算法以及最小陪集覆盖的算法，并给出了独立试验的结果。     

解 packing 及 CNF-SAT 问题的拟物拟人方法

提出拟物拟人方法．论述了如何按此种方法为ＮＰ难问题设计出高效实用的快速求解算法．作为例证，所得出的关于ＣＮＦ－ＳＡＴ问题及ｐａｃｋｉｎｇ问题的算法，其先进性在国际竞赛及工业生产中得到了显示．