用对分HS-树计算最小碰集

在基于模型的诊断中,利用冲突集计算最小碰集是其关键的步骤,因为所有冲突集的最小碰集就是所考察系统的诊断.在Reiter的方法中,要用HS-树(图)来计算最小冲突集的最小碰集.HS-树的计算量比较大,且又会因为剪枝的问题而剪掉真实解.提出了用对分HS-树(binary hitting set-树,简称BHS-树)计算最小碰集的方法.这种方法的优点是:(1)产生的树的节点数明显少于HS-树,因而效率较高;(2)解决了因为剪枝而产生的最小碰集丢失的问题;(3)在新增加冲突集时不必完全重新计算,只需在原BHS-树     

在基于模型诊断中计算最小碰集算法

介绍了基于模型诊断中的计算碰集的算法 ,并分析比较了各算法的效率和计算结果。其中的逻辑型数组算法、递归算法、BHS 树算法、布尔代数算法、GA算法均是笔者近年来研究的结果。     

集总RLC互连树的建模及门负载延迟的近似计算

利用一段简单的电路模型对门输出端的集总RLC互连树建模并计算门负载延迟．采用二叉树的数据结构表示集总RLC互连树,从而快速计算互连树入端导纳的分量,进一步导出II-RLC模型中的R1,L1,C1和C2参数,计算出斜坡输入时的门负载延迟．实验证明,应用文中模型计算出的门负载延迟与Spice延迟偏差不超过3％,因此该模型适合设计验证中门延迟的近似计算．     

基于点表示的曲面曲率计算方法

提出两种方法直接在点集模型上计算曲面的局部微分性质，包括平均曲率、高斯曲率、主曲率和主方向．第一种方法利用voronoi元和有限元，将曲率公式离散．再进行计算；第二种方法利用移动最小二秉法(MLS)，构造局部参数曲面来逼近原始曲面，以局部参数曲面的曲率来近似点集模型的曲率．试验表明这两种方法可以在较小的误差范围内表示曲面的曲率．最后对这两种方法进行了比较，给出了各自的适用场合．     

基于大数据的配电网运行线损异常诊断模型构建

该文针对当前配电网运行线路损耗异常无法甄选异常候选集且诊断不精准的问题，构建配电网运行线损异常诊断模型。采用了一种新的自适应函数，获取最小碰集的线损电量。通过长短时记忆网络方法预处理线损电量数据，获取日线损序列。结合最小二乘支持向量机将序列转变为优化求解问题，通过求解参数构建线损异常诊断模型。计算测试结果与实际结果之间线损误差，确定线损严重程度。由算例仿真结果可知，该模型线损电量统计结果与实际数据存在最大为0.1 MW的误差，说明使用该模型诊断结果精准。     

粗集中上下近似运算的逻辑性质

1 引论近年来,粗集理论的实际应用与理论探讨已成为计算机科学中的一个热点问题。1995年Pawlak曾在文[6]中指出,粗集的逻辑性质研究将是今后粗集理论的一个重要同题。本文正是通过深入研究拓扑布尔代数与粗集的关系,给出了关于有限拓扑布尔代数的表示定理,从逻辑上全面刻画了粗集中上下近似运算这一核心概念。     

利用CSP求解极小碰集的方法

基于模型诊断是人工智能领域中具有挑战性的问题,包含了很多人工智能中的关键问题,其研究对整个人工智能领域起着重要推动作用。在基于模型诊断中,候选诊断结果通常由所有极小冲突集对应的所有极小碰集所描述,求出所有极小碰集是其核心问题之一。提出一种将极小碰集问题转换为约束满足问题的方法,该方法调用成熟的CSP求解器进行求解,扩展了约束可满足问题的应用领域。首次提出hard‐冲突集和sof t‐冲突集的概念,并给出利用所提的方法分别求解具有一些特征的极小碰集：小于固定长度、不含特定元素及包含hard‐冲突集和sof t‐冲突集。实验结果表明,提出的方法易于实现、扩展性强,对于特定类型极小碰集问题的求解效率较高。     

LR最小替换集求解算法研究

文中对Ｄ．Ｍａｉｅｒ提出的关于关系数据库中的ＬＲ最小集的结构进行了分析，提出了一个比“ＬＲ最小集”更为简化的ＦＤ集的覆盖－ＬＲ最小替换集。给出了一个求ＬＲ最小替换集的多项式时间算法。修正了Ｄ．Ｍａｉｅｒ在其文中给出的一个ＦＤ集为最优覆盖的必要条件。     

基于位图的点集表面表示及其渲染

提出了一种基于位图的点集表面表示形式：先对点集表面进行参数化，然后在参数域上进行曲面重构和重采样得到基于二维数组的点集表面表示。采用了切空间对齐的方法得到点集表面的参数坐标。该方法能寻找出点集代表的流型所在的二维参数空间，并存参数化过程中较好地保留了原曲面的尺度信息。位图形式表示点集表面具有数据结构简单和便于随机访问的优点。提出了基于位图表示形式的点渲染方法，该方法采用双线性插值来实现视角依赖的点集表面的重采样，解决了点渲染中采样点不足的问题。     

函数依赖集的有向图表示及在教学中的应用

以有向图表示函数依赖集,将求属性集的闭包转换成有向图的遍历问题,在此基础上,给出了求解候选码、最小覆盖等问题的解决方案。教学实践表明,该方法为相关内容的教学提供了图形化的手段,有助于学生利用数据结构知识来理解新的教学内容以及有关算法的编程和验证。     

The computation of hitting sets: Review and new algorithms

In model-based diagnosis or other research fields, the hitting sets of a set cluster are usually used. In this paper we introduce some algorithms, including the new BHS-tree and Boolean algebraic algorithms. In the BHS-tree algorithm, a binary-tree is used for the computation of hitting sets, and in the Boolean algebraic algorithm, components are represented by Boolean variables. It runs just for one time to catch the minimal hitting sets. We implemented the algorithms and present empirical results in order to show their superiority over other algorithms for computing hitting sets.     

求解掩盖故障的新方法

针对用单故障策略诊断多故障时可能出错的原因,提出一种确定性的,效率较高的求解掩盖故障的算法;首先通过定义寻找系统中可能存在的隐藏故障集;然后在隐藏故障集中寻找可能存在掩盖故障的故障元件集以及冲突集;其次通过建立冲突集簇的相关矩阵,把求解冲突集簇掩盖故障的问题转换为求解集合覆盖,并用确定性方法DNA粘贴模型来求解,获得全部真实解;最后通过实例验证,该方法是一种并行算法,可行、简单、有效。     

一种求解极小诊断的遗传模拟退火算法

基于模型的诊断方法是人工智能领域发展起来的一个十分活跃的分支.在该方法中,由极小冲突集求解极小击中集的过程是一个NP-Hard问题.尽管人们提出了不少算法,但是各种算法的效率仍然不是十分理想.通过将该问题映射到0/1整数规划问题,提出了将遗传算法与模拟退火算法相结合的问题求解思想.在给出遗传模拟退火(genetic simulated anncaling,简称GSA)算法和算法各个参数的同时,对算法的性能和求解精度进行了测试.GSA算法不仅比传统的算法效率有很大的提高,而且在冲突集基数大于35的情况下,较单独使用GA的算法在效率上提高约1/3～1/2.在求解精度上,GSA算法在大多数情况下能够求出98%～100%的极小诊断.     

基于SAT求解器的故障树最小割集求解算法

故障树分析广泛应用于核工业、航空航天和交通控制等安全攸关领域的安全性分析。求解故障树的最小割集是故障树分析的关键步骤。目前,对于大规模故障树的最小割集的求解方法主要是将故障树转化为二元决策图之后求解,其主要缺点在于算法在时间和空间上的消耗严重依赖良好的变量顺序。为了减少存储资源并加快求解速度,提出了一种基于可满足性问题的故障树最小割集求解算法。首先,将求解故障树最小割集问题转化为求解布尔可满足性问题。然后,利用可满足性问题求解器,通过迭代分析求得最小可满足解集合,即为对应故障树的最小割集。实验表明,本文算法求得的最小割集准确、有效并且在空间和时间上的消耗均要优于传统的基于二元决策图的故障树最小割集求解算法。     

针对MUS求解问题的加强剪枝策略

极小不可满足子集(minimal unsatisfiable subsets, MUS)的求解是布尔可满足性问题中的一个重要子问题. 对于一个给定的不可满足问题, 其MUS的求解能够反映出问题中导致其不可满足的关键原因. 然而, MUS的求解是一项极其耗时的任务, 不同的剪枝过程将直接影响到搜索空间的大小、算法的迭代次数, 从而影响算法的求解效率. 提出一种针对MUS求解的加强剪枝策略ABC (accelerating by critical MSS), 依据MSS、MCS、MUS这3者之间的对偶性和碰集关系特点, 提出cMSS和subMUS概念, 并总结出4条性质, 即每个MUS必是subMUS的超集, 进而在避免对MCS的碰集进行求解的情况下有效利用MUS和MCS互为碰集的特征, 有效避免求解碰集时的时间开销. 当subMUS不可满足时, 则subMUS是唯一的MUS, 算法将提前结束执行; 当subMUS可满足时, 则剪枝掉此节点, 进而有效避免对求解空间中的冗余空间进行搜索. 同时, 通过理论证明ABC策略的有效性, 并将其应用于目前最高效的单一化模型算法MARCO和双模型算法MARCO-MAM, 在标准测试用例下的实验结果表明, 该策略可以有效地对搜索空间进行进一步剪枝, 从而提高MUS的枚举效率.     

求极小碰集的蛛网算法

为降低空间复杂度和减少搜索时间,结合极小碰集的特点和生物学中蜘蛛捕食思想,提出了一种搜索极小碰集的蛛网算法。该方法考虑集合之间的相关性,并构造能在蛛网上寻路的访问蜘蛛用于寻找蛛网内集合的所有极小碰集。在该算法中,所提出的访问蜘蛛生成和搜索策略能够降低空间复杂度和减少搜索时间。将此算法与其他的极小碰集算法进行比较,实验结果表明,该算法在保证得到所有极小碰集的前提下,具有较低的空间复杂度和较高的时间效率。     

Hitting sets when the VC-dimension is small

We present an approximation algorithm for the hitting set problem when the VC-dimension of the set system is small. Our algorithm uses a linear programming relaxation to compute a probability measure for which ?-nets are always hitting sets (see Corollary 15.6 in Pach and Agarwal [Combinatorial Geometry, J. Wiley, New York, 1995]). The comparable algorithm of Brönnimann and Goodrich [Almost optimal set covers in finite VC-dimension, Discrete Comput. Geom. 14 (1995) 463] computes such a probability measure by an iterative reweighting technique. The running time of our algorithm is comparable with theirs, and the approximation ratio is smaller by a constant factor. We also show how our algorithm can be parallelized and extended to the minimum cost hitting set problem.     

最小k-击中集问题的一个随机近似算法

Franco等给出一个基于平均度数的最小3-击中集问题的贪心算法,并给出算法返回击中集规模的上界.首先将其算法推广成为求解最小k-击中集问题的贪心算法HGREEDY1(A,C),并类似地给出算法返回击中集规模的上界;然后给出基于最大度数的贪心算法HGREEDY2(A,C),并证明算法HGREEDY2(A,C)在给定条件下返回的击中集规模上界优于算法HGREEDY1(A,C);另外设计了用于求解最小k-击中集的随机算法RH(A,C),并对其性能进行平均分析;在此基础上设计一个求解最小k-击中集的随机近似算法并讨论其性质.