[發(fā)明專利]基于擴展規(guī)則的布爾可滿足性問題的求解方法

在審

• 申請?zhí)枺?/td>: 201910747374.2
• 申請日: 2019-08-14
• 公開（公告）號: CN110689128A
• 公開（公告）日: 2020-01-14
• 發(fā)明（設(shè)計）人: 王金艷;胡春;李先賢
• 申請（專利權(quán)）人: 廣西師范大學(xué)
• 主分類號: G06N5/04
• 分類號: G06N5/04
• 代理公司: 45107 桂林市持衡專利商標(biāo)事務(wù)所有限公司
• 代理人: 陳躍琳

1.基于擴展規(guī)則的布爾可滿足性問題的求解方法，其特征是，具體包括步驟如下：

步驟1、設(shè)定最大主迭代次數(shù)maxStep和最大次迭代次數(shù)subMaxStep；令CNF公式集中所有子句的初始權(quán)值均為1，CNF公式集中所有變量的初始格局改變狀態(tài)為1，迭代次數(shù)i為0；

步驟2、根據(jù)輸入的CNF公式集，得到輸入變量集M及其變量個數(shù)MCount，以及輸入子句集C及其子句個數(shù)CCount；

步驟3、首先遍歷CNF公式集得到其中最長子句集S；然后遍歷最長子句集S，并記錄每個文字出現(xiàn)的次數(shù)；最后將所有文字按出現(xiàn)次數(shù)進行排序，并將出現(xiàn)次數(shù)較多前K位的文字的否定形成限定子句u；其中K為設(shè)定值；

步驟4、將限定子句u中的文字轉(zhuǎn)成變量形式后，放入到限定變量集W中，并將輸入變量集M與限定變量集W的差集中的變量放入到隨機變量集Y中；

步驟5、對于隨機變量集Y中的每個變量，隨機選擇每個變量的文字來與限定子句u中文字進行合并，形成初始極大項；

步驟6、判斷當(dāng)前極大項是否可以被CNF公式集中的子句擴展：如果所有子句均不能擴展當(dāng)前極大項，則輸出當(dāng)前極大項，并結(jié)束；否則，將轉(zhuǎn)至步驟7；

步驟7、計算CNF公式集中每個變量的主貢獻值、次貢獻值和綜合貢獻值，其中：

變量x的主貢獻值Score_er(x)為：

Score_er(x)＝cost_er(F，e)-cost_er(F，e’) (1)

變量x的次貢獻值Subscore_er(x)為：

Subscore_er(x)＝Submake_er(F，e’)-Subbreak_er(F，e’) (2)

變量x的綜合貢獻值CScore_er(x)為：

CScore_er(x)＝Score_er(x)+Subscore_er(x)/d (3)

式中，e為當(dāng)前極大項，e’為當(dāng)前極大項e翻轉(zhuǎn)變量x之后得到的當(dāng)前翻轉(zhuǎn)極大項；cost_er(F，e)表示CNF公式集中所有能擴展當(dāng)前極大項e的子句的權(quán)值之和，cost_er(F，e’)表示CNF公式集中所有能擴展當(dāng)前翻轉(zhuǎn)極大項e’的子句的權(quán)值之和；Submake_er(F，e’)表示在當(dāng)前翻轉(zhuǎn)極大項e’下，CNF公式集中的關(guān)鍵子句變?yōu)榉€(wěn)定子句的權(quán)值之和，Subbreak_er(F，e’)表示在當(dāng)前翻轉(zhuǎn)極大項e’下，CNF公式集中的穩(wěn)定子句變?yōu)殛P(guān)鍵子句的權(quán)值之和；d為人為設(shè)定的正整數(shù)；

步驟8、計算CNF公式集的子句個數(shù)CCount與變量個數(shù)MCount的比值：如果該比值大于預(yù)設(shè)的比值閾值，則轉(zhuǎn)至步驟9；否則，轉(zhuǎn)至步驟13；

步驟9、將主貢獻值和綜合貢獻值都大于0且格局改變狀態(tài)為1的變量放入候選格局綜合下降變量集P中；

步驟10、判斷當(dāng)前迭代次數(shù)i是否達到最大次迭代次數(shù)SubMaxStep：如果未達到，則令當(dāng)前迭代次數(shù)i加1，并轉(zhuǎn)至步驟11；否則，轉(zhuǎn)至步驟12；

步驟11、判斷候選格局綜合下降變量集P是否為空：如果候選格局綜合下降變量集P不為空，且候選格局綜合下降變量集P與隨機變量集Y的交集不為空，則將候選格局綜合下降變量集P與隨機變量集Y的交集中的變量放入限定格局綜合下降候選變量集R，并從限定候選格局綜合下降變量集R中選出具有最大綜合貢獻值的變量作為抽選變量，并轉(zhuǎn)至步驟17；否則，從隨機變量集Y中隨機選擇一個變量作為抽選變量，并轉(zhuǎn)至步驟17；

步驟12、判斷候選格局綜合下降變量集P是否為空：如果候選格局綜合下降變量集P不為空，則從候選格局綜合下降變量集P中選出具有最大綜合貢獻值的變量作為抽選變量，并轉(zhuǎn)至步驟17；否則，采用PAWS_ER規(guī)劃對CNF公式集中的子句的權(quán)值進行更新后，從CNF公式集中所有能擴展當(dāng)前極大項的子句中，隨機挑選出一個最長時間沒有翻轉(zhuǎn)的變量作為抽選變量，并轉(zhuǎn)至步驟17；

步驟13、將主貢獻值大于0且格局改變狀態(tài)為1的變量放入候選格局下降變量集H中；將主貢獻值大于預(yù)設(shè)貢獻閾值的變量放入到候選有意義下降變量集Q中；

步驟14、判斷當(dāng)前迭代次數(shù)i是否達到最大次迭代次數(shù)SubMaxStep：如果未達到，則令當(dāng)前迭代次數(shù)i加1，并轉(zhuǎn)至步驟15；否則，則轉(zhuǎn)至步驟16；

步驟15、判斷候選格局下降變量集H是否為空：

如果候選格局下降變量集H不為空，且候選格局下降變量集H與隨機變量集Y的交集不為空，則將候選格局下降變量集H與隨機變量集Y的交集中的變量放入限定候選格局下降變量集Z，并從限定候選格局下降變量集Z中選出具有最大主貢獻值并且具有最大次貢獻值的變量作為抽選變量，并轉(zhuǎn)至步驟17；

否則，進一步判斷候選有意義下降變量集Q是否為空：如果候選有意義下降變量集Q不為空，且候選有意義下降變量集Q與隨機變量集Y的交集不為空，則將候選有意義下降變量集Q與隨機變量集Y的交集中的變量放入限定候選有意義下降變量集G，并從限定候選有意義下降變量集G中選出具有最大主貢獻值并且具有最大次貢獻值的變量作為抽選變量，并轉(zhuǎn)至步驟17；否則，從隨機變量集Y中隨機選擇一個變量作為抽選變量，并轉(zhuǎn)至步驟17；

步驟16、判斷候選格局下降變量集H是否為空：

如果候選格局下降變量集H不為空，則從候選格局下降變量集H中選出具有最大主貢獻值并且具有最大次貢獻值的變量作為抽選變量，并轉(zhuǎn)至步驟17；

否則，進一步判斷候選有意義下降變量集Q是否為空：如果候選有意義下降變量集Q不為空，則從候選有意義下降變量集Q中選出具有最大主貢獻值并且具有最大次貢獻值的變量作為抽選變量，并轉(zhuǎn)至步驟17；否則，采用PAWS_ER規(guī)劃對CNF公式集中的子句的權(quán)值進行更新后，從CNF公式集中所有能擴展當(dāng)前極大項的子句中，隨機挑選出一個最長時間沒有翻轉(zhuǎn)的變量作為抽選變量，并轉(zhuǎn)至步驟17；

步驟17、對當(dāng)前極大項中的抽選變量的文字進行翻轉(zhuǎn)，得到一個更新的當(dāng)前極大項；同時，將抽選變量的格局改變狀態(tài)置0，并將抽選變量的鄰居變量的格局改變狀態(tài)置1；

步驟18、判斷當(dāng)前迭代次數(shù)i是否達到最大次迭代次數(shù)SubMaxStep：

如果未達到，則轉(zhuǎn)至步驟6；否則，令當(dāng)前迭代次數(shù)i加1，并進一步判斷當(dāng)前迭代次數(shù)i是否達到最大主迭代次數(shù)maxStep：如果未達到，則轉(zhuǎn)至步驟6；如果達到，則輸出無解，并結(jié)束。