基于桶消元的联合树算法

The Junction Tree Algorithm Based on the Bucket Elimination

一、引言 联合树算法[1]是一种应用广泛的信度网推理算法.根据不同的消息传递方案,可以将联合树算法分为两种:一种基于Hugin消息传递方案,称为Hugin联合算法;另和中采用Shafer-Shenoy消息传递方案[2],称为Shafer-Shenoy联合树算法.下文除特别申明外,提到的联合树算法都是指Hugin联合树算法.

The junction tree algorithm is broadly applied to inference on the belief network. In this paper we optimize the message-propagation procedure by using the bucked elimination algorithm, and then build a new algorithm-the junction tree algorithm based on the bucket elimination. The new algorithm can exploit independence relations induced by evidence to reduce both time and space costs. By experiment we show that the new algorithm is really faster than the old one.