科学网 › 标签 › 分段子句消去法

标签: 分段子句消去法

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

没有相关内容

相关日志

3-SAT求解基本方法: accsys 2015-11-18 08:38; 3-SAT 求解基本方法姜咏江分段子句消去法的求解，最关键的是关联段求解。 3SAT 关联段无解只有 3 中情况：（ 1 ）出现有 8 个子句的子句块；（ 2 ）出现了只有一个变量需要确定值，却无值可选的动态块；（ 3 ）在确定了一个变量值之后，出现了 4 个 2SAT 子句的动态块，叫全 2sat 动态块。 3SAT 解题中如何排除无解分支？基本方法是：先选择4个同变量值的子句块定值，随时注意避免出现全2sat动态块。下面我们以实际例子来加以说明。图 1 中有变量 x6 和 x8 有 4 个相同的值，不选这个值就会进入到无解分支。因而选择 x6 ＝ 0 、 x8 ＝ 0 。图 1 子句块变量4同值消去相关子句，出现了有唯一解的动态块（图2 中有 3 个子句的子句块）。图 2 出现了唯一解动态子句块选定动态块解，并消去相关子句就得到了图3 ，其中有唯一解的子句块 2 个。图 3 唯一解的一个子句子句块消去这两个唯一解子句块，得到图4 。图4 中除了一个 4 子句块之外，都是有 1 个子句或 2 个子句的子句块。这有 4 个子句的子句块是由两对互反子句构成的，因而也是多解子句块。图 4 多解的4子句子句块对于都是多解的子句块或动态子句块都可以设定变量值得到相应的解。如图5 所示，可有此 3SAT 的满足解为 000010101*1010***01* 。“ * ”表示可以为 0 或 1 。图 5 选择关联子句多的变量值总结一下，当固定了一个变量之后，有一个、两个子句的子句块总有多解。有三个子句的子句块可能有唯一解或多解；有四、五和六个子句的子句块都可能出现无解或多解的情况，七个子句的子句块只有唯一解。一般过程：（ 1 ）先寻找唯一解或可能无解的子句块，若有无解子句块则关联段无解。进而3SAT无解。（ 2 ）设定值时应避开无解情况。（ 3 ）最后处理都是多解的关联子句块，可设定关联变量值使消去的子句最多。定理：变量 4 同值不取，则发生无解。此定理证明留给读者如何？（参考【 1 】定理 8 ） 2015-11-18 【 1 】 http://blog.sciencenet.cn/blog-340399-928224.html; 个人分类: 教学笔记|4210 次阅读|0 个评论

3-SAT问题为什么长期得不到解决？: accsys 2015-11-2 09:38; 3-SAT 问题为什么长期得不到解决？ 3-SAT 是解决 P/NP 问题的关键问题之一，可就是长期得不到有效的解法，原因在哪里呢？第一、人们过于将 3-SAT 问题做为整体性问题来求解了。例如，随便写出 100 个变量的 3-SAT ，如果你将 3 个逻辑变量的子句放到一起，如果同变量的子句有 8 个（不包括同一变量正反都在的子句），那么 3-SAT 肯定就没有满足解。但是，如果将那些子句无规律地放到一起，这种易于判断的特征就消失了。再如，没有共同逻辑变量的子句之间是无关的，因而各自变量值的变化不影响局部的求解。第二、 3-SAT 的关联段解决定着整体的解。 3-SAT 是否有解是由那些相互有共同变量关联的段来决定的。关联段分为一元关联，二元关联和三元关联。 3-SAT 的三元关联的段之间是相互独立的，不会超过 8 个子句（不包括同一变量正反都在的子句）。二元关联和一元关联会形成长段。实际上，关联段是 3-SAT 的基本组成部分，只要这些基本组成的关联段都有解，那么 3-SAT 整体才有解；只要其中任何一个关联段无解， 3-SAT 整体就无解。第三、每个 3-SAT 的关联段最多需要 7 次求解过程就可以将该关联段的解都求出。关联段解的长度是由段中包含的逻辑变量数来确定的。用分段子句消去法求解的次数是由起始子句块的可能解数量确定的。有解的子句块最多有 7 个可能解，因而关联段最多要进行 7 次求解过程。第四、利用分段子句消去法才能够在求解中判断出变量应该的取值。由于 3-SAT 关联段是否有解要看关联变量之间的相互制约情况。这其中制约最简单的情况是 2 个变量值已经确定，看所有通过第三个变量相关的子句是否能都设定这一个变量值消去。复杂些的是有一个变量值确定的有 2 个共同变量的子句，是否可以找到这两个变量的值，将这些子句全部消去。分段子句消去法给出了关联段求解中有一解和无解的判断方法，并且给出了有 2 个解的延续处理方法，从而能够顺利地求出关联段的解。分段子句消去法给出的这些函数方法是以往 3-SAT 研究中未见有人使用过的。 2015-11-2; 个人分类: 教学点滴|6458 次阅读|0 个评论

子句分段消去法求解的要点: accsys 2015-10-17 18:58; 分段子句消去法求解的要点姜咏江 3-SAT 问题的子句分段消去法实际上是一种局部降阶的方法，其本质是将 3-SAT 转化为 2-SAT或1-SAT 求解。用数码表示的 2-SAT 只有 4 种子句，这种变量相同的子句组成了子句块。表 1 左面两列是子句的数值表达方式，右面一列是文字表达方式。表 1 2 阶子句块 x y 子句 0 0 x’+y’ 1 0 x+y’ 0 1 x’+y 1 1 x+y 这 4 种子句同时出现在 2-SAT 中，自然找不到逻辑变量 x 、 y 的满足这些子句值都是 1 的解。但如果这 4 个子句中仅出现 3 个，那么我们就可以确定这个子句块有惟一的一组变量值使 3 个子句的值都是 1 。如果子句块只出现 1 个或 2 个子句，那么这个子句块就有两组值使这 1 个或 2 个子句的值都是 1 。如果是 3-SAT 的子句块，则出现 8 个子句一定无块解。确定了一个变量值的 3-SAT 动态块实际上是一个 2-SAT 的子句块，因而可以按照 2-SAT 子句块求解。对于确定了 2 个变量的动态块，相当于 1-SAT 子句块，这时只要这个变量值出现了不同，那么就肯定无解。对于高阶的 k-SAT ，我们可以依据这种降阶的方法求解。先从有唯一解的子句块开始设定变量值，通过子句消去法得到降阶的动态块，再依据降阶法求解。若子句关联段有多解，要将其解全部求出，然后与其它关联段解组合，这样才能够得到 3-SAT 的全部满足解。分段子句消去法： http://blog.sciencenet.cn/blog-340399-928224.html 2015-10-17; 个人分类: 3SAT解法|2203 次阅读|0 个评论

100个变量的3-SAT求解实例: accsys 2015-10-8 20:50; 100 个变量的 3-SAT 求解实例姜咏江用分关联段子句消去法求 3-SAT 的满足解并不困难。我这里有一个 100 个变量的求解实例。手工操作也用不了多长时间。求解时，要先找有唯一解的子句块，从各个唯一解的子句块解出发，运用剩余动态块有唯一解的判定，做起来并不困难。遇到段多解留在最后处理，可以按需要取值。如果将多解留下，最终可以表达出更多的解。第二张表就是这个意思。我用 Excel 的窗口分割，将解的变量值设定放在上面，滚动下面窗口，不影响观查变量直的设定。为了朋友们能够观看过程，仍然用绿色覆盖消去的子句，其实直接消去操作起来更容易。解法请参考： http://blog.sciencenet.cn/blog-340399-925143.html 100个变量的3sat求解.xls 2015-10-8; 个人分类: 随笔|2056 次阅读|0 个评论

3-SAT分段子句消去法求唯一解例题: 热度 1 accsys 2015-10-6 08:49; 3-SAT 分段子句消去法求唯一解例题姜咏江利用子句块唯一解和动态块唯一解来处理 3-SAT 求解，最方便的是 3-CNF=1 有唯一解的情况。这也是用其他方法求解 3-SAT 问题最不易的事情。在用关联段子句消去的过程中，如果出现动态块消去呈现多解的情况，如果选择的变量值不合适，有可能出现后续无解的情况。正确的做法是暂不设值，而是沿着一元关联的子句块寻找唯一解的剩余子句块。只要找到关联的满足唯一解的子句块，就可以先设定这个子句块的变量值，然后反方向去确定前面多解的选值，这样可以最终正确地求出 3-SAT 的解。如果最终都是多解的子句块，那么这个3-SAT的问题肯定是多解了，此时确定最后一个子句块解，反向可得解。 3-SAT 有唯一解的情况，用分段子句消去法既方便又准确。有兴趣的朋友不妨试试。我还没有编写程序处理。不过手工操作弄个百八十个变量也不是难事。就是上千个变量也未必是难事，操作过程中随着子句的消去，工作量会迅速减少，时间自然会加速减少。本文给朋友一个唯一解的例子，希望有心人能够自己做做看，体会一下求解3-SAT问题的关键点在何处。表下面一行是实际消去子句后的结果。唯一解实例： 3-SAT分段子句消去法唯一解例题.xls 参考： http://blog.sciencenet.cn/blog-340399-925143.html 2015-10-6; 个人分类: 机器计算|2659 次阅读|2 个评论

3-SAT关联段子句消去法（详细解法）: 热度 1 accsys 2015-10-4 06:54; 3-SAT 关联段子句消去法姜咏江摘要：本文给出了 3-SAT 分段消去子句的求解算法。证明了可以在多项式时间求出 3-SAT 的解。从而证实斯提芬 . 库克定义下的 NP-complete 问题就是一个 P 类问题。。关键词： NP-complete ， P/NP 问题，子句消去法 1. 引言 P/NP 问题曾于 2000 年被美国克雷数学所定为最难的难题，有甚者说其挑战了人类智慧。所谓 P/NP 问题的定义是这样给出的：复杂度类 P 包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题；类 NP 由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，或者等效的说，那些解可以在非确定图灵机上在多项式时间内找出的问题的集合。实际上这个定义有很多歧义，涉及到人们对确定型图灵机、非确定型图灵机、多项式时间、问题、决定问题、肯定解、给定正确信息、验证等一系列概念的认识的不统一，很难形成统一的见解。人们能够统一的是 P 类问题属于 NP 类问题，但 NP 类问题是否就是 P 类问题，一直没有确定的结论。 1971 年斯提芬 . 库克 (Stephen A. Cook) 发表了〈 The Complexity of TheoremProving Procedures 〉才把 P 之外的问题归结为三大类，即 NP 、 NP-complete 及 NP-hard 。库克的分类得到了学术界的认可。在库克的定义下， P 、 NP 、 NPC 、 NPH 问题的定义如下： P 问题，可以在多项式时间内求出解的问题， Polynomialproblem 。 NP 问题，可以在多项式的时间里验证一个解的问题， Non-deterministicpolynomial 。 NPC 问题，如果所有的 NP 问题都存在多项式时间算法使其能够归约为某一 NP 问题，则称该 NP 问题为 NPC 问题， NP-complete 。 NPH 问题，如果所有的 NP 问题都存在多项式时间算法使其归约到某问题，则称该问题为 NPH 问题， NP-hard 。由以上 NPC 问题的定义，我们不难想到，只要我们能够找到一个 NPC 问题，并能够找到其多项式时间的求解算法，那么就可以肯定这个 NPC 问题就是一个 P 问题。因为所有的 NP 问题都可以通过多项式时间算法归约成 NPC 问题，并且所有的 NPC 之间都有多项式时间算法实现转化。因而只要找到一个 NPC 问题的多项式时间算法，也就等于找到了所有 NP 问题的多项式时间算法，于是也就证明了 NP=P 。 2. 典型的 NPC 问题长时间以来，人们将寻找 NPC 类问题的多项式时间算法作为了解决 P=NP 问题的关键途径。一些典型的 NP 类问题（见图 1 所示）早已经被一些数学家明是 NPC 问题。例如， 3 元合取范式满足问题 3-CNF-SAT （简称为 3-SAT ）、子集和问题 SUBSET-SUM 、旅行商问题 TSP 、哈密顿回路问题 HAM-CYCLE 等，这些都是 NPC 问题寻找多项式时间解法的研究热门问题。但时至今日，尚未见到任何 NPC 问题的多项式时间复杂度的算法出现。本论文给出的是求 3-CNF-SAT 满足解的多项式时间复杂度的算法，还包括一些相关的概念和定理证明。这种算法只要将 3 换成 k 就可以得到 k-CNF-SAT 的解法。图 1 典型 NPC 问题及相关 3. 子句消去的算法子句消去法源自最简单的逻辑运算关系，即多个逻辑多项式之间的与运算结果为 1 ，必须每一个多项式的值为 1 才行。 3-SAT 每个子句多项式有 3 个变量，只要其中一个变量表示是 1 ，那么就可以将含有该变量表示的所有子句多项式消去，从而可以找到整个与运算表达式可能为 1 的那些解。一个个单独设置变量值，子句消去法不是一个多项式时间算法，但本文给出的分段子句消去法却有了惊人之处。 3.1 3-SAT 的定义所谓的 3-SAT 就是多个由 3 个逻辑变量或其非组成的多项式间形成与运算表达式。一般这种逻辑表达式被称为合取范式 3-CNF 。我们这里将逻辑或运算符用“ + ”表示，逻辑非运算符用“ ’ ”表示，而将逻辑与运算符省略。将逻辑变量或其非表示组成的多项式叫“子句”。例如， (x1’+x2’+x3’) (x1+x2’+x3’)(x1’+x2’+x4) (x3+x4’+x5)(x2’+x2+x3’) 是一个 3-CNF 合取范式，我们要求出满足 3-CNF=1 的那些解，这个问题习惯上人们称之为 3-SAT 。表达式中每个括号之间是与运算的关系，每个括号内的多项式就是子句。如果一个子句中包含一个变量和其非的项，那么显然该子句的值永远是 1 。我们称这样的子句是恒一子句。因为 3 元合取范式 3-CNF=1 中象 (x2’+x2+x3’) 这种恒一子句不影响求解，所以本文的 3-CNF=1 问题中不包括恒一子句，并用 3-SAT 替代它。 3.2 子句消去法与规定所谓的子句消去法，就是逐一设定变量的值，并将所有在变量值设定下值为 1 的子句消去，最终看是否剩余子句的算法。例如，合取范式 F=(x1’+x2’+x3’) (x1+x2’+x3’)(x1’+x2’+x4) (x3+x4’+x5) 我们令 x1=0,x2=0,x3=1 就可以将等式右面的全部子句消去（此处变量 x4 与 x5 的值可以任意设置），那么就可以得到 F=1 的一组 4 个解： 00100 、 00110 、 00101 、 00111 。为了方便又不失一般性，我们给出子句变量的概念和去除未参与构成子句变量的规定。定义 1 ：不论是逻辑变量 x 还是其非 x ’在一个子句中，我们都称 x 是这个子句的变量，叫子句变量。规定，我们研究的 3-SAT 既不不含无关的变量，也不包括恒一子句。 4. 3-SAT 格式表与反子句采用子句消去法要建立 3-SAT 表格式（见图 2 ），将子句以 3 位二进制数的形式写入表中。我们用 0 表示逻辑变量的非运算形式，用 1 表示逻辑变量本身，并称此种表示子句的二进制数为子句值。例如，用 000 表示子句 x i ’+ x j ’+ x k ’ ，而子句 x i + x j ’+ x k ’ 则用 100 表示。子句左面的变量叫开始变量，右面的变量叫结束变量。 4.1 合取范式的表格式 3-SAT 的规范表格式如图 2 所示。规定每个子句占用一行，并且要求变量相同的子句行相邻。图 1 合取范式值格式定义2 ：变量相同的子句放到一起叫子句块。图 2 中 3-SAT 表中颜色相同的部分就是一个子句块。当然，单独的子句也自成一块。按照从编号 1 顺序划分有 3 个相邻变量的子句块叫标准块。其它 3 个变量组成的块叫非标准块。非标准块中不相邻变量组成的块叫分散块。变量取值与其它子句块变量无关的块，叫独立块。两子句块开始变量相同，叫同根；结束变量相同叫同尾；子句块的开始变量到结束变量之间有其它子句块，这叫跨越。定义3 ：能够使子句块的子句全部消去的块中变量值叫块解。 3-SAT 一个子句块中子句值最多有 8 个，而块解最多只有 7 个。这一点下面会解释。为了清晰起见， 3-SAT 表将选择确定的变量值放到表下面的对应位置。 4.2 反子句与关联段两个数码之和为最大数码，一个就叫另一个的反码。二进制中数码 0 和 1 是互为反码。将一个数的数码都用其反码表示，叫原数的反码数，也简称反码。定义 4 ：子句块中子句值为反码的子句，一个叫另一个的反子句。 3-SAT 子句块的反子句最多有 4 对，用值表示分别是｛ 000,111 ｝｛ 100,011 ｝｛ 010, 101 ｝｛ 110,001 ｝。子句消去法求 3-SAT 满足解的算法，要用到关联段的概念。定义 5 ：有相同变量的子句块称为关联块，通过关联块形成的子句块集合叫关联段。能使关联段中所有子句值为 1 的段中变量值，称为段解。 3-SAT 有一元关联、二元关联。定义 6 ：子句块间有一个共同变量的子句块叫一元关联。子句块间有 2 个共同变量的子句块叫二元关联。 3-SAT 独立块间无变量关联。定义 6 ：在进行子句消去过程中由选择变量确定的子句形成的块叫动态块。能够使动态块子句消去的变量值叫动态块解。 5. 相关定理与性质为了说明子句消去法对 k ≥ 3 合取范式 k-CNF-SAT 求解的有效性，我们以更一般的情况来论述本节内容。子句消去法能够一次性求出 k-CNF-SAT 满足解基于如下的一些基本定理。定理1 ：子句块中若有互反子句存在，则互反子句值都不是块解。证明：依据子句消去法，以子句值消去的所有子句中不包括其反子句，因此总有一个子句值不能被消去。推论1 ： k-CNF-SAT 子句块解不超过 2 k -1 个。推论2 ： k-CNF-SAT 子句块中已有子句的反子句值不是块解。推论3 ：若 k-CNF-SAT 中有 2 k 个子句的子句块存在，则 k-CNF-SAT 无满足解。定理2 ：从一个子句块出发确定的解，也可以从另一子句块出发确定这个解。证明：假设由子句块 A 确定的解 a 不是由子句块 B 确定的解，那么因 a 中必含有 B 的一个子句值，于是可以从这个值出发，按照 a 的值扩充来求解，仍然是这个合取范式的一个解。于是可知，可以从 A 起始块或 B 做起始块得到相同的解。由此定理可知，选择任何子句块做为起始块求解，效果一样。推论4 ：从任意子句块出发都可能确定出合取范式的解。定理3 ：关联段无解，则 k-CNF-SAT 无满足解。证明：因为关联段解是 k-CNF-SAT 解的部分，其无解， k-CNF-SAT 自然无解。定理4 ： 3-SAT 有解的子句块确定了一个变量值，如剩下 4 个不同的值，则无段解。证明：由表1 可见，只要选值的两个变量值出现右侧的 4 个值，那么无论如何设值，都不能将其余子句消去。表 1 子句变量值表块子句可能值固定一个变量其它变量可取值 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 0 1 0 1 1 1 1 1 关联段性质：各关联段解相互独立。即一个关联段解改变，不影响其它段解。因为关联段解不独立，则说明这是一个关联段。推论5 ：动态块确定一个变量值后二剩余变量有 3 组值，则有惟一动态块解；两组或一组值，则有多个动态块解。定理5 ：连续多值可选的关联段最终可确定段解。证明： 3-CNF 求解中只有一个变量值确定的动态块可以产生多解。若设定关联变量值后的剩余动态块仍然有多值可设，则可连续查找关联动态块，直至无解、有惟一解或有关联段的结束动态块出现。如果最终出现动态块无解，则关联段无解。如果出现动态块有唯一解，可反方向设定关联变量值去确定前面每个多值动态块的解；如果多解情况最终关联的是未曾设定解的子句块，可以把子句块解设定，然后反方向去确定多解的动态子句块，最终会连成一个关联段，得到关联段的解或无解。 6. 3-SAT 分段求解方法 3-SAT 的子句块有解，并且关联段有解，那么 3-CNF=1 才会有解。依据这一原理，我们先检查子句块是否都有解。如果子句块都有解，那么选择 3-SAT 的关联段，求出各关联段解，进而能够组合求出 3-SAT 的满足解。 6.1 关联段子句消去法表格式 3-CNF=1 求解算法如下：（ 1 ）选择左侧子句块为起始块；判断有块解后选择一个块解，无块解 3-CNF=1 无解。（ 2 ）消去至少含有一个与这个块变量相同且值相同的所有子句。（ 3 ）向右寻找靠近的 2 个变量值已确定的动态块，设定最后一个变量值，将含有该变量且值相同的子句块消去；若设定 0 或 1 都不能够消去动态块全部子句，则知从起始块设定值开始得不到 3-CNF=1 的解，需要选择下一个起始块解进行从新操作；若起始块解都操作过并无解，则 3-CNF=1 无解。（ 4 ）若是只有 1 个变量值已确定的动态块，则需要同时确定 2 个变量的值。此时应依据定理 4 先判断有无解；无解，则需重复下一个起始块解。（ 5 ）通过（ 4 ）判定有解，并依靠推论 4 判断出有唯一解，则设定 2 个变量值，并消去所有相关子句。（ 6 ）如果通过（ 5 ）得出设定 2 个变量值多解的情况，依据定理 5 向后去确定关联段的解。（ 7 ）如果（ 6 ）的操作的关联段一端遇到无后续关联的子句块，并且关联段无跨越子句块，则该关联段结束，可以进入下一个关联段求解操作；如有跨越关联子句，需通过跨越子句向左右两个方向求段解。（ 8 ）依据子句消去法，若所有的关联段都有解，那么 3-CNF=1 就有解。其解为各关联段解的顺序组合。由于 3-CNF 一个关联段最多有 7 个段解，所以 3-CNF=1 通过分段求解，如果每个关联段都有解，则可以配合出 3-CNF=1 的多组解。 6.2 子句消去法实例我们以图 2 的例子来说明子句消去法。（ 0 ）判断子句块中是否有子句数为 8 的，是， 3-SAT 无解。（ 1 ）最左面的 x1x2x3 子句块为起始块，此块只有 000 、 100 和 010 三个块解。选择 x1x2x3=010 ，消去有 x1=0 、 x2=1 、 x3=0 的所有子句（绿色部分是消去的子句）。图 2 逐步消去子句块求解过程（ 1 ）（ 2 ）向右，以子句块尾最靠左为原则，寻找剩余子句块。此例为块尾是 x5 的子句块。由于该块有 x3=0 ，只有 x4x5 关联的动态块出现｛ 00 、 10 、 11 ｝，有唯一动态块解 010 ，于是选 x4x5=10 消去相关子句。剩下以 x6 关联的动态块只需要设定 x6=0 就可以将该动态块消去，选择 x6=0 ，并消去相关子句（见图 3 ）。图 3 逐步消去子句块求解过程（ 2 ）（ 3 ）剩余没有 x7 结尾的动态块，只二变量确定块尾为 x8 的动态块，设 x8=0 ，消去 x8=0 相关子句后，遇到了需要设置 x7x13= ｛ 10 、 01 ｝多解的动态块解（见图 4 青色块）。图 4 逐步消去子句块求解过程（ 3 ）（ 4 ）在关联段中遇到动态块多值，为了避免选择关联段无解的分支，我们采用向下寻找唯一解的方法来保证关联块有解。此时暂不设置变量值，而是通过与其一元相关子句块连续寻找有唯一解的子句块。向上关联有 x5x13x18 子句块，向下有 x6x13x21 子句块和 x13x14x16 子句块。它们后续关联的都是需要三个变量设值的子句块。可以假定这些子句块是新的一个关联段，照顾到与前面关联关系，可设定子句块解，往回消去前面没有定解的动态块（见图 5 青色所示）。图 5 逐步消去子句块求解过程（ 4 ）（ 5 ）由于 x13x14x16 子句块是无后续关联的，可以设定 x13x14x16=001 消去相关子句（见图 6 ）。图 6 逐步消去子句块求解过程（ 5 ）（ 6 ）动态子句块 x7x8x13 已有 2 个变量值被确定，必需设 x7=1 将其消去。然后将 x11x12x14 和 x9x10x11 的子句块消去（见图 7 ）图 7 逐步消去子句块求解过程（ 6 ）（ 7 ）此时， x8x13x18 动态块必需设 x18=0 。接续消去 x18x19x20 的子句块及关联子句块（图8 ）。图 8 逐步消去子句块求解过程（7）如图8 所示，至此就得到了这个 3-CNF=1 的一组解。由图8 我们看到通过以上消去子句操作，已经没有了剩余子句。从表下面一行就得到了这个 3-SAT 的满足解。解的变量空白处，实际上是值为 0 和 1 两种情况，这表明实际上所求出的解是一组，解的数量应是 2 的空格数指数倍。本例求得的合取范式一组解包括 2 3 个解。此例全部子句在一个关联段中，如果 3-SAT 含有多个独立的关联段，那么将段解组合在一起就是求得的 3-SAT 满足解。如果想要求出 3-SAT 更多的解，必需将起始块解都考虑到，这样才能达到目的。此例题其它两个起始块解都不能够形成段解，因而通过它们不可能有 3-SAT 的解。 6.3 关联段解处理讨论 3-SAT 的满足解是由 n 个变量值组成的，其中任何一部分变量值不构成解的变量值， 3-SAT 就无解。这种局部特征是破解 3-SAT 难题的关键。依据定理 4 ，只要 3-SAT 子句块都有解，那么一元关联段总可以判断出是否有解。二元关联段是否有解很容易判断。判断一元确定的动态块有几个解，要看其余子句变量的状况。如果要确定的变量值为｛ 00 、 01 、 10 ｝｛ 11 、 01 、 10 ｝｛ 11 、 01 、 00 ｝｛ 11 、 00 、 10 ｝之一，则有一个解；为｛ 00 、 01 、 10 、 11 ｝无解；而为｛ 00 ｝｛ 11 ｝｛ 10 ｝｛ 01 ｝｛ 10 、 01 ｝｛ 00 、 11 ｝之一，则有多个解。这种多解可以在一个变量值被确定的情况下，仍然可能选择另一个变量值将剩余子句块消去。如果动态块有多个解，为了后续动态块不出现无解，可以依据动态块多解向后查找定解，然后反向确定动态块多解，不需要将所有的可能解都计算一遍，只要能够得到关联段解就达到了求 3-SAT 解的目的。要求出更多解，需要将每个关联段的段解都求出来进行组合。下面例子是对一个关联段求解的过程。图 8 的起始段只有 000 、 100 和 010 这 3 个块解，求解只要从这 3 个值出发就可以。图 8 （ 1 ）出现二元判断无解的情况。图 8 （ 2 ）出现一元判断无解的情况。图 8 （ 3 ）才是有段解的情况。图 9 有段解的判断关联段结束在两个相互独立的子句块之间。由于没有恒一子句的 3-SAT 子句数量不超过 2 3 C n 3 个，并且相关子句越多， 3-SAT 的解越少。因而子句数量越接近 2 3 C n 3 个，那么分段子句消去法的效率越高。每一个关联段就是一个 3-SAT ，因而 3-SAT 并不完全是一个全局性的问题。 7. 3-SAT 分段子句消去法时间复杂度 3-CNF=1 的解是由 n 个变量值组成的，如果其中任何一部分变量值不构成解的变量值，那么 3-CNF=1 就无解。分段子句消去法，将 3-CNF 的子句分成了相互关联的段，并以段解来组成 3-CNF=1 的解。由于关联段是不重复的，所以 3-CNF 的关联段最多有个，此时最多有一至两个子句块之间关联，其余子句块都是独立的。由于 3-CNF 的每个关联段不会超过 7 次求段解操作得出段解，因而用分段子句消去法求出 3-CNF=1 的解或判定无解，最多需要进行 7 次消去子句的过程。从这一点来说，用分段子句消去法求 3-CNF=1 的解是一个 O( n ) 时间复杂度的算法。其实， 3-CNF=1 是否有解，主要取决于子句数 m 和子句分配的结构，亦即子句之间关联的程度。 3-CNF 关联段子句越多， 3-CNF=1 的解就越少，反之解的数量会很多。当所有子句块只有一个子句并且都是独立块时， 3-CNF=1 会有最多的解。 8. 结论 3-SAT 求满足解的分段子句消去法是一个多项式时间复杂度的算法。本算法证明了典型的 NP-complete 问题之一 3-SAT 是一个 P 类问题。依据学术界公认的观点，分段子句消去法可以说明 P=NP 。联系邮箱： accsys@126.com Accsysuibe@uibe.edu.cn 2015-09-19 备注：从 C n 3 个子句块中选块解，如同做除法试商。修改于 2015-10-04; 个人分类: 科研论文|5514 次阅读|2 个评论

象做多位数除法一样求出3-SAT的解: 热度 1 accsys 2015-9-22 07:18; 象做多位数除法一样求出 3-SAT 的解姜咏江 3-SAT 是破解千禧大奖P/NP的典型 NP-complete 问题。据说 NP-complete 问题一直没有多项式时间复杂度的算法，因而回答不了P/NP问题，所以美国克雷数学所才于 2000 年悬赏百万美元，广征P/NP问题破解。不才，知道其中的难度，但出于兴趣，开动脑筋，经历波折数次，终于设计出了 3-SAT 分段子句消去法，使 3-SAT 的求解过程，如同做多位整数除法的算数题，可以用来解决一些问题。君，如有兴趣，可参阅 http://blog.sciencenet.cn/blog-340399-928224.html 还是那句话：“把简单问题说复杂了，那叫蒙人。把复杂问题说简单了，那叫本事。” 科研快乐！ 2015-9-22; 个人分类: 随笔|2082 次阅读|1 个评论

分段子句消去法求解3-SAT的练习: accsys 2015-9-22 04:54; 分段子句消去法求解 3-SAT 的练习姜咏江这里给出用 excel 的表练习求解 3-SAT 的例子。有兴趣的读者可以自己练习一下。为了全面观查，消去的子句块用颜色覆盖就可以。遵循每行一个子句，变量相同的子句写到一起，形成子句块的形式，可以添加子句，当然也可以自己设计3-SAT。记住，子句块要有解，先选二元关联段消去。解法请看 http://blog.sciencenet.cn/blog-340399-922267.html 3sat.xls 2015-9-22; 个人分类: 科研讨论|2182 次阅读|0 个评论

3-SAT分段子句消去算法，数学人都能看懂NPC=P的证明: 热度 1 accsys 2015-9-21 06:30; 3-SAT 分段多项式时间求解算法姜咏江摘要：本文给出了 3-SAT 分段消去子句的求解算法。证明了可以在多项式时间求出 3-SAT 的解。从而证实斯提芬 . 库克定义下的 NP-complete 问题就是一个 P 类问题。关键词： NP-complete ， P/NP 问题，子句消去法转： http://blog.sciencenet.cn/blog-340399-928224.html 2015－10－04; 个人分类: 科研论文|5297 次阅读|2 个评论

3-SAT分段多项式时间求解算法: 热度 1 accsys 2015-9-19 04:57; 3-SAT 分段多项式时间求解算法姜咏江摘要：本文给出了 3-SAT 分段消去子句的求解算法。证明了可以在多项式时间求出 3-SAT 的解。从而证实斯提芬 . 库克定义下的 NP-complete 问题就是一个 P 类问题。关键词： NP-complete ， P/NP 问题，子句消去法转： http://blog.sciencenet.cn/blog-340399-928224.html 联系邮箱： accsys@126.com （为防止网络被窃，在此公开并存档） 2015-09-19; 个人分类: 科研论文|2906 次阅读|2 个评论

更多...

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

关闭 安全验证

标签: 分段子句消去法

相关帖子

相关日志

关闭安全验证