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

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

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

【部分圖文】：

二元約束CSP的一個子網(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在不同測試集的修訂次數(shù)的平均對比結(jié)果。圖3為3種傳播策略使用dom/ddeg在不同測試集的修訂次數(shù)。圖4給出3種傳播策略使用queue在不同測試集的修訂時間。圖5給出3種傳播策略使用dom/ddeg在不同測試集的修訂時間。本文測試了超過1 600個實(shí)例,并在有限的600 s時間內(nèi)區(qū)分是否超時,有關(guān)測試實(shí)例的詳細(xì)信息可以在C.lecoutre的主頁上找到。圖3 3種傳播策略使用dom/ddeg在不同測試集上修訂次數(shù)的對比結(jié)果

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

【參考文獻(xiàn)】：
期刊論文
[1]一種基于時間戳的簡單表縮減算法[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]時間約束優(yōu)化問題的解空間壓縮方法研究[J]. 張博洋,朱延廣,楊峰.  計(jì)算機(jī)工程. 2012(14)
[5]改進(jìn)求解約束滿足問題粗粒度弧相容算法[J]. 李宏博,李占山,王濤.  軟件學(xué)報(bào). 2012(07)
[6]基于約束理論的工作流適應(yīng)性改進(jìn)[J]. 劉俊莉,歐陽松.  計(jì)算機(jī)工程. 2010(11)

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



本文編號：3216526