Biased Random Walk

1) With probability p, “walk”, i.e., flip variable in some unsatisfied clause.

2) With probability 1-p, “greedy move”, i.e., flip variable that yields greatest number of satisfied clauses.

Previous slide

Next slide

Back to first slide

View graphic version