[讨论]

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

2015-10-14 21:58:55 1901

0 大家来讨论一下这样一个简单的局部搜索算法，在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。 0
2015-10-14 21:58:55　　评论淘帖0 举报相关推荐 • 考研还是就业？大家来讨论一下！ 2552 • 讨论一下平台与各种“流”的关系 3347 • 重点讨论一下硬件CBB 3562 • 讨论一下Linux的各种躺平姿势 1311 • 讨论一下封装的发展简史 2426 • 大家来讨论一下用蚁群算法实现路径规划的硬件实现问题 6443 • 图染色局部搜索算法python 1 • 求解#SMT问题的局部搜索算法 0 • 讨论一下在CCM模式下几种开关电源设计思路 2706 • 大家讨论一下这种电路 8119 1 个讨论