量詞約束滿足問題是人工智能和自動(dòng)推理領(lǐng)域的一個(gè)重要問題.尋找多項(xiàng)式時(shí)間易解子類,是研究此類問題計(jì)算復(fù)雜性的關(guān)鍵.通過分析二元量詞約束滿足問題中的約束關(guān)系特征,以及量詞前綴中的全稱量詞排列的順序,提出了針對(duì)全稱量詞變量子結(jié)構(gòu)的易解性質(zhì)的分析方法.通過該方法,擴(kuò)展了已知的基于Broken-Triangle Property的多項(xiàng)式時(shí)間易解子類,提出了一個(gè)更一般化的量詞約束滿足問題的混合易解子類.討論了易解子類在問題結(jié)構(gòu)分析中的一個(gè)應(yīng)用,即通過易解子類確定量詞約束滿足問題的隱蔽變量集合,并通過實(shí)驗(yàn)分析不同易解子類所確定的集合大小.實(shí)驗(yàn)改造了基于回溯算法的求解器,在回溯過程中加入了易解子類的識(shí)別算法,并采用隨機(jī)約束滿足問題的生成模型作為測試基準(zhǔn).通過對(duì)比實(shí)驗(yàn),驗(yàn)證了提出的多項(xiàng)式時(shí)間易解子類可以識(shí)別出更小的隱蔽變量集合,因此,新提出的易解子類在確定隱蔽變量集合方面更具優(yōu)勢.最后闡述了其他已有的混合易解子類也可以通過類似方法進(jìn)行擴(kuò)展,從而得到更多的一般化的理論結(jié)果. 

【文章來源】：軟件學(xué)報(bào). 2019,30(12)北大核心EICSCD

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

【參考文獻(xiàn)】：
期刊論文
[1]優(yōu)化求解約束滿足問題的MDDc和STR3算法[J]. 楊明奇,李占山,李哲.  軟件學(xué)報(bào). 2017 (12)
[2]負(fù)表約束的簡單表縮減廣泛弧相容算法[J]. 李宏博,梁艷春,李占山.  軟件學(xué)報(bào). 2016(11)
[3]基于量詞約束滿足的機(jī)械產(chǎn)品質(zhì)量特性穩(wěn)健優(yōu)化設(shè)計(jì)方法[J]. 林曉華,馮毅雄,譚建榮,馮勇,高一聰.  機(jī)械工程學(xué)報(bào). 2013(15)
[4]Integrating Standard Dependency Schemes in QCSP Solvers[J]. 金繼偉,馬菲菲,張健.  Journal of Computer Science & Technology. 2012(01)
[5]一種基于環(huán)切割的約束滿足問題求解算法[J]. 李占山,李宏博,張永剛,王孜文.  計(jì)算機(jī)學(xué)報(bào). 2011(08)
[6]求解QBF問題的啟發(fā)式調(diào)查傳播算法[J]. 殷明浩,周俊萍,孫吉貴,谷文祥.  軟件學(xué)報(bào). 2011(07)



本文編號(hào)：3221947