科学网 › 标签 › k-SAT求解练习

标签: k-SAT求解练习

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

子句消去法求k-SAT满足解的基本思路和练习: accsys 2016-10-18 05:27; 姜咏江子句消去法能够一次性求出 k-SAT 的满足解，基本思路十分简单。如果按照穷举法的思路，每一个逻辑变量都有 0 和 1 两个可能解值，因而 n 个变量组合到一起所成的 k-SAT 就要有 2 n 个可能解，这样就会在最坏的情况下，要验证 2 n 次才能够得到有解与无解的结果。子句消去法的思路：假如 k-SAT 有解，那么每个变量的取值 0 或 1 ，就都有可能使 k-SAT 有解或无解。能不能先确定哪些只能取唯一值变量？如果先将唯一值变量的相关子句都消去，那么剩下的子句就可以都是 2 个可选解了，即任选其中一个变量的 0 或 1，再考察剩余的部分，进而可以得到剩余的 SAT 有满足解。子句消去法的可选解是经过“唯一解”消去的判断方法确定的。这要用到我找到的子句块特有的结构规律，即用限位数理论确定的“ k 阶子句块中一个变量有 2 k-1 个相同表现值，不选这个值 k-SAT 就无解 ”。判断变量有唯一解或有解也是通过子句消去法降阶操作完成的。方法是设定一个变量的 0 或 1 值，运用子句消去法逐步检查消去后得到的剩余子句块是唯一解、无解还是多解。如果是唯一解，就继续运用子句消去法，直至无解或多解。这样就可以认定设定的 0 或 1 是否是可选解。再去考察设定这个变量的另一个值。如果 0 和 1 都是其可选解就标记。然后去考查另外的变量。如果某个变量有唯一可选解，那么就可以实际运用子句消去法将 k-SAT 进行化简，对剩余的 k-SAT 继续这种方法，直到剩余的变量都有 2 个可选解。当剩余的 k-SAT 每个变量都有 2 个可选解的时候，任选一个变量的一个值并施行唯一解消去法，就可以得到其关联段的一组解。不相关的另外的变量也施行此法，最终就可以得到所有变量使 k-SAT 成立的确定值。总结一句话：先选变量唯一解，变量全多可选解时，任意选一个值，仍然通过唯一解消去法确定其他变量值。为了让有兴趣的网友能够真正理解子句消去法，并能够实际应用，附上论文和实际练习的简单例子。 2016子句消去法求k-SAT满足解.pdf 子句消去法求SAT满足解（例题）.pdf 全例题.xls 2016-10-18; 个人分类: k-SAT求解|2610 次阅读|0 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: k-SAT求解练习

相关帖子

相关日志

关闭安全验证