1
我正在试图制定一个算法，以找出消除小贝叶斯网络（由DAG表示）中节点的最有效排序。所有节点都是布尔型的，并且可以采用两种可能的状态，除了没有后继节点的节点（这些节点必须具有单个观测值;否则将它们边缘化与删除它们相同）。计算边缘化贝叶斯网络的步骤数
我原来的计划是，我会递归地选择一个没有剩余前辈的剩余变量，并且对于它的每个可能状态，通过图表传播值。这将导致所有可能的拓扑排序。
给定拓扑排序，我想找到边缘化的代价。
例如，该曲线图：
U --> V --> W --> X --> Y --> Z
仅具有一个这样的排序（U，V，W，X，Y，Z）。 （U，V，W，X，Y，Z）= f1（U）f2（V，U）f3（W，V）f4（X，W）f5（Y ，X）F6（Z，Y）
所以对应于该排序边缘化将是
Σ（Σ（Σ（Σ（Σ（Σ（克（W，X，Y，Z），Z （Σ（Σ（f1（U））f2（V，U）f3（W，V）f4（Σ） （f1（U）
Σ（f2（Y，X）f6（Z，Y），Z），Y），X），W），V），U）=
Σ （V，U）
Σ（F3（W，V）
Σ（F4（X，W）
Σ（F5（Y，X）
Σ（F6（Z ，Y），Z）
，Y）
，X）
，W）
，V）
，U）
对于该曲线图，U --> V可以变成V的符号函数在4个步骤（所有所有X所有V.鉴于此， V --> W也可以通过4个步骤变成符号功能。总的来说，它需要18步（4 + 4 + 4 + 4 + 2，因为Z只有一个状态）。
这是我的问题：如何确定此次订购可以计算的总和的最快步数？
非常感谢您的帮助！