小さなベイジアン ネットワーク (DAG で表される) でノードを削除するための最も効率的な順序を見つけるアルゴリズムを作成しようとしています。すべてのノードはブール値であり、2 つの可能な状態を取ることができます。
私の最初の計画は、先行変数が残っていない残りの変数を再帰的に選択し、その可能な状態ごとに、グラフを介して値を伝播することでした。これにより、考えられるすべてのトポロジー順序が得られます。
位相的な順序付けを考慮して、疎外することのコストを見つけたいと思いました。
たとえば、このグラフ:
U --> V --> W --> X --> Y --> Z
にはそのような順序 (U、V、W、X、Y、Z) が 1 つだけあります。
結合密度を因数分解できます 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 には状態が 1 つしかないため)。
これが私の質問です。この順序でこの合計を計算できる最速のステップ数を決定するにはどうすればよいですか?
助けてくれてどうもありがとう！