贝叶斯网络变量消元法最优消元顺序构造  

作　　者：任东平 郭建喜 郝小礼 蒋涛 

机构地区：[1]海军勤务学院基础部 [2]海军装备部装备保障大队

出　　处：《数字技术与应用》2023年第2期44-48,97,共6页Digital Technology & Application

摘　　要：变量消元法(Variable Elimination,VE)是贝叶斯网络众多推理算法中最基本的一个,其推理的快慢和复杂度主要取决于消元的顺序。寻找最优消元顺序是一个非确定性多项式难解算法(Nondeterminism Polynomial Hard,NP-Hard)问题,在实际中常采用启发式搜索来求解。为了提高变量消元法的推理速度,在此对最小度、最大势、最小缺边和最小增加复杂度搜索方法进行了研究,以亚洲网络为例,分析计算了上述搜索方法的复杂度和消元顺序,通过MATLAB R2018a对上述不同搜索方法分别进行网络构建和推理,最后通过推理时间分析比较了4种搜索方法的性能。实验结果表明最小增加复杂度搜索方法优于其他搜索方法,其平均耗时最少为0.012s,可加快贝叶斯网络的推理过程。

关 键 词：贝叶斯网络 启发式搜索 非确定性 网络构建 推理算法 推理过程 最小度 平均耗时 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]