ベイジアンネットワークでの信念伝播のためのジャンクションツリーアルゴリズムの実装をいじっています。ジャンクション ツリーを形成できるように、グラフを三角測量するのに少し苦労しています。
最適な三角形分割を見つけることが NP 完全であることは理解していますが、比較的単純なベイジアン ネットワークに対して「十分な」三角形分割をもたらす汎用アルゴリズムを教えていただけますか?
これは学習課題 (趣味であり、宿題ではありません) であるため、無向グラフが与えられた場合にアルゴリズムが三角グラフになる限り、空間/時間の複雑さはあまり気にしません。最終的には、何らかの近似を試みる前に、正確な推論アルゴリズムがどのように機能するかを理解しようとしています。
私は NetworkX を使用して Python をいじっていますが、典型的なグラフ トラバーサルの用語を使用したそのようなアルゴリズムの疑似コードの記述は価値があります。
ありがとう！