Problem formulation of Constraint Satisfaction Problem

(21th-March-2021)

• Constraint is a declarative description of constituent elements to be applied and relationships established between the attributes.

• Formal description of the problem

1. • Set of variables: V = {v 1,...,Vn}, each vi is a mutually independent variable.

2. • A set of discrete values: D = {d1,...,Dn}, and each variable vi is assigned a value di which is an element of D.

3. • Set of constraints: C = {c1,...,Cl} Goal: a set of assignments of variable values that satisfy all the constraints given

Examples of constraint satisfaction problems

• Three-color classification problem Sudoku cross word puzzle packing of luggage problem People's schedule management problem When incorporating various parts into computers, mobile phones, home appliances, etc., problems such as how to make the parts smaller

Solving the constraint satisfaction problem

• (1) Full solution search method ... All the possibilities are searched for all the search space, so the integrity of the algorithm is guaranteed.

• (A) Solving method using matching method ... In the matching method, simplify domain and constraints of problems to be solved and convert them into simpler problems. However, the converted problem has the same solution set as the original problem.

• (B) Solving method using search method... It is a backtrack-based solution, there are checks to trim the search branch and prefetch of value assignment.

• (2) Local search method ... Instead of guaranteeing the completeness of the algorithm, an approximate solution for solving the solution at high speed

• (a) Repetitive hill climbing method ... When the evaluation value does not decrease with a certain search, the state is optimized locally Try another search again as a solution.

• (B) Probabilistic hill climbing method: A method of avoiding local optimal solutions by stochastically transitioning states.

• (C) Solving method using neural network

• (d) Solution method using genetic algorithm Note) Completeness ... It is always to be found if a solution exists in the search space, and it guarantees it if there is no solution.