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

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