本文關(guān)鍵詞：約束滿足問題中基于MDD的相容性算法研究

  更多相關(guān)文章： 人工智能 約束滿足問題 多元約束 多值決策圖

【摘要】：約束滿足問題(CSP)是人工智能領(lǐng)域的一個重要分支,其核心是約束求解,探索高效的求解算法來提高求解效率是當(dāng)前研究的主要問題。相容性技術(shù)在約束滿足問題求解過程中起著舉足輕重的作用,它可以在預(yù)處理階段和搜索過程中將那些一定不能擴(kuò)展成解的變量值刪掉,從而減少了一些不必要的搜索,并減小了搜索空間。回溯搜索是目前比較通用的一種求解技術(shù),在對變量選擇和值的選擇時還可加入合適的啟發(fā)式策略,在回溯過程中與相容性技術(shù)相結(jié)合,使得約束滿足問題的求解變得快速、高效。目前對于約束滿足問題的求解多數(shù)是針對二元約束的,而很多實際問題都涉及多個變量,因此,多元約束的求解問題受到人們?nèi)找嬷匾�。對于多元約束的求解有兩種處理辦法:一是將多元約束滿足問題轉(zhuǎn)化為二元約束滿足問題,然后再利用其高效的求解算法進(jìn)行求解;二是直接利用多元約束的相容性算法來進(jìn)行求解,本文主要研究的是后者。多元約束的表示形式有很多種,目前常用的是將解的元組放到一個表中,而表約束的壓縮表示方法有多種,例如:結(jié),多值決策圖(MDD),壓縮表,確定型有限自動機(jī)。當(dāng)用這些復(fù)雜的數(shù)據(jù)結(jié)構(gòu)表示表時,成功最關(guān)鍵的因素是實現(xiàn)的壓縮率,它決定了需要空間的大小。利用多值決策圖來表示多元約束可在空間上達(dá)到壓縮的效果,本文就是在MDD這種結(jié)構(gòu)下,根據(jù)已有的算法進(jìn)行分析以及優(yōu)化,具體所做工作如下:(1)對于多元約束求解算法進(jìn)行介紹,針對原有的基于MDD的GAC算法進(jìn)行改進(jìn),提出了mddc+算法,通過加入提前終止策略,在每一次遍歷MDD以及子MDD節(jié)點(diǎn)過程中記錄下每個變量的論域中當(dāng)前已找到支持的值,若某個變量及其MDD圖中下面的所有變量論域中的所有值都能夠找到支持,那么當(dāng)前節(jié)點(diǎn)的子MDD就無需遍歷,而是只需找到一條當(dāng)前節(jié)點(diǎn)到終端節(jié)點(diǎn)的路徑,這樣減少了一些不必要的尋找支持的過程,并通過實驗驗證了其高效性。(2)在搜索圖中,對于每層待擴(kuò)展結(jié)點(diǎn)的選擇,即選擇變量實例化過程中加入了啟發(fā)式,經(jīng)過比較,本文選用的是目前應(yīng)用廣泛的dom/wdeg啟發(fā)式,可減少整體求解所用的時間,在一定程度上提升了求解效率。本文給出了(1)、(2)兩點(diǎn)改進(jìn)的偽代碼,并與原有的mddc算法和STR算法進(jìn)行對比試驗,比較了求解所用CPU時間和擴(kuò)展節(jié)點(diǎn)數(shù),通過對比試驗驗證了本文所做的改進(jìn)在很多問題上可以提高求解效率。
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TP18

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 郭冬芬;李鐵克;;基于約束滿足的煉鋼批量計劃的制定方法[J];微計算機(jī)信息;2007年12期

2 湯萍萍;王紅兵;;基于層次約束滿足的產(chǎn)品選擇算法[J];現(xiàn)代計算機(jī)(專業(yè)版);2007年08期

3 谷學(xué)強(qiáng);陳t，

本文編號：1160885