科学网

 找回密码
  注册
一个可以快速求解的3SAT例题
姜咏江 2016-5-30 12:41
我这里提供一个3SAT可以用子句消去法快速求解的例题。有兴趣的读者不妨试试在十几分钟内求出满足解如何? 3SAT求解.xls 姜咏江 2016-5-30
个人分类: 3SAT解法|3785 次阅读|没有评论
判定哈密顿图
热度 1 姜咏江 2016-3-4 19:08
判定哈密顿图 姜咏江 判定一个图是不是哈密顿图,只要求出其哈密顿回路即可。有兴趣可研究一下下面的图是不是哈密顿图。 2016-3-4
个人分类: 3SAT解法|5026 次阅读|1 个评论 热度 1
3SAT多关联段求解训练例题
姜咏江 2015-12-26 06:49
3SAT 多关联段求解训练例题 配合我介绍的 3-SAT 解法博文《 子句消去法如何避免进入无解分支求解》(见 http://blog.sciencenet.cn/blog-340399-945926.html )这里上传一个多关联段求解练习的例子,有 100 逻辑变量, 296 个子句。由于用的是 Excel 文件,操作十分方便,设值之后可用编辑 - 删除菜单项将满 ...
个人分类: 3SAT解法|2124 次阅读|没有评论
子句消去法如何避免进入无解分支求解
姜咏江 2015-12-26 05:57
子句消去法如何避免进入无解分支求解 姜咏江 合取范式 3-CNF=1 的解是由 n 个逻辑变量的可满足取值所决定的,用子句消去法求解时,只要一个逻辑变量无法确定使子句值为 1 ,那么整个 3-CNF=1 就无解。实际上,整体的 3-CNF=1 是由一些局部的性质所决定的。这种局部特征集中体现在子句块和关联段,并且随着变量值的 ...
个人分类: 3SAT解法|2562 次阅读|没有评论
柳渝你还认为子句消去法证明的是P=P吗?
热度 1 姜咏江 2015-12-26 05:27
今在网上偶见蒋迅的“数学都知道”还在登载柳渝对子句消去法的否定见解,觉得应该更改了。 我这个人喜欢公开地讨论问题,因为相互竞说能够引人入胜,促进问题的解决。子句消去法求解 3-SAT(包括k-SAT) ,到现在应该是端倪尽现了。不知柳渝博友是否还认为这是一个 P=P 的方法? 诚然,我当初提出的子句消去法 ...
个人分类: 3SAT解法|2592 次阅读|1 个评论 热度 1
k-Sat归约到3sat求解只会得到部分解
姜咏江 2015-12-25 09:37
k-Sat 归约到 3sat 求解只会得到部分解 姜咏江 当 k3 时, k-SAT 归约到 3-SAT 的公式 : k-CNF=( x 1 + x 2 + y 1 ) ( y’ 1 + x 3 + y 2 ) ( y’ 2 + x 3 + y 3 )…( x k-1 + x k + y’ k-3 ) 用 01 表格式表达的 5-CNF 如表 1 所示,最上面一行是变量取值。 表 1 5-CNF 0 1 ...
个人分类: 3SAT解法|3942 次阅读|没有评论
学术研究常常需要你改变思路
热度 1 姜咏江 2015-12-23 09:45
学术研究常常需要你改变思路 姜咏江 学术研究和创新科研常常需要你改变前人的思路,如此才有希望获得独到的成就。我现在可以完全肯定 3-SAT 问题已经被我解决了。 3-SAT 就是一个初等数学的问题。一个初等数学就能够解决的问题,被学术界说得如此神乎其神,其原因多半是研究中缺乏及时地改变思路所至。 搞学术或 ...
个人分类: 3SAT解法|2993 次阅读|2 个评论 热度 1
详解3SAT归约到子集和问题的方法
姜咏江 2015-12-17 08:29
详解 3SAT 归约到子集和问题的方法 姜咏江 《算法导论》一书对 3SAT 规约到子集和论述不够,特作如下详细解释。 1. 确认表示与 01 表示 先给出一个 3-CNF=( x' 1 + x' 2 + x' 3 )( x' 1 + x' 2 + x 3 )( x 1 + x 2 + x ...
个人分类: 3SAT解法|11387 次阅读|没有评论
多解的子句块关联段求解
姜咏江 2015-12-15 11:11
多解的子句块关联段求解 姜咏江 都是多解的子句块形成的关联段,求解时要先解决有可能形成无解的情况。表 1 中可能形成无解的情况只有底纹暗色的部分,那么选取 x 1 和 x 4 及 x 5 的值,就要注意不能够产生无解的剩余子句块。 图 1 中用子句消去法若选择 x 1 = 1 , x 4 = 1 就会出现无解的情况。因而求 ...
个人分类: 3SAT解法|2406 次阅读|没有评论
3SAT剩余子句块多解表示方法
姜咏江 2015-12-15 09:07
3-sat剩余子句块多解表示方法 姜咏江 使用子句消去法对 3-SAT 求解,最后会碰到剩余子句块多解的情况。如果我们只选择 0 和 1 表示,就会使那些很容易就得到的多解无法表出,为此需要引进 确定了一个变量值后 的剩余多解子句块的表示方法,这样一次可以获得更多的 3SAT 解表示。下面表 1 和表 2 中的 $ 表示该 ...
个人分类: 3SAT解法|2840 次阅读|没有评论

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-11-3 05:00

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部