A typical local search algorithm (i.e. hill climbing for CSPs):
- Randomly generate a complete assignment
- When a solution not found or stop criterion not met, iteratively perform the following two steps; otherwise return the assignment.
- Step 1 : Step 1: Explore all the neighbours of the assignment (i.e., try every assignment that only has one variable difference from the considered assignment).
- Step 2 : Choose the assignment that violates the fewest constraints.
Example
There are three variables A, B and C, all with domain {1, 2}. The constraints:
Let us say the randomly generated initial assignment is (A=1, B=1, C=1). When a solution not found or stop criterion not met, do:
-
Step 1: Explore all the neighbours of the assignment: (A=2, B=1, C=1), (A=1, B=2, C=1), (A=1, B=1, C=2).
-
Step 2: Choose the assignment (A=1, B=1, C=2) that violates the fewest constraints.
Can Local Search always guarantee finding a solution ?
-
Local search may get stuck in somewhere, depending on the problem’s landscape and search strategy.
-
But it is effective in practice: can solve the million queens problem in an average of 50 steps!