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

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

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

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

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