基于樹寬的警示傳播算法收斂性分析

打開文本圖片集

摘要：警示傳播算法作為一種基本的信息傳播算法，其收斂時(shí)求解可滿足性問題十分有效，但因子圖結(jié)構(gòu)較為復(fù)雜時(shí)，算法往往不收斂導(dǎo)致求解失敗。為了對(duì)這種現(xiàn)象給予理論解釋，同時(shí)對(duì)警示傳播算法收斂性進(jìn)行有效分析，利用樹分解方法構(gòu)造了命題公式對(duì)應(yīng)因子圖的樹寬度量模型，計(jì)算可滿足隨機(jī)實(shí)例的樹寬。建立樹寬與警示傳播算法收斂性之間的關(guān)系，給出了基于樹寬的警示傳播算法收斂性判定條件。（剩余14521字）