Local Search

Definition

Local Search

Given a state , the neighbourhood is the set of all subsequent states that can be reached from state .

The step function defines the transition behaviour from one state to another state .

Traverse completely and choose the best neighbour solution.

Traverse in a certain order and choose the first solution that is better than .

Choose a random solution from .

Given: a Boolean function in CNF with variables , e.g.:

Find: a variable assignment, such that all clauses are satisfied.

Optimisation variant: Max