论文部分内容阅读
变量消元(VE)法是贝叶斯网推理的一个基本方法,然而不同的消元顺序会导致相差悬殊的计算复杂度,寻找最优消元顺序问题是一个NP难问题,因此在实际应用中多采用近似算法求解。通过对贝叶斯网对应的端正图的分析,综合考虑了消元过程中消去的边和增加的边对剩余图的影响,进而提出了一些降低图的复杂度从而控制消元成本的方法,在此基础上提出了一个最优消元顺序的近似构造算法,最后通过随机仿真实验分析比较了算法的性能。实验结果表明,新算法较最小缺边搜索算法有明显的优势。