發(fā)布時(shí)間：2018-06-27 02:10

  本文選題：NP完全問(wèn)題 + 可滿(mǎn)足性問(wèn)題　； 參考：《計(jì)算機(jī)應(yīng)用》2017年12期

【摘要】：針對(duì)學(xué)習(xí)子句數(shù)量有限或相似度高導(dǎo)致歷史信息有限、搜索樹(shù)不平衡的問(wèn)題,提出了基于動(dòng)態(tài)獎(jiǎng)懲的分支策略。首先,對(duì)每次單子句傳播的變?cè)M(jìn)行懲罰,依據(jù)變?cè)欠癞a(chǎn)生沖突和產(chǎn)生沖突的間隔,確立不同的懲罰函數(shù);其次,在學(xué)習(xí)階段,利用學(xué)習(xí)子句確定對(duì)構(gòu)造沖突有益的變?cè)?非線性增加它們的活躍度;最后,選擇活躍度最大的變?cè)鳛樾路种ё冊(cè)�。在glucose3.0算法基礎(chǔ)上,完成了改進(jìn)的動(dòng)態(tài)獎(jiǎng)懲算法——AP7。實(shí)驗(yàn)結(jié)果表明,相比glucose3.0算法,AP7算法的剪枝率提高了14.2%~29.3%,少數(shù)算例剪枝率的提高可達(dá)51%,且改進(jìn)后的AP7算法相比glucose3.0算法,運(yùn)行時(shí)間縮短了7%以上。所提分支策略可以有效降低搜索樹(shù)規(guī)模,使搜索樹(shù)更加平衡,減少計(jì)算時(shí)間。
[Abstract]:Aiming at the problem that the limited number of learning clauses or the high similarity result in the limited historical information and the imbalance of search tree, a branch strategy based on dynamic rewards and punishments is proposed. First of all, the variables propagated by each single child sentence are punished, and different penalty functions are established according to whether the variables produce conflicts and the interval between them. Secondly, in the learning stage, learning clauses are used to determine the variables that are beneficial to the construction of conflicts. Finally, the most active variables are selected as new branch variables. On the basis of glucose3.0 algorithm, the improved dynamic reward and punishment algorithm AP7. The experimental results show that compared with glucose3.0 algorithm, the pruning rate of AP7 algorithm is increased by 14.2and 29.3s, the pruning rate of a few examples can be increased by 51%, and the running time of the improved AP7 algorithm is reduced by more than 7% compared with that of glucose3.0 algorithm. The proposed branching strategy can effectively reduce the size of the search tree, make the search tree more balanced and reduce the computing time.
【作者單位】： 武漢科技大學(xué)理學(xué)院;華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;
【基金】：湖北省教育廳科學(xué)研究計(jì)劃項(xiàng)目(B2016015)~~
【分類(lèi)號(hào)】：TP301.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 畢忠勤;陳光喜;單美靜;;可滿(mǎn)足性問(wèn)題全部解的求解算法[J];計(jì)算機(jī)工程與應(yīng)用;2009年03期

2 周康;魏傳佳;劉朔;王防修;;可滿(mǎn)足性問(wèn)題的閉環(huán)DNA算法[J];華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年07期

3 王建新;管利娜;江國(guó)紅;;可滿(mǎn)足性問(wèn)題的研究綜述[J];計(jì)算技術(shù)與自動(dòng)化;2009年04期

4 湛少鋒;關(guān)于部分變?cè)姆浅７�(wěn)定性[J];武漢測(cè)繪科技大學(xué)學(xué)報(bào);1990年04期

5 林耿;;可滿(mǎn)足性問(wèn)題的填充函數(shù)算法[J];閩江學(xué)院學(xué)報(bào);2011年02期

6 郝遂興;MPROLOG語(yǔ)言參考手冊(cè)[J];計(jì)算機(jī)工程與應(yīng)用;1985年11期

7 黃拙,張健;由一階邏輯公式得到命題邏輯可滿(mǎn)足性問(wèn)題實(shí)例(英文)[J];軟件學(xué)報(bào);2005年03期

8 李未;黃雄;;命題邏輯可滿(mǎn)足性問(wèn)題的算法分析[J];計(jì)算機(jī)科學(xué);1999年03期

9 許可,李未;SAT問(wèn)題的相變現(xiàn)象[J];中國(guó)科學(xué)E輯:技術(shù)科學(xué);1999年04期

10 張德富,李光輝;求解可滿(mǎn)足性問(wèn)題的兩個(gè)啟發(fā)式策略(英文)[J];常德師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2001年03期

相關(guān)碩士學(xué)位論文 前10條

1 賈yN愷;基于深度特征學(xué)習(xí)的目標(biāo)檢測(cè)與跟蹤算法研究[D];西安科技大學(xué);2017年

2 張燦龍;不確定DM-chameleon聚類(lèi)算法在滑坡危險(xiǎn)性預(yù)測(cè)的研究及應(yīng)用[D];江西理工大學(xué);2017年

3 鄧曉瑤;可滿(mǎn)足性問(wèn)題的預(yù)處理策略研究與分析[D];天津大學(xué);2014年

4 靳慶庚;基于代數(shù)幾何的可滿(mǎn)足性問(wèn)題連續(xù)求解方法研究[D];廣西民族大學(xué);2016年

5 李韶華;可滿(mǎn)足性問(wèn)題和圖染色的一些研究[D];中國(guó)科學(xué)院研究生院（軟件研究所）;2005年

6 葛平平;可滿(mǎn)足性問(wèn)題的改進(jìn)型類(lèi)組織P系統(tǒng)的求解研究[D];安徽理工大學(xué);2015年

7 管利娜;參數(shù)化可滿(mǎn)足性問(wèn)題的研究[D];中南大學(xué);2009年

8 熊玲芳;基于擬物的布爾可滿(mǎn)足性問(wèn)題連續(xù)求解方法研究[D];廣西民族大學(xué);2013年

9 王芙;改進(jìn)的蟻群算法求解可滿(mǎn)足性問(wèn)題[D];華南理工大學(xué);2012年

10 丁志宇;應(yīng)用線性代數(shù)求解可滿(mǎn)足性問(wèn)題的研究與實(shí)現(xiàn)[D];中山大學(xué);2014年

，

本文編號(hào)：2072266