论文标题：Enhancing model-based diagnosis with multiple pseudo-normal observations by Key nodes and IterativeDFS

期刊：Frontiers of Computer Science

作者：Ran TAI, Dantong OUYANG, Ximing LI, Huisi ZHOU, Liming ZHANG

发表时间：30 May 2025

DOI：10.1007/s11704-025-50555-1

微信链接：点击此处阅读微信文章

引用格式：

Ran TAI, Dantong OUYANG, Ximing LI, Huisi ZHOU, Liming ZHANG. Enhancing model-based diagnosis with multiple pseudo-normal observations by Key nodes and IterativeDFS. Front. Comput. Sci., 2026, 20(8): 2008341

阅读原文：

问题概述

针对利用多观测解决基于模型诊断问题中的伪正常观测情况，目前的算法无法对伪正常观测中的正常观测进行处理，只能选择无视它们而对异常观测进行处理。本文介绍了一种利用这些正常观测获得额外信息的算法DKIPNO。该算法通过这些额外信息能够确认更多的功能正常的系统组件，从而减少诊断过程中需要考虑的诊断数，提高求解诊断效率。

技术步骤

通过引入关键节点的概念，进一步提出对应该概念的命题，给出命题的详细证明，表明使用关键节点的概念能够通过观测在求解诊断前确认功能正常的组件，从而提升求解效率。并且提出了IterativeDFS方法，该方法用迭代取代了传统DFS方法中的递归方式，使算法在求解大规模系统的诊断时不会出现栈溢出的错误，使得在大规模系统中求解诊断成为可能。结合关键节点与IterativeDFS方法，我们提出了DKIPNO算法。

实验结果

实验结果表明，本文提出的DKIPNO算法相比其他算法HSD、IHSD、DiagDO在求解极小子集诊断和极小势诊断时都有着更高的求解效率。并且DKIPNO算法能够在给定时间内较大规模的电路上返回相应的诊断解，这是其他算法做不到的。

期刊简介

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办，南京大学支持，SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华院士，执行主编为周昆教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐B类期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；两次入选“中国科技期刊卓越行动计划”（一期梯队、二期领军）。