科学网—accsys的博文

3SAT的子句消去法求解方法介绍

姜咏江 2015-12-11 08:56

3SAT 的子句消去法求解方法介绍姜咏江子句消去法求解用 0 和 1 表示的 3SAT 问题简单易学。这里以简单的例子来说明解法。 1. 独立子句块由逻辑变量 x 1 , x 2 , x 3 构成的 3SAT 有最多有 8 个子句，将其用阵列表示，即为表 1 所示。表 1 子句 ...

个人分类: 3SAT解法|3183 次阅读|没有评论

悬赏百万美元千禧难题有了新进展

姜咏江 2015-12-6 13:42

悬赏百万美元千禧难题有了新进展美国克雷数学研究所于 2000 年悬赏 100 万美元求解的 P/NP 问题最近有了新进展。据维基百科说 P/NP 问题直接涉及到计算机科学和数学的方方面面（参见附录）。什么是 P/NP 问题呢？简单地说，能够用函数或映射方式有限次（多项式时间）求解的问题是 P 类问题，而能够用验证方法 ...

个人分类: 3SAT解法|3961 次阅读|没有评论

3-SAT求解中几种无解情况及回避

姜咏江 2015-11-29 16:34

3-SAT 求解中几种无解情况及回避姜咏江表格式给出的 3-SAT 用子句消去法求解很方便，但应该记住无解的情况。无解的情况有：（ 1 ）有 8 个子句的子句块存在；（ 2 ）两个相互关联的子句块，一个关联变量有 0 和 1 的值各 4 个；（ 3 ）动态子句块不可避免的全 2-SAT 可选值；（ 4 ）子句块中两个 ...

个人分类: 3SAT解法|2711 次阅读|没有评论

神奇的子句消去法

姜咏江 2015-11-26 08:45

神奇的子句消去法姜咏江连我自己都想不到子句消去法最终竟然如此简单神奇。这里给出 100 变量的 3-SAT 解题的例子。你可以选择任意的关联段求解，只要记住解题一般步骤如下： 1. 避免出现无解情况（找一个变量有 4 个相同值的子句块，为这个变量设定该值，消去相关子句）； 2. 找出剩下的有唯一解动 ...

个人分类: 3SAT解法|2077 次阅读|没有评论

3SAT解题步骤与规则

姜咏江 2015-11-19 10:08

3SAT 解题步骤与规则姜咏江随着我对 3SAT 的分段子句消去法的深入，使求解 3SAT 的过程也在不断地瘦身，此次介绍的分段子句消去法步骤更加简单化，解法更加易学。一、规则运用分段子句消去法求解 3SAT 的满足解，要遵循如下两条规则：（ 1 ）处理好可能无解子句块。 3SAT 数值表示法可能无解的子句 ...

个人分类: 3SAT解法|2038 次阅读|没有评论

3SAT求解什么情况下可以确定变量只有惟一值？

姜咏江 2015-11-4 08:32

3SAT求解什么情况下可以确定变量只有惟一值？用分段子句消去法去求解 3SAT ，关键是找出变量的惟一值。下面 4 种情况都可以惟一地确定逻辑变量的值。 1. 动态子句块只有一个变量需要确定值； 2. 动态子句块 2 个变量需要确定值，这两个变量刚好组成了 3 ...

个人分类: 3SAT解法|2408 次阅读|没有评论

Can I declare the solution to the 3SAT problem?

姜咏江 2015-10-19 09:29

Can I declare the solution to the 3SAT problem? Jiang Yongjiang Email: accsys@126.com I have been invented the Clause remove by section method that is solving the 3SAT problem. You can see the method in the following: Fig.1 The green clauses have been removed ...

个人分类: 3SAT解法|2168 次阅读|没有评论

3SAT什么情况下无满足解？

姜咏江 2015-10-19 07:47

3SAT 什么情况下无满足解？姜咏江 3-SAT 无满足解的情况非常多。在求解过程中如果能够及时地判断出无满足解，无疑会节省出很多计算时间。用分段子句消去法在求解中出现以下几种情况，就不用再往下浪费时间了。 1. 子句块有 8 个子句； 2. 两变量已经定值，要 ...

个人分类: 3SAT解法|2054 次阅读|没有评论

3-SAT最多有几个满足解？

热度 1 姜咏江 2015-10-18 08:24

3-SAT 最多有几个满足解？姜咏江朋友让我去看每年的 The international SAT Competitions web page ，看了一些数据没搞清楚竞赛的基础。总之没有有效的 SAT 解法，不想费更多时间去了解其中的事情了。就 3-SAT 来说，最多能有多少个满足解？通过子句分段消去法理论可知，都是相互独立的子句块组成的 3-SAT ， ...

个人分类: 3SAT解法|2494 次阅读|2 个评论热度 1

子句分段消去法求解的要点

姜咏江 2015-10-17 18:58

分段子句消去法求解的要点姜咏江 3-SAT 问题的子句分段消去法实际上是一种局部降阶的方法，其本质是将 3-SAT 转化为 2-SAT或1-SAT 求解。用数码表示的 2-SAT 只有 4 种子句，这种变量相同的子句组成了子句块。表 1 左面两列是子句的数值表达方式，右面一列是文字表达方式。表 1 2 阶子句块 x ...

个人分类: 3SAT解法|2364 次阅读|没有评论

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

关闭 安全验证

accsys

关闭安全验证