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

博文

用C++编写的子句消去法要比VFP快得多

已有 3332 次阅读 2017-8-10 12:44 |个人分类:3SAT解法|系统分类:科研笔记| VFP, 子句消去法

C++编写的子句消去法要比VFP快得多

姜咏江

本人最近为解决巨量3-SAT问题,用C++编写了子句消去法程序。与以前用VFP所写程序执行比较,C++程序要快多了。一个实际逻辑电路转换的合取范式求满足解,VFP程序执行用时2秒,而用C++程序执行时间不到一秒。下图是对比。C++用负数表示“假”,用正数表示“真”。

求解3-SAT问题的子句消去法能够在O(n4)时间复杂度完备求出满足解。

图中黑色部分是c++程序运行结果,最低与最高位是辅助位,不是变量的解。




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

上一篇:关于物质宇宙的闲聊回复
下一篇:国外著名学术期刊害怕什么?
收藏 IP: 36.102.227.*| 热度|

0

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

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

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

GMT+8, 2024-11-9 15:09

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部