質問不可能格子グラフである理由タイトルMRFの正確な推論が
で書かれているように、上記画像における3×3グリッドグラフです。私たちはジャンクションツリーに変換することができます。次に、推論（推定尤度/事後等）にメッセージパッシング（積和アルゴリズム）を用いることが可能である。ですから、グリッドグラフの正確な推論がなぜそんなに難しいのでしょうか？
グリッドが大きくなると、このようなジャンクションツリーを見つけることは不可能ですか？
短い答え：nxnグリッドの場合、複雑さは少なくとも指数nです。
接合ツリーは、除去順序（最初に境界を計算するために排除する変数）に依存するMRFの誘導グラフから作成されます。排除コストは、誘導グラフの最大クリークのサイズで指数関数的です。詳細は、this用紙を参照してください。
したがって、接合ツリー上で正確な推論を使用することができますが、複雑さは、使用された消去順序の誘導グラフの最大クリークのサイズが指数関数的になります。
最善の削除順序では、nxnグリッドのnであるツリー幅に等しい最大クリークサイズが得られます。しかし、それを見つけるための効率的なアルゴリズムはありません。