弧一致性技術(shù)的符號A DD實現(xiàn)算法研究.pdf

1、實際生活中的許多問題都可以建模為約束問題模型,然后用約束滿足問題求解技術(shù)進行處理,比如物流規(guī)劃,硬件電路設(shè)計,生產(chǎn)調(diào)度等各領(lǐng)域的問題,這就使得研究約束滿足問題(Constraint Satisfaction Problem,CSP)具有重大的實用價值。求CSP的解,就是為每個變量賦一個其值域內(nèi)的取值,使得所有約束被滿足。弧一致性( Arc consistency,AC)技術(shù)作為經(jīng)常與搜索算法相結(jié)合的約束推理求解技術(shù),通過在搜索前或搜索過

2、程中刪除肯定不會出現(xiàn)在最終解中的值,達到壓縮搜索空間,提高求解效率的目的。
　　傳統(tǒng)弧一致性實現(xiàn)算法對于狀態(tài)空間和變量組合難免要逐個枚舉,使用有序二叉決策圖(Ordered Binary Decision Diagram,OBDD)及其擴展形式代數(shù)決策圖(Algebraic Decision Diagram,ADD)則可以實現(xiàn)狀態(tài)空間或變量組合的隱式表示和搜索,且具有高效存儲和易操作等特性,可以在一定程度上緩解組合復(fù)雜性問題。因此

3、,本文對基于OBDD及其擴展形式ADD的弧一致性技術(shù)實現(xiàn)方法及其在求解中的應(yīng)用做了相關(guān)研究,取得的主要研究成果如下:
　　(1)根據(jù)經(jīng)典 CSP及加權(quán)約束滿足問題(Weighted Constraint Satisfaction Problem,WCSP)弧一致性定義及實現(xiàn)方法的具體步驟,重寫了ADD中的量化提取操作、部分ITE操作、以及尋找子路徑等操作。為提出基于AD D的弧一致性實現(xiàn)算法打下了基礎(chǔ),也為具體編程驗證弧一致性符號

4、ADD算法性能提供了理論依據(jù)。
　　(2)給出了經(jīng)典CSP的弧一致性符號ADD算法,在搜索前利用該算法對已表示為ADD形式的原問題進行預(yù)處理,接著將該算法嵌入回溯(Backtracking algorithm, BT)搜索框架中,在搜索的過程中使由未實例化的變量組成的子問題也保持弧一致性,形成 BT+GetAC算法。實驗通過對隨機產(chǎn)生的測試用例及部分標準庫中的測試用例進行求解對比,結(jié)果表明,對于經(jīng)典 CSP求解,本文算法的執(zhí)行效率