|||
用C++编写的子句消去法要比VFP快得多
姜咏江
本人最近为解决巨量3-SAT问题,用C++编写了子句消去法程序。与以前用VFP所写程序执行比较,C++程序要快多了。一个实际逻辑电路转换的合取范式求满足解,VFP程序执行用时2秒,而用C++程序执行时间不到一秒。下图是对比。C++用负数表示“假”,用正数表示“真”。
求解3-SAT问题的子句消去法能够在O(n4)时间复杂度完备求出满足解。
图中黑色部分是c++程序运行结果,最低与最高位是辅助位,不是变量的解。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-11-9 15:09
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社