微波EDA网,见证研发工程师的成长!
首页 > 研发问答 > 嵌入式设计讨论 > FPGA,CPLD和ASIC > 大家来讨论一下这样一个简单的局部搜索算法

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

时间:10-02 整理:3721RD 点击:
大家来讨论一下这样一个简单的局部搜索算法,在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。

没人有兴趣么?

Copyright © 2017-2020 微波EDA网 版权所有

网站地图

Top