我正在尝试制作一种算法，该算法将找到消除小型贝叶斯网络（由 DAG 表示）中节点的最有效排序。所有节点都是布尔值，可以采取两种可能的状态，除了没有后继节点的节点（这些节点必须有一个观察值；否则将它们边缘化与删除它们相同）。
我最初的计划是，我将递归地选择一个没有剩余前任的剩余变量，并针对其每个可能的状态，通过图形传播该值。这将导致所有可能的拓扑排序。
给定一个拓扑排序，我想找出边缘化的成本。
例如，这张图：
U --> V --> W --> X --> Y --> Z
只有一个这样的排序 (U,V,W,X,Y,Z)。
我们可以分解关节密度 g(U,V,W,X,Y,Z) = f1(U) f2(V,U) f3(W,V) f4(X,W) f5(Y,X) f6 (Z,Y)
所以这个排序对应的边缘化将是
∑(∑(∑(∑(∑(∑(∑(g(W,X,Y,Z),Z),Y),X),W),V),U) =
∑(∑(∑(∑(∑ (∑(f1(U) f2(V,U) f3(W,V) f4(X,W) f5(Y,X) f6(Z,Y),Z),Y),X),W), V),U) =
∑(f1(U)
∑(f2(V,U)
∑(f3(W,V)
∑(f4(X,W)
∑(f5(Y,X)
∑(f6(Z, Y),Z)
,Y)
,X)
,W)
,V)
,U)
对于该图，U --> V可以分 4 步转换为 V 的符号函数（所有 U x所有 V。鉴于此，V --> W同样可以分 4 步转换为符号函数。所以总体而言，需要 18 步（4+4 +4+4+2 因为 Z 只有一种状态）。
Here is my question: how can I determine the fastest number of steps that this sum can be computed for this ordering?
Thanks a lot for your help!