[发明专利]求解加权最大可满足性问题的局部搜索求解方法和系统

摘要

本发明涉及一种求解加权最大可满足性问题的局部搜索求解方法和系统，包括：搜索第一变量，若存在则在所有第一变量中选择第一分数最大的变量进行翻转；否则搜索第二变量，若存在则在所有第二变量中选择总分数最大的变量进行翻转；否则搜索未满足硬子句，若存在则在所有未满足硬子句中随机选中一未满足硬子句，并在选中的未满足硬子句中随机选择一个变量进行翻转，否则随机选中一未满足软子句并在选中的未满足软子句中随机选择一个变量进行翻转，在对待翻转变量进行翻转前执行判断步骤，若待翻转变量的格局从上一次翻转到本次迭代搜索之间没有发生变化，则待翻转变量在本次迭代搜索中保持不变。本文发明使局部搜索求解的格局检测策略限制更加宽松。

主权项

1.一种求解加权最大可满足性问题的局部搜索求解方法，包括：通过将实际问题编码为加权带硬子句的最大可满足性问题，得到加权带硬约束的合取范式，随后根据随机局部搜索法对该合取范式进行迭代搜索，得到一组结果变量，并将该结果变量的赋值作为最优解进行输出，其特征在于，该迭代搜索包括：概率获取步骤，获取用户预设概率p；以概率1‑p执行第一搜索步骤，该第一搜索步骤包括：搜索是否存在第一变量，若存在，则在所有第一变量中选择第一分数最大的变量作为待翻转变量进行翻转；否则更新该硬子句的权值并搜索是否存在第二变量，若存在，则在所有第二变量中选择总分数最大的变量作为待翻转变量进行翻转；否则搜索是否存在未满足硬子句，若存在，则在所有未满足硬子句中随机选中一个未满足硬子句，并在选中的未满足硬子句中随机选择一个变量作为待翻转变量进行翻转，否则，随机选中一个未满足软子句，并在选中的未满足软子句中随机选择一个变量作为待翻转变量进行翻转。