【摘要】：約束滿足問(wèn)題在人工智能領(lǐng)域有著廣泛的應(yīng)用。目前有許多求解約束滿足問(wèn)題的方法,本文對(duì)常用的求解約束滿足問(wèn)題的維持弧相容算法做了改進(jìn),對(duì)求解約束滿足問(wèn)題的效率起到至關(guān)重要的兩個(gè)部分--弧相容和啟發(fā)式分別做了改進(jìn),從兩個(gè)方面整體地提高求解約束滿足問(wèn)題的效率。本文通過(guò)分析約束滿足問(wèn)題的粗粒度維持弧相容求解算法在弧相容(arc containing,AC)的執(zhí)行過(guò)程,發(fā)現(xiàn)在對(duì)弧的修正檢查算法中存在冗余的弧放回操作,并對(duì)弧的冗余放回給出了完整的證明。啟發(fā)式是約束滿足問(wèn)題求解的一個(gè)重要組成部分,它通過(guò)一定的策略來(lái)選擇并確定變量和值來(lái)搜索約束滿足問(wèn)題的解。目前已有許多成熟的變量啟發(fā)式能夠針對(duì)特定的問(wèn)題屬性進(jìn)行搜索路徑選擇,但是由于針對(duì)性極強(qiáng),一旦被求解問(wèn)題針對(duì)的特性并不明顯,則相應(yīng)的啟發(fā)式不能發(fā)揮選擇作用,有時(shí)甚至使得問(wèn)題求解效率下降極大�；诖�,考慮設(shè)計(jì)一種魯棒性強(qiáng)的啟發(fā)式,來(lái)避免斷崖式的求解效率波動(dòng)。本文對(duì)約束滿足問(wèn)題求解的改進(jìn)主要體現(xiàn)在以下兩個(gè)方面:(1)在AC3算法的基礎(chǔ)上提出了一種改進(jìn)算法AC_AO通過(guò)保證弧的唯一性來(lái)避免冗余弧的放回隊(duì)列的操作。這種通過(guò)維持弧的唯一性改進(jìn)弧相容算法的模式可以形成框架并適用于AC系列算法,包括AC3算法、AC2001算法、AC3rm算法,本文將提出的改進(jìn)算法框架AC_AO應(yīng)用于AC3、AC2001、AC3rm算法與原算法做實(shí)驗(yàn)對(duì)比,實(shí)驗(yàn)結(jié)果表明,應(yīng)用AC_AO算法框架后的AC系列算法最多可以少檢查77%的弧,最多可以減少30%的CPU求解時(shí)間,AC_AO算法通過(guò)減少弧的檢查進(jìn)而減少修正函數(shù)的調(diào)用次數(shù),從而提高AC的執(zhí)行效率,縮短弧相容算法的執(zhí)行時(shí)間。將AC_AO算法應(yīng)用在維持弧相容算法求解的過(guò)程中對(duì)求解效率提高是非常有意義的。(2)提出了一種基于遺傳選擇的啟發(fā)式方法,能夠針對(duì)問(wèn)題屬性進(jìn)行自適應(yīng)地選擇合適啟發(fā)式指導(dǎo)變量選擇。本文對(duì)該方法進(jìn)行了詳細(xì)分析與描述,將之與最新版本的Choco求解器中最常用的默認(rèn)啟發(fā)式domOverWdeg啟發(fā)式、activityBased啟發(fā)式作對(duì)比,并且針對(duì)遺傳選擇的啟發(fā)式算法,分別做了兩組實(shí)驗(yàn),一組弧相容算法選擇AC3算法,另一組弧相容算法選擇AC_AO算法,分別進(jìn)行約束滿足問(wèn)題的求解,實(shí)驗(yàn)結(jié)果表明在約束滿足問(wèn)題的求解上,AC_AO算法優(yōu)于AC3算法�；谶z傳選擇的啟發(fā)式算法的求解效率最高是domOverWdeg啟發(fā)式的2.35倍,activityBased啟發(fā)式的2.26倍。在求解效率的魯棒性上也優(yōu)于其他啟發(fā)式算法。
【圖文】：

圖 2.1 原始 CSP 問(wèn)題示了一個(gè)約束滿足問(wèn)題示例，，此約束滿足問(wèn)題涉及 3命名，其中 =( , )、 =( , ) 、 =( , )，被 、 ，變量 的論域?yàn)閧0、1、2}，變量 、 、 表示支持，如 中的值 1 與 中的值 0 互為支持。，0）；對(duì)于約束 ，支持的元組為（1，0）、（2，1）；對(duì)1，0）、（2，1）。了此 CSP 問(wèn)題的一組解，即變量 取 1 值，變量 取 取 0 值。

圖 2.1 原始 CSP 問(wèn)題示了一個(gè)約束滿足問(wèn)題示例，此約束滿足問(wèn)題涉及 3 個(gè) 命名，其中 =( , )、 =( , ) 、 =( , )，被約 、 、 ，變量 的論域?yàn)閧0、1、2}，變量 、 、 的線表示支持，如 中的值 1 與 中的值 0 互為支持。對(duì)1，0）；對(duì)于約束 ，支持的元組為（1，0）、（2，1）；對(duì)（1，0）、（2，1）。了此 CSP 問(wèn)題的一組解，即變量 取 1 值，變量 取 量 取 0 值。
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2019
【分類號(hào)】：TP18

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 陸明;;約束滿足問(wèn)題在題庫(kù)系統(tǒng)中的應(yīng)用[J];民營(yíng)科技;2008年04期

2 王俊潔;王俊鑫;桂林斌;;人工智能中感知問(wèn)題的求解技術(shù)——約束滿足法[J];楚雄師范學(xué)院學(xué)報(bào);2008年03期

3 郭平;侯睿;楊國(guó)洲;范麗;;方位關(guān)系約束滿足問(wèn)題的推理求解[J];計(jì)算機(jī)科學(xué);2005年08期

4 李偉,劉光復(fù);一類基于動(dòng)態(tài)約束滿足問(wèn)題的產(chǎn)品配置方法[J];機(jī)械科學(xué)與技術(shù);2005年04期

5 劉洋,陳英武;動(dòng)態(tài)約束滿足及其在資源調(diào)度問(wèn)題中的應(yīng)用[J];計(jì)算機(jī)工程與應(yīng)用;2004年27期

6 郭寶龍,郭雷,戴冠中;約束滿足神經(jīng)網(wǎng)絡(luò)[J];電子學(xué)報(bào);2000年01期

7 孫偉,馬紹漢;約束滿足問(wèn)題并行弧相容算法[J];計(jì)算機(jī)工程與科學(xué);1997年01期

8 柏淑琴;;高校排課問(wèn)題的約束滿足優(yōu)化模型與算法[J];科技視界;2012年18期

9 張泉樂(lè);袁際軍;;非二元約束滿足問(wèn)題的產(chǎn)品配置建模與求解[J];武漢理工大學(xué)學(xué)報(bào);2010年01期

10 董存祥;王文俊;楊鵬;;基于約束滿足問(wèn)題的應(yīng)急決策[J];計(jì)算機(jī)工程;2010年07期

相關(guān)會(huì)議論文 前3條

1 張寶;方圣恩;;基于改進(jìn)約束滿足問(wèn)題的結(jié)構(gòu)損傷評(píng)估方法[A];第23屆全國(guó)結(jié)構(gòu)工程學(xué)術(shù)會(huì)議論文集（第Ⅲ冊(cè)）[C];2014年

2 李海晨;馮玉強(qiáng);;基于模糊約束滿足問(wèn)題的談判決策研究[A];第八屆中國(guó)管理科學(xué)學(xué)術(shù)年會(huì)論文集[C];2006年

3 張志強(qiáng);王萬(wàn)玉;王建平;李凡;袁剛;;多站多星任務(wù)調(diào)度優(yōu)化模型研究[A];第二十三屆全國(guó)空間探測(cè)學(xué)術(shù)交流會(huì)論文摘要集[C];2010年

相關(guān)博士學(xué)位論文 前9條

1 劉濤;約束滿足問(wèn)題：算法和復(fù)雜性[D];中國(guó)科學(xué)院研究生院（計(jì)算技術(shù)研究所）;1994年

2 王秦輝;約束滿足及其分布式求解和應(yīng)用研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2007年

3 馮欣;約束滿足技術(shù)的研究及在生產(chǎn)調(diào)度中的應(yīng)用[D];東北大學(xué);2008年

4 李宏博;約束滿足問(wèn)題研究及其在蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)中的應(yīng)用[D];吉林大學(xué);2015年

5 徐周波;約束滿足問(wèn)題的符號(hào)算法及其在裝配規(guī)劃中的應(yīng)用研究[D];西安電子科技大學(xué);2012年

6 韋沙;基于分布式約束滿足算法的無(wú)線信道分配研究[D];華中科技大學(xué);2011年

7 沈靜;約束滿足問(wèn)題的模型構(gòu)造和相變現(xiàn)象[D];華中師范大學(xué);2011年

8 付宏杰;求解二元約束滿足問(wèn)題的混合差分進(jìn)化算法研究[D];吉林大學(xué);2011年

9 袁際軍;大規(guī)模定制下基于約束的產(chǎn)品配置方法研究[D];湖南大學(xué);2008年

相關(guān)碩士學(xué)位論文 前10條

1 王宇星;基于多主體建模與量詞約束滿足的產(chǎn)品質(zhì)量控制研究[D];西南科技大學(xué);2019年

2 王希彤;基于MBO的約束滿足問(wèn)題求解算法研究[D];吉林大學(xué);2019年

3 楊罡;基于約束滿足問(wèn)題求解算法的改進(jìn)算法研究[D];吉林大學(xué);2019年

4 王蓀馨;基于約束滿足技術(shù)的作業(yè)車間調(diào)度問(wèn)題研究[D];西安理工大學(xué);2007年

5 任雪亮;改進(jìn)的置信傳播算法在求解最大約束滿足問(wèn)題的應(yīng)用[D];東北師范大學(xué);2015年

6 趙利;基于約束滿足問(wèn)題的配置解釋算法研究[D];吉林大學(xué);2008年

7 李碧濤;基于約束滿足神經(jīng)網(wǎng)絡(luò)的作業(yè)車間調(diào)度及應(yīng)用[D];吉林大學(xué);2006年

8 馬冬梅;約束滿足問(wèn)題分解算法及其在配置求解中的應(yīng)用[D];吉林大學(xué);2007年

9 王旭;交互約束滿足問(wèn)題的沖突解釋算法研究[D];吉林大學(xué);2016年

10 徐亞男;二元約束滿足問(wèn)題上基于禁止模式刪變量的實(shí)現(xiàn)及其優(yōu)化研究[D];吉林大學(xué);2016年

本文編號(hào)：2588855