本文關(guān)鍵詞：基于貪心搜索的Singleton弧相容算法的研究

  更多相關(guān)文章： 約束滿足問(wèn)題 Singleton弧相容 啟發(fā)式方法

【摘要】：約束滿足問(wèn)題是人工智能領(lǐng)域的一個(gè)重要分支,其表示形式可以形象的對(duì)現(xiàn)實(shí)世界中的問(wèn)題進(jìn)行建模,從而將問(wèn)題抽象為約束滿足問(wèn)題的模型進(jìn)行求解,已經(jīng)廣泛的應(yīng)用于配置,調(diào)度,規(guī)劃,網(wǎng)絡(luò)以及生物信息學(xué)等諸多領(lǐng)域。求解一個(gè)約束滿足問(wèn)題,是指為其找到一個(gè)解或者證明其無(wú)解。約束滿足問(wèn)題的求解往往結(jié)合使用搜索和推理的方法。搜索技術(shù)用于遍歷問(wèn)題中所有變量的當(dāng)前論域來(lái)尋找解。推理技術(shù)通過(guò)變量消元,樹(shù)分解和相容性技術(shù)將問(wèn)題轉(zhuǎn)化為一個(gè)等價(jià)問(wèn)題,使之更易于求解。相容性技術(shù)主要有兩個(gè)作用:在預(yù)處理階段,有效的采用合理的相容性技術(shù)可以刪除那些必然不屬于解的值;在搜索過(guò)程中,采用相容性技術(shù)來(lái)強(qiáng)化網(wǎng)絡(luò),有助于判斷搜索樹(shù)的當(dāng)前節(jié)點(diǎn)是否擴(kuò)展正確。相容性技術(shù)一直是約束求解領(lǐng)域的熱點(diǎn)問(wèn)題。常見(jiàn)的相容性技術(shù)有:弧相容AC(Arc Consistency),路徑相容PC(Path Consistency),最大限定路徑相容max RPC(max-Restricted Path Consistency)和單弧相容SAC(Singleton Arc Consistency)等。如何利用網(wǎng)絡(luò)當(dāng)前的信息指導(dǎo)變量和值的實(shí)例化順序,是啟發(fā)式方法所要解決的主要問(wèn)題。在約束傳播的過(guò)程中如何選取后續(xù)執(zhí)行相容性檢查的變量值直接影響著算法的求解效率。盡早的刪除不滿足相容性的值化簡(jiǎn)網(wǎng)絡(luò),就可以在隨后的約束傳播過(guò)程中避免冗余的約束檢查,從而提高算法的求解效率。本文首先介紹約束滿足問(wèn)題的相關(guān)背景知識(shí)包括常見(jiàn)的相容性算法,結(jié)合弧相容的回溯搜索算法MAC和在求解過(guò)程中指導(dǎo)搜索進(jìn)程的啟發(fā)式方法。由于相容性技術(shù)和啟發(fā)式方法是影響約束滿足問(wèn)題求解效率的關(guān)鍵因素。本文對(duì)相容性技術(shù)中單弧相容算法進(jìn)行了研究,在已有SAC3算法的基礎(chǔ)上加入啟發(fā)式的賦值策略提出改進(jìn)的SAC3_avg Sup算法,具體工作如下:SAC3_avg Sup算法的主要思想為:在采用深度優(yōu)先的搜索策略對(duì)約束網(wǎng)絡(luò)進(jìn)行SAC檢查的過(guò)程中,采取動(dòng)態(tài)啟發(fā)式的策略,隨著求解的不斷進(jìn)行,對(duì)待傳播隊(duì)列Qsac中的值按照變量的平均支持?jǐn)?shù)(即變量的支持?jǐn)?shù)/變量的論域大小)升序排序,優(yōu)先賦值變量的平均支持?jǐn)?shù)小的值。某一變量的平均支持?jǐn)?shù)越小,其被擴(kuò)充為解的可能性就越低,成為死節(jié)點(diǎn)的可能性就越高,故優(yōu)先對(duì)其賦值,目的是提前確定死節(jié)點(diǎn),從而降低算法的檢查次數(shù)和執(zhí)行時(shí)間。實(shí)驗(yàn)通過(guò)SAC3算法和本文提出的SAC3_avg Sup算法分別對(duì)標(biāo)準(zhǔn)庫(kù)測(cè)試用例和隨機(jī)問(wèn)題測(cè)試用例進(jìn)行求解,以求解所需的CPU時(shí)間,實(shí)例化過(guò)程所生成的擴(kuò)展節(jié)點(diǎn)數(shù)和約束檢查的次數(shù)作為評(píng)價(jià)標(biāo)準(zhǔn)。實(shí)驗(yàn)結(jié)果表明,在大多數(shù)問(wèn)題中,SAC3_avg Sup算法的時(shí)間性能比SAC3算法有了顯著提升,擴(kuò)展節(jié)點(diǎn)數(shù)和約束檢查的次數(shù)也有明顯減少。從整體上講,SAC3_avg Sup算法有著更出色的求解性能。
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前3條

1 杜會(huì)盈;李占山;李宏博;沈海嬌;;圖分割在Singleton弧相容算法中的應(yīng)用[J];吉林大學(xué)學(xué)報(bào)(理學(xué)版);2010年06期

2 劉春暉;朱興軍;孫吉貴;姜珊珊;;一種改進(jìn)的雙向singleton弧相容算法[J];吉林大學(xué)學(xué)報(bào)(工學(xué)版);2008年03期

3 ;[J];;年期

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條

1 劉明慧;基于貪心搜索的Singleton弧相容算法的研究[D];吉林大學(xué);2016年

，

本文編號(hào)：1192579