CMP设计分享 http://blog.sciencenet.cn/u/accsys 没有逆向思维就没有科技原创。 不自信是科技创新的大敌。

博文

Algorithm ZJXQF for SAT Problem

已有 2905 次阅读 2017-5-16 08:07 |个人分类:3SAT解法|系统分类:科研笔记| SAT, polynomial, ZJXQF

Algorithm ZJXQF for SAT Problem

                                                                                          Author:JIANG Yong-jiang  

Input : A “0” and “1” table of clauses Q.

Output: A Truth Value.


Function ZJXQF(Q)

(1).  If a variable has 2k-1 “0” and “1” in a k-block (k=1,2,3,…, j, j is a constant number)

             Thenreturn “false”;

(2).  If a variable has unique solution in a clause block

             Then delete the variable and the relative clauses in Q,call (1);

(3).  If a variable has unique solution in a relative section

             Then delete the variable and relative clauses in Q,call (2);

(4). Final, set 0 (or 1) to a selected variable in the  possible solutions table and delete the line  by relative clauses;

(5).   By relative value and extend the solution, can get the result.




This polynomial algorithm is a completed for solve any SAT problem. I have the program for test. If you want get it, I will give you the program and the Eliminate-Clause method paper.



                                                                     MyEmail: accsysuibe@uibe.edu.cn


2017/5/16




https://wap.sciencenet.cn/blog-340399-1055187.html

上一篇:活到老、学到老、研究到老
下一篇:你有SAT问题?我来帮你解答
收藏 IP: 116.117.135.*| 热度|

1 haipengzhangdr

该博文允许注册用户评论 请点击登录 评论 (1 个评论)

数据加载中...
扫一扫,分享此博文

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

GMT+8, 2024-3-29 13:03

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部