代码之家 › 专栏 › 技术社区 › Joe Holloway

无向图三角化的通用算法?

belief-propagation bayesian-networks graph-theory algorithm

5

Joe Holloway · 技术社区 · 14 年前

我正在尝试在贝叶斯网络上实现一个用于信念传播的连接树算法。我正在努力对图形进行三角定位,以便形成连接树。

我知道找到最佳三角测量是NP完全的,但是你能给我指出一个通用的算法,为相对简单的贝叶斯网络生成一个“足够好”的三角测量吗?

这是一个学习练习(爱好,而不是家庭作业),所以我不太关心空间/时间的复杂性,只要算法在给定任何无向图的情况下生成三角图。最后,在我尝试做任何一种近似之前,我试图理解精确推理算法是如何工作的。

我正在使用networkx修补python,但是使用典型的图遍历术语对此类算法的任何伪代码描述都是有价值的。

谢谢!

1 回复 | 直到 14 年前

1

3

Lance Roberts 14 年前

如果XI是一个可能被删除的变量(节点),

启发式的:

在每种情况下,用最小S(I)/C(i)选择一组变量中的变量Xi。