我正在尝试在贝叶斯网络上实现一种用于信念传播的连接树算法。我在对图形进行三角剖分方面遇到了一些困难，以便可以形成连接树。
我知道找到最佳三角剖分是 NP 完全的，但您能否指出一种通用算法，该算法可以为相对简单的贝叶斯网络生成“足够好”的三角剖分？
这是一个学习练习(业余爱好，而不是家庭作业)，所以我不太关心空间/时间复杂度，只要算法在给定任何无向图的情况下生成三角图即可。最终，我试图在尝试进行任何类型的近似之前了解精确推理算法的工作原理。
我正在使用 NetworkX 在 Python 中进行修补，但是任何使用典型图形遍历术语的此类算法的伪代码描述都是有值(value)的。
谢谢!
最佳答案
如果Xi是一个可能被删除的变量(节点)那么，
- S(i) 将是通过删除此变量创建的团的大小
- C(i) 将是 Xi 及其相邻节点给出的子图的团大小之和
启发式:
在每种情况下，从一组可能的变量中选择一个变量 Xi 以最小的 S(i)/C(i) 删除
关于algorithm - 用于对无向图进行三角剖分的通用算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3846825/