Tree Search vs Local Search
TreeSearchmethods:systematicallysearchthespaceof
assignments.
Start with an empty assignment.
Assign a value to an unassigned variable and deal with constraints on
the way until a solution is found.
Butwhatifthespaceistoobigandeveninfinite,soinany reasonable time, systematic search may fail to consider enough of the space to give any meaningful results.
LocalSearchmethods:notsystematicallysearchthespacebut
design to find solutions quickly on average
Start with an (arbitrary) complete assignment, so constraints can be
violated.
Try to improve the assignment iteratively.
Local Search for CSPs
Example:TherearethreevariablesA,B,C,allwithdomain {0, 1, 2}. The constraints: .
B=0
C=1
B=0
C=1
A=1
A=0
Atypicallocalsearchalgorithm(i.e.hillclimbingforCSPs):
Randomly generate a complete assignment
While stop criterion not met
Step 1: Variable selection ‐ randomly select a constraint‐violated variable.
Step 2: Value selection (min‐conflict heuristic) – choose a value that violates the fewest constraints.
Example: N‐Queens
Problem: N‐queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other.
Q1 Q1 2 0 2 Q1
Q2 Q2 Q2 Q2 Q3 2 1 0 Q3 Q3
Q4 Q4 Q4 0 3 1
Q1
Formulation – Variables: Q1, Q2, Q3, Q4; Domains: {1,2,3,4}; Constraints: ∀ i, j, not‐threatening(Qi and Qj).
Randomly generate a complete assignment;
Assume we first consider Q3, then Q3 going to column 4 has fewest constraints
violated;
Assume then we consider Q1, then Q1 going to column 3 has fewest constraints
violated;
Assume next we consider Q4, then Q4 going to column 2 has fewest constraints
violated;
Stop execution and return the solution.
Q3 Q4
Can Local Search always guarantee finding a solution
Localsearchmaygetstuckinsomewherebasedonthe problem’s landscape and search strategy
Q1 1 1 1 3 Q1 1 1 3 1 1 Q1 Q2 Q2 Q2
Q3 Q3 Q3
Q4 Q4 Q4
……
Butitiseffectiveinpractice:cansolvethemillion‐queens problem in an average of 50 steps!
Strategy like “fixing the queen on the top before fixing the others” can lead to a never‐ending search
Summary: CSPs
CSPsareaspecialclassofsearchproblems States are partial assignment
Goal test defined by constraints Basicstrategy:Backtracking
Speed‐ups
Filtering: forward checking
Ordering
Localsearch:notsystematicallysearchthespace,startwitha (bad) complete assignment and improve it iteratively
Not only apply to CSPs, but to various optimisation problems
Optimisation
Optimisation problem: search problem with preferences, i.e. objective function(s).
They consist of variables, domains, objective function(s) Objectives:
Single‐objective optimisation problems, e.g., Travelling Salesman Problem (TSP): minimising the cost of the travelling.
Multi‐objective optimisation problems, e.g., TSP with an additional objective: minimising the time of the travelling.
Constraints:
Unconstrained optimisation problems
Constrained optimisation problems
Tree search methods may not work for optimisation problems, e.g. in some continuous search space.
Local search methods can be effective for optimisation problems.
Hill climbing, e.g. gradient descent
Simulated annealing
Tabu search (keep a small list of recently visited solutions and forbid the algorithm
to return to those solutions) …
Local Search for Optimisation
Generallyfastandmemoryefficient.
Candealwithproblemswherethesearchstateisdifficultto
represent/formulate.
Canbeusedinanonlinesettingwhentheproblemchanges, e.g., in airline scheduling problem.
But what if the problem has very complex landscape
We may need population‐based search algorithms!