一个简单的局部搜索算法，在FPGA中实现如何在最短的时间内获得解？

shelby

3 t# C% K* a0 w2 N+ t: a; Q1 x一个简单的局部搜索算法，在FPGA中实现如何在最短的时间内获得解？
7 Z$ K& `) G& k: |  O( i/ @1 u; R
WSAT(F,MAX-TRIES , MAX-FLIPS)
% [# P& u: k& J+ I/ R5 h0 f{
   for (i = 0; i < MAX-TRIES; i++) {
! b$ n0 p1 q; U4 O# y1 A$ Y/ z         T = randomly generated truth assignment;
         for (j = 0; j < MAX-FLIPS; j++) {
. X& p, a& F) w/ X& N1 Q0 V             if T satisfies F return T;
            c = an unsatisfied clause selected at random;
0 t/ T* E0 A) {% Z            v = a variable in c chosen by the Heuristic(c);
            T = T with v flipped;
. J3 s+ E9 s; f* g0 X           }
    }
1 w6 J3 m& \* u, ]: s' J}
简单说明一下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.
& T  n" M' H2 z' A/ ?6 }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,继续翻转变量。
0 h% s% V% d) X/ r+ k6 J/ O5 ~% }' o当尝试MAX-FLIPS次后任然没有找到一组赋值使F=1，则跳出此循环，重新赋一组初值继续上面循环，直到找到F=1的一组赋值。
不知道我是否表达清楚，有兴趣的朋友可以一起探讨一下。F中可以有N个子句C，每个C最多包含三个X。

Demyar

这是用来干什么的，有C语音代码不，变量是整数还是布尔型。

Colbie

理论性太强了，另外很少有人搞你这个专业，我也帮不了你。