Walksat Procedure

Start with random initial assignment.

Pick a random unsatisfied clause.

Select and flip a variable from that clause:

With probability p, pick a random variable.

With probability 1-p, pick greedily
a variable that minimizes the number of unsatisfied clauses

Repeat to predefined maximum number flips; if no solution found, restart.

Previous slide

Next slide

Back to first slide

View graphic version