5
我在貝葉斯網絡上實現信賴傳播的聯結樹算法。我用三角形化圖形掙扎了一下，所以可以形成結合樹。用於三角化無向圖的通用算法？
我知道找到最佳的三角測量是NP完全的，但是您能否指出一個通用算法，該算法對相對簡單的貝葉斯網絡產生了「足夠好」的三角測量？
這是一個學習練習（愛好，而不是家庭作業），所以我不太關心空間/時間複雜性，只要算法在給定任何無向圖的情況下生成三角圖。最終，我試圖瞭解確切的推理算法如何工作，然後我甚至嘗試做任何類似的近似。
我在Python中使用NetworkX修補程序，但任何使用典型圖形遍歷術語的這種算法的僞代碼描述將是有價值的。
謝謝！
當你說「派系（S）的大小」，你的意思是你已經連接到彼此因變量刪除？即如果一個圖包含一個5團，你的方法在第一次迭代中是否可以識別它，或者最初是否將所有變量視爲1團？我想避免每次需要計算C（i）時調用找到最大派系的方法。 – user 2010-11-09 09:21:54