用python或java实现
3 .实验要求
设计算法求解 SAT 问题
设定问题规模为 3 5 10 20 50 设计实验程序考察算法的时间性能。
实现提示
假设 SAT 问题的规模为 n 则任一个长度为 n 的二进制串都是该问题的可能解。考虑最简
单的方 法 将每一个长度为 n 的二进制串依次代入某个给定的合取范式中 直到该合取范式取
值为 TRUE 得到此问题的解 或将所有长度为 n 的二进制串依次检测后该合取范式的取值始终
为 FALSE 则此问题无解
【算法 2】SAT 问题
1.将一个长度为 n 的二进制串 s 初始化为 00⋯0 ;
2.循环直到串 s 为 11⋯1
2.1 将二进制串 s 代入给定的合取范式中;
2.2 若合取范式取值为 TRUE ,则将串 s 作为结果输出,算法结束;
2.3 否则,将串 s 加 1;
3.输出 “无解”