一种用于信度网推理的高效三角化算法  

An Effective Triangulation Algorithm for Bayesian Network Inference

作　　者：张聪[1] 沈一栋[2] 程克非[3] 

机构地区：[1]重庆大学计算机学院 [2]中国科学院软件研究所计算机科学重点实验室,北京100080 [3]重庆邮电学院计算机系,重庆400054

出　　处：《计算机科学》2005年第6期114-117,136,共5页Computer Science

基　　金：国家自然科学基金(No.69883009);(No.60373052);<跨世纪优秀人才培养计划基金>;重庆市科技攻关项目<面向工业应用的智能开发平台及系统研究>的资助

摘　　要：信度网是不确定性知识表达和推理的有力工具。信度网的精确推理是NPC问题,计算的主要困难在于将信度网三角化并构造一棵最小权的join tree上。此项研究提出了一种新的三角化算法MsLB-Triang,该算法同时利用了无向图三角化的Direc性质与LB-单纯性质,在生成的三角化图的总权以及增加边的数目上均明显优于目前广泛采用的Min.Weight Heuristic算法。Bayesian network is a powerful tool on non-deterministic knowledge representation and inference. The ex- act inference of Bayesian network is a NPC problem, the main difficulty is to triangulate the network and construct a join tree with minimum weight. This work presents a new triangulation algorithm: MsLB-Triang. MsLB-Triang is based on both the Direc property and LB-simple property of triangulation graph, and outperforms the popular using Min. Weight Heuristic triangulation algorithm at the total weight and total filling edges of result graph.

关 键 词：信度网 三角化算法 Min.WeightHeuristic算法 不确定性知识表达 随机变量 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]