Local Search

search

Definition

Local Search

Neighbourhood

Given a state $x$, the neighbourhood $N(x)$ is the set of all subsequent states that can be reached from state $x$.

Step Function

The step function defines the transition behaviour from one state $x$ to another state $x^{\prime }\in N(x)$.

Best Improvement

Traverse $N(x)$ completely and choose the best neighbour solution.

First Improvement

Traverse $N(x)$ in a certain order and choose the first solution that is better than $x$.

Random Neighbourhood

Choose a random solution from $N(x)$.

Examples

Local Search: SAT

Given: a Boolean function in CNF with variables $x_1,\dots ,x_n$, e.g.:

$$(\neg x_1\vee x_2\vee x_3)\wedge (x_1\vee \neg x_2\vee x_3)\wedge (\neg x_1\vee \neg x_2\vee \neg x_3)$$

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

Optimisation variant: Max