基于笛卡爾積壓縮的負(fù)表約束上相容性算法的研究

發(fā)布時(shí)間：2020-03-20 01:56

【摘要】：約束規(guī)劃是人工智能領(lǐng)域的重要分支,在產(chǎn)品配置、任務(wù)調(diào)度、組合優(yōu)化等問題上有廣泛的應(yīng)用。約束規(guī)劃為實(shí)際問題提供了一種簡(jiǎn)單有效的解決方案,首先通過約束建模將實(shí)際問題抽象成統(tǒng)一的約束模型,然后利用約束求解技術(shù)對(duì)模型進(jìn)行求解。結(jié)合相容性技術(shù)的回溯搜索算法是約束求解的主流方法之一,通過相容性技術(shù)對(duì)回溯搜索過程進(jìn)行剪枝可以提高問題求解的效率。表約束是一種重要的約束的表示形式,通過枚舉支持或者禁止元組將約束以表格的形式呈現(xiàn)。表約束處理的目的是維持約束網(wǎng)絡(luò)的相容性,表約束處理對(duì)整個(gè)問題求解過程影響巨大。廣義弧相容(GAC)是目前應(yīng)用最為廣泛的相容性,其簡(jiǎn)單高效性在大多數(shù)問題實(shí)例上有良好的效果。簡(jiǎn)單表縮減算法(STR算法)及其優(yōu)化(STR2算法和STR3算法)是在表約束上維持廣義弧相容的高效算法,STR算法通過動(dòng)態(tài)維持有效支持元組來(lái)保證約束網(wǎng)絡(luò)的相容性。STR2算法對(duì)STR算法做出兩點(diǎn)改進(jìn),一方面如果兩次相容性檢查過程中變量論域未發(fā)生改變,則跳過該變量上值的有效性檢查。另一方面如果某變量論域中的值均存在有效支持,則停止為該值繼續(xù)尋找支持。STR3算法將表約束的表示形式變?yōu)閷?duì)偶表,在對(duì)偶表上維持約束網(wǎng)絡(luò)的相容性。然而隨著問題中變量個(gè)數(shù)的增加,表約束規(guī)�？赡艹手笖�(shù)階上升,表約束處理的效率將會(huì)下降。有學(xué)者使用笛卡爾積壓縮方法對(duì)正表約束進(jìn)行壓縮,并提出壓縮正表上維持廣義弧相容的方法STR2-C算法和STR3-C算法,在壓縮率較高的問題實(shí)例上,其空間規(guī)模和時(shí)間效率均優(yōu)于STR2算法和STR3算法。負(fù)表是正表的互補(bǔ)表示形式,負(fù)表是約束上所有禁止元組的集合。當(dāng)負(fù)表規(guī)模較小時(shí),直接處理負(fù)表效率更高。STR-N算法是針對(duì)負(fù)表約束提出的簡(jiǎn)單表縮減算法,可以直接在負(fù)表上維持約束網(wǎng)絡(luò)的相容性。STR-N算法計(jì)算有效元組與有效禁止元組的差值,根據(jù)差值是否為零判斷論域中的值是否滿足廣義弧相容,從而進(jìn)一步檢查整個(gè)約束網(wǎng)絡(luò)的相容性。但STR-N算法維持約束網(wǎng)絡(luò)相容性時(shí)需要遍歷負(fù)表中的所有元組,當(dāng)負(fù)表規(guī)模較大時(shí)算法效率較低。因此,受STR2-C算法和STR3-C算法的啟發(fā),本文對(duì)STR-N算法進(jìn)行了優(yōu)化,首先使用笛卡爾積壓縮方法將負(fù)表進(jìn)行壓縮得到壓縮負(fù)表,并提出在壓縮負(fù)表上維持廣義弧相容的方法STRC-N算法。STRC-N算法同樣是通過計(jì)算有效元組與有效禁止元組的差值來(lái)檢查約束網(wǎng)絡(luò)的相容性,但是STRC-N算法統(tǒng)計(jì)有效禁止元組數(shù)的方法卻有所不同。STRC-N算法直接處理有效壓縮禁止元組,有效壓縮禁止元組上一次遍歷可以統(tǒng)計(jì)多個(gè)有效標(biāo)準(zhǔn)禁止元組。經(jīng)過笛卡爾積壓縮后,壓縮負(fù)表的空間規(guī)模更小,STRC-N算法更加節(jié)省空間。得益于壓縮負(fù)表規(guī)模的減小,STRC-N算法相對(duì)于STR-N算法速度更快,效率更高。
【圖文】：

皇后問題,片段,搜索樹