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

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

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

【參考文獻(xiàn)】：
期刊論文
[1]優(yōu)化求解約束滿(mǎn)足問(wèn)題的MDDc和STR3算法[J]. 楊明奇,李占山,李哲.  軟件學(xué)報(bào). 2017 (12)
[2]負(fù)表約束的簡(jiǎn)單表縮減廣泛弧相容算法[J]. 李宏博,梁艷春,李占山.  軟件學(xué)報(bào). 2016(11)
[3]基于量詞約束滿(mǎn)足的機(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)切割的約束滿(mǎn)足問(wèn)題求解算法[J]. 李占山,李宏博,張永剛,王孜文.  計(jì)算機(jī)學(xué)報(bào). 2011(08)
[6]求解QBF問(wèn)題的啟發(fā)式調(diào)查傳播算法[J]. 殷明浩,周俊萍,孫吉貴,谷文祥.  軟件學(xué)報(bào). 2011(07)



本文編號(hào)：3221947