Joe*_*way 5 algorithm graph-theory bayesian-networks belief-propagation
我正在玩实现用于贝叶斯网络上的置信度传播的连接树算法.我在对图形进行三角测量时遇到了一些困难,因此可以形成连接树.
我知道找到最优的三角剖分是NP完全的,但是你能指出一个通用算法,它可以为相对简单的贝叶斯网络产生"足够好"的三角剖分吗？
这是一个学习练习(爱好,不是家庭作业),所以我不太关心空间/时间的复杂性,只要算法导致给定任何无向图的三角图.最后,我试图在我尝试进行任何近似之前理解精确推理算法的工作原理.
我正在使用NetworkX修补Python,但使用典型的图遍历术语的这种算法的任何伪代码描述都是有价值的.
谢谢!
如果Xi是一个可能被删除的变量（节点），那么，
启发式：
在每种情况下，从一组可能的变量中选择一个变量 Xi 以最小的 S(i)/C(i) 进行删除
参考：图三角剖分的启发式算法
| 归档时间： |
|
| 查看次数： |
1412 次 |
| 最近记录： |