基于全条件独立的贝叶斯网络MPD-JT构造算法

针对求解贝叶斯网络最大主子图存在的NP(non-deterministic polynomialtine)难问题，提出了一种基于全条件独立结构的最大主子图连接树（maximal prime sub graph decomposition junction tree， MPD-JT）构造算法。该算法通过道义图上的全条件独立结构得到贝叶斯网络最大主子图，并利用构成这些最大主子图的节点作为簇节点构造连接树，避免了三角化过程，而且在求解过程中通过删除一些符合条件的点，大大降低了算法复杂度。给出了算法的理论证明，通过具体案例分析验证了算法的有效性。

Construction algorithm of MPD-JT for Bayesian networks based on full conditional independence

As the decomposition of Bayesian networks (BN) into their maximal prime sub-graph is a NP-hard problem, a new method for constructing the maximal prime sub-graph junction tree (MPD-JT) of  BN is presented. This approach obtains the MPD of BN motivated by the full conditional independence information encoded in the moral graph of the original BN and uses these MPDs as a cluster of nodes to construct a junction tree, it also avoids the process of triangulation and reduces the time complexity by eliminating some coincident nodes. The correctness of the method is proven and the validity of the algorithm is analyzed by an example．