【摘要】：約束程序(Constraint Programming,CP)是求解組合優(yōu)化問題的一種經(jīng)典方法,在交通、電信、教育等領(lǐng)域發(fā)揮了重要的作用。CP現(xiàn)在已成功用于車輛路徑規(guī)劃、調(diào)度、配置、生物信息等問題的求解中。CP研究的核心問題是約束滿足問題(Constraint Satisfaction Problem,CSP)的建模與求解,人工智能領(lǐng)域中很多復(fù)雜問題都可以建模為CSP來求解,基于CSP的建模和求解方法是當(dāng)前研究熱點(diǎn)。回溯搜索結(jié)合約束傳播的方法是目前公認(rèn)最好的CSP求解方法,而相容性算法是約束傳播過程中使用的主要算法,也是影響約束求解效率的重要因素。通常而言,CSP依靠回溯框架進(jìn)行搜索,在搜索過程中,不斷通過相容性算法移除不相容的值來縮減解的搜索空間,從而大大加快算法搜索解的效率。經(jīng)典的相容性算法有弧相容(Arc Consistency,AC)算法、路徑相容(Path Consistency,PC)算法、單弧相容(Singleton Arc Consistency,SAC)算法、受限路徑相容(Restricted Path Consistency,RPC)算法和最大受限路徑相容(max-Restricted Path Consistency,maxRPC)算法等,其中AC,RPC和maxRPC是三個最流行且效果最好的相容性算法。AC算法因?yàn)楹唵胃咝Ф粡V泛使用。MaxRPC算法剪枝能力強(qiáng),在解決大而難的問題上有非常好的效果,而lmaxRPC3rm(light-max RPC3-residues multidirectional,rm表示多向殘差)算法是maxRPC算法中表現(xiàn)出眾、效率較高的算法。RPC算法具有較強(qiáng)的剪枝能力,且不需要太多時間和空間開銷。其最新最好的版本rRPC3(restricted-RPC3)被證明在求解很多問題上能夠達(dá)到和AC一樣的效果,甚至在部分問題上比AC好,因此rRPC3算法是一個很有前景的算法。啟發(fā)式是算法求解過程中指導(dǎo)變量和值選擇的策略。一個好的變量排序啟發(fā)式(值排序啟發(fā)式)能正確指導(dǎo)變量(值)的選擇,從而大大縮短搜索時間,加快解的搜索過程。因此啟發(fā)式策略在求解CSP中發(fā)揮了重要作用。本文通過對RPC和maxRPC的研究,對非常有前景的rRPC3算法和高效的lmaxRPC3rm算法進(jìn)行改進(jìn)。具體工作為:(1)對RPC算法進(jìn)行改進(jìn):基于位操作改進(jìn)相容性算法的思想已在幾種重要的相容性算法中取得了不錯的效果,我們利用位操作思想來改進(jìn)rRPC3算法。因?yàn)樗惴ú檎褹C支持、PC支持以及PC證人這一過程是算法中進(jìn)行最多、消耗時間最長的一個步驟,因此加快搜索支持和證人的過程非常重要。我們根據(jù)位操作數(shù)據(jù)結(jié)構(gòu)高效快速的特點(diǎn),利用位操作結(jié)構(gòu)對搜索AC支持、PC支持以及PC證人的過程進(jìn)行改進(jìn),使算法搜索、存取相容性支持和PC證人的過程更加便捷高效,以此實(shí)現(xiàn)搜索解更快的效果。(2)對maxRPC算法進(jìn)行改進(jìn):算法lmaxRPC3rm有很好的剪枝能力,但是時空開銷較大。我們對lmaxRPC3rm從算法內(nèi)容和啟發(fā)式兩個方面進(jìn)行改進(jìn)。首先對lmaxRPC3rm算法提出兩種改進(jìn)算法,第一種改進(jìn)不使用原算法存儲AC支持和PC支持的LastAC和LastPC數(shù)據(jù)結(jié)構(gòu),從而使算法高效易于實(shí)現(xiàn),同時減少時間和空間消耗;第二種改進(jìn)不同于lmaxRPC3rm算法同時使用AC殘差支持和PC殘差支持的方式,只保留一種殘差支持來存儲相容性支持,以此存儲和查找AC支持、PC支持和PC證人,進(jìn)而減少很多冗余殘差支持的存取,從而使算法更加高效,同時減少了時間和空間的開銷。另外我們應(yīng)用改進(jìn)的變量排序啟發(fā)式對lmaxRPC3rm算法進(jìn)行改進(jìn)。結(jié)合dom/wdeg(domain/weighted degree)和ABS(Activity-Based Search)啟發(fā)式提出改進(jìn)啟發(fā)式ADW(Activity+dom/wdeg),并將ADW啟發(fā)式,應(yīng)用在改進(jìn)算法中,進(jìn)一步提升算法效率。我們對rRPC3和lmaxRPC3rm算法分別進(jìn)行改進(jìn),并通過實(shí)驗(yàn)評估算法改進(jìn)效果。對rRPC3算法利用位操作結(jié)構(gòu)對查找支持和存儲支持的過程進(jìn)行優(yōu)化,取得了較好的效果。對lmaxRPC3rm算法利用減少冗余的殘差支持存取的思想進(jìn)行改進(jìn),使算法在剪枝能力和開銷之間取得平衡,從而加快算法求解過程。同時將改進(jìn)的變量排序啟發(fā)式應(yīng)用到lmaxRPC3rm的改進(jìn)算法上,使改進(jìn)算法有更好的效果。實(shí)驗(yàn)表明,我們的改進(jìn)算法具有明顯的效果。未來我們打算利用位操作改進(jìn)lmaxRPC3rm算法,并將ADW應(yīng)用于rRPC3的改進(jìn)算法中。
【圖文】：

圖 2.1 n 皇后問題求解包括搜索和推理，約束推理包含很多處理約束中之一。約束傳播是求解一個約束問題的中心傳播包括一些推理，因?yàn)橐恍┲祷蛘咧档慕M合播明確禁止這些值或者值的組合。例如，在一須是 R，從歐洲國家拋棄掉單詞 NORWAY 和 第二個字母必須是 R 的約束條件，不滿足的選個變量1x 和2x ，取值從 1 到 10 的問題中，禁止值 5 和 6 作為1x 或者2x 來傳播這個約束組合空間。

圖 2.2 弧相容執(zhí)行前（左）后（右）的約束網(wǎng)絡(luò)如圖 2.3 是 6 皇后問題上通過回溯進(jìn)行約束傳播后傳播失敗的結(jié)果。左圖在傳播中維持 AC，當(dāng)變量1x 賦值為 2，，通過維持 AC 可以發(fā)現(xiàn)填 1 的部分是不能再放皇后的，即其他變量不可以在這些位置取值。當(dāng)變量2x 賦值為 5 時，通過維持 AC 發(fā)現(xiàn)所有填 2 的地方都不能放皇后，出現(xiàn)域空，從而可以判斷1x 取 2，2x取 5 是無解的，從而進(jìn)行回溯。右圖在約束傳播中不維持 AC�？梢钥闯鲞M(jìn)行到第四個變量才能發(fā)現(xiàn)域空，多進(jìn)行了很多約束檢查。
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：TP18

【參考文獻(xiàn)】

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

1 李宏博;李占山;王濤;;改進(jìn)求解約束滿足問題粗粒度弧相容算法[J];軟件學(xué)報;2012年07期

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

1 劉春暉;基于約束傳播的約束求解方法研究[D];吉林大學(xué);2008年

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

1 崔佳旭;Mistral求解器擴(kuò)展與應(yīng)用研究[D];吉林大學(xué);2016年

2 郭勁松;約束滿足問題（CSP）的求解技術(shù)研究[D];吉林大學(xué);2013年

本文編號：2695554