約束滿足問題是經(jīng)典NP-hard問題,其基本算法是遞歸形式的回溯算法和弧一致性算法。將弧相容與回溯搜索結(jié)合,可以有效降低解空間大小。針對(duì)弧相容的維持問題,提出一種新的基于時(shí)序計(jì)數(shù)的傳播方案,用于增量更新約束子網(wǎng)。將accumulateRevision和pushRevison作為雙向修訂的主要方法,以減少修訂次數(shù)和域過(guò)濾變量的數(shù)量。實(shí)驗(yàn)結(jié)果表明,與經(jīng)典的基于關(guān)系的方案和基于變量的傳播方案相比,該方案的整體求解速度明顯提高,且具有較少的修訂時(shí)間。 

【文章來(lái)源】：計(jì)算機(jī)工程. 2020,46(04)北大核心CSCD

【文章頁(yè)數(shù)】：7 頁(yè)

【部分圖文】：

二元約束CSP的一個(gè)子網(wǎng)絡(luò)

本文實(shí)驗(yàn)是在3.20 GHz Intel 8th core i5處理器上運(yùn)行,內(nèi)存為8 GB。圖2為使用基于約束關(guān)系、基于混合變量關(guān)系和基于變量的雙向傳播策略,這3種策略應(yīng)用queue在不同測(cè)試集的修訂次數(shù)的平均對(duì)比結(jié)果。圖3為3種傳播策略使用dom/ddeg在不同測(cè)試集的修訂次數(shù)。圖4給出3種傳播策略使用queue在不同測(cè)試集的修訂時(shí)間。圖5給出3種傳播策略使用dom/ddeg在不同測(cè)試集的修訂時(shí)間。本文測(cè)試了超過(guò)1 600個(gè)實(shí)例,并在有限的600 s時(shí)間內(nèi)區(qū)分是否超時(shí),有關(guān)測(cè)試實(shí)例的詳細(xì)信息可以在C.lecoutre的主頁(yè)上找到。圖3 3種傳播策略使用dom/ddeg在不同測(cè)試集上修訂次數(shù)的對(duì)比結(jié)果

3種傳播策略使用dom/ddeg在不同測(cè)試集上修訂次數(shù)的對(duì)比結(jié)果

【參考文獻(xiàn)】：
期刊論文
[1]一種基于時(shí)間戳的簡(jiǎn)單表縮減算法[J]. 楊明奇,李占山,張家晨.  軟件學(xué)報(bào). 2019(11)
[2]基于啟發(fā)式的約束滿足問題AC系列算法改進(jìn)研究[J]. 蔣李鳴,呂佳宇,何哲華,馮澤斌.  軟件工程. 2018(02)
[3]Dom/ddeg自主分支輔助決策約束求解[J]. 王海燕,李闖,張良,董延華.  吉林大學(xué)學(xué)報(bào)(理學(xué)版). 2014(06)
[4]時(shí)間約束優(yōu)化問題的解空間壓縮方法研究[J]. 張博洋,朱延廣,楊峰.  計(jì)算機(jī)工程. 2012(14)
[5]改進(jìn)求解約束滿足問題粗粒度弧相容算法[J]. 李宏博,李占山,王濤.  軟件學(xué)報(bào). 2012(07)
[6]基于約束理論的工作流適應(yīng)性改進(jìn)[J]. 劉俊莉,歐陽(yáng)松.  計(jì)算機(jī)工程. 2010(11)

碩士論文
[1]CSP中的約束傳播策略及啟發(fā)式的研究[D]. 楊微.吉林大學(xué) 2018



本文編號(hào)：3216526