[發明專利]求解加權最大可滿足性問題的局部搜索求解方法和系統

在審

• 申請號: 201711034941.7
• 申請日: 2017-10-30
• 公開（公告）號: CN109726362A
• 公開（公告）日: 2019-05-07
• 發明（設計）人: 初一;羅川;尤海航
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: G06F17/18
• 分類號: G06F17/18;G06F17/10
• 代理公司: 北京律誠同業知識產權代理有限公司 11006
• 代理人: 祁建國;梁揮

1.一種求解加權最大可滿足性問題的局部搜索求解方法，包括：通過將實際問題編碼為加權帶硬子句的最大可滿足性問題，得到加權帶硬約束的合取范式，隨后根據隨機局部搜索法對該合取范式進行迭代搜索，得到一組結果變量，并將該結果變量的賦值作為最優解進行輸出，其特征在于，該迭代搜索包括：

概率獲取步驟，獲取用戶預設概率p；

以概率1-p執行第一搜索步驟，該第一搜索步驟包括：搜索是否存在第一變量，若存在，則在所有第一變量中選擇第一分數最大的變量作為待翻轉變量進行翻轉；否則更新該硬子句的權值并搜索是否存在第二變量，若存在，則在所有第二變量中選擇總分數最大的變量作為待翻轉變量進行翻轉；否則搜索是否存在未滿足硬子句，若存在，則在所有未滿足硬子句中隨機選中一個未滿足硬子句，并在選中的未滿足硬子句中隨機選擇一個變量作為待翻轉變量進行翻轉，否則，隨機選中一個未滿足軟子句，并在選中的未滿足軟子句中隨機選擇一個變量作為待翻轉變量進行翻轉。

2.如權利要求1所述的求解加權最大可滿足性問題的局部搜索求解方法，其特征在于，在對該待翻轉變量進行翻轉前執行判斷步驟，若該待翻轉變量的格局從上一次翻轉到本次迭代搜索之間沒有發生變化，則該待翻轉變量在本次迭代搜索中保持不變。

3.如權利要求2所述的求解加權最大可滿足性問題的局部搜索求解方法，其特征在于，該迭代搜索還包括：

以概率p執行第二搜索步驟，該第二搜索步驟包括：若存在未滿足硬子句，則隨機的選擇一個未滿足硬子句，并在選擇的未滿足硬子句中選擇一個第二分數最大的變量作為待翻轉變量進行翻轉，若硬子句全部被滿足，則隨機的選擇一個未滿足軟子句，并在選擇的未滿足軟子句中選擇一個第二分數最大的變量作為待翻轉變量進行翻轉。

4.如權利要求1所述的求解加權最大可滿足性問題的局部搜索求解方法，其特征在于，更新該硬子句的權值具體包括：對未滿足硬子句增大其權值，對滿足硬子句減小其權值。

5.如權利要求1所述的求解加權最大可滿足性問題的局部搜索求解方法，其特征在于，還包括：當迭代搜索結束后，輸出該最優解以及該最優解的花費，若沒有找到該最優解，則輸出沒有找到可行解。

6.一種求解加權最大可滿足性問題的局部搜索求解系統，包括：通過將實際問題編碼為加權帶硬子句的最大可滿足性問題，得到加權帶硬約束的合取范式，隨后根據隨機局部搜索法對該合取范式進行迭代搜索，得到一組結果變量，并將該結果變量的賦值作為最優解進行輸出，其特征在于，該迭代搜索包括：

概率獲取模塊，用于獲取用戶預設概率p；

以概率1-p調用第一搜索模塊，該第一搜索模塊用于，搜索是否存在第一變量，若存在，則在所有第一變量中選擇第一分數最大的變量作為待翻轉變量進行翻轉；否則更新該硬子句的權值并搜索是否存在第二變量，若存在，則在所有第二變量中選擇總分數最大的變量作為待翻轉變量進行翻轉；否則搜索是否存在未滿足硬子句，若存在，則在所有未滿足硬子句中隨機選中一個未滿足硬子句，并在選中的未滿足硬子句中隨機選擇一個變量作為待翻轉變量進行翻轉，否則，隨機選中一個未滿足軟子句，并在選中的未滿足軟子句中隨機選擇一個變量作為待翻轉變量進行翻轉。

7.如權利要求6所述的求解加權最大可滿足性問題的局部搜索求解系統，其特征在于，在對該待翻轉變量進行翻轉前調用判斷模塊，該判斷模塊，用于判斷若該待翻轉變量的格局從上一次翻轉到本次迭代搜索之間沒有發生變化，則該待翻轉變量在本次迭代搜索中保持不變。

8.如權利要求7所述的求解加權最大可滿足性問題的局部搜索求解系統，其特征在于，該迭代搜索還包括：

以概率p調用第二搜索模塊，該第二搜索模塊用于，若存在未滿足硬子句，則隨機的選擇一個未滿足硬子句，并在選擇的未滿足硬子句中選擇一個第二分數最大的變量作為待翻轉變量進行翻轉，若硬子句全部被滿足，則隨機的選擇一個未滿足軟子句，并在選擇的未滿足軟子句中選擇一個第二分數最大的變量作為待翻轉變量進行翻轉。