大家来讨论一下这样一个简单的局部搜索算法

只看该作者 · 2015-10-14 21:39

本帖最后由可木于 2015-10-22 21:09 编辑

大家来讨论一下这样一个简单的局部搜索算法，在FPGA中实现如何在最短的时间内获得解？

WSAT(F,MAX-TRIES , MAX-FLIPS)
{
for (i = 0; i < MAX-TRIES; i++) {
      T = randomly generated truth assignment;
      for (j = 0; j < MAX-FLIPS; j++) {
         if T satisﬁes F return T;
         c = an unsatisﬁed clause selected at random;
         v = a variable in c chosen by the Heuristic(c);
         T = T with v ﬂipped;
         }
}
}
简单说明一下F为CNF公式，如F(x1,x2,x3)=C1 | C2 | C3 | C4=(¬x1 & x2) | (¬x2 &¬x3) | (x1 &¬x2 & x3) | (x1 &¬x3)，MAX-TRIES为给公式赋初值的次数，MAX-FLIPS为赋值T不满足F的情况下，翻转变量最大次数。以上算法过程是这样的：1.给定F和一组随机初值，如{x1,x2,x3}={1,1,1}，可知C2=0，因此F=0.
2.选择C2,随机或利用启发式选择某一变量进行取反，假设选择X2，即{x1,x2,x3}={1,0,1}，可知C2=1，但是C1=0，以此F=0,继续翻转变量。
3选择C1,随机或利用启发式选择某一变量进行取反，假设选择X1，即{x1,x2,x3}={0,0,1}，可知C1=1，但是C4=0，以此F=0,继续翻转变量。
当尝试MAX-FLIPS次后任然没有找到一组赋值使F=1，则跳出此循环，重新赋一组初值继续上面循环，直到找到F=1的一组赋值。
不知道我是否表达清楚，有兴趣的兄弟可以一起探讨一下。F中可以有N个子句C，每个C最多包含三个X。