Search by Constraints (CSP ) and Local Algorithms:
Constraint search and local algorithms are two important approaches in artificial intelligence and optimization to solve complex problems, often with large amounts of constraints or a huge research space.
1. Search by Constraints :
In constraint reasoning, a model is constructed using
• Variables
• Variable domains
• Constraints between variables
A solution to a CSP is:
Assign each variable a value in its domain to satisfy all the constraints.
1.2 A constraint solver allows:
- Find a solution at CSP,
- Or prove that there is no solution.
Constraint-solving techniques are widely used in problems such as planning, scheduling, puzzles, or resource management.
The main components are:
· Variables: Part of the problem with possible values.
· Domains: Set of possible values for each variable.
· Constraints: Relationships between variables, specifying the combinations of values allowed.
1.3 Modeling :
Variables, domaines, contraintes è Modeling
What is a model?
• A model is an abstarction of a problem
• A model must respect the language of the solver
· Example:
The following Constraint Satisfaction Problem (CSP) : Coloring nodes of a graph.
What is the minimum number of color such as two knots adjacent receive different colors?
Step 1:
Give each node a name: A, B, C, D, E, F. It represents the colors to assign to the nodes
For example ‘A = Red’. They represent the variables.
Step 2:
Initially all nodes can be {red, blue, green, yellow, blueciel, purple} They represent the domains of variables.
Step 3:
Declare that two adjacent nodes cannot take the same color. They represent the constraints.
Step 4:
Minimize the number of colors
• It represents the objective function
How to color the graph?
• There are 6 knots, so a maximum of 6 colours:
Complete model:
Variables: A, B, C, D, E, F
Areas(domains): {red, blue, green, yellow, blue eciel, purple}
Constraints:
Solution:
Assign a color for each variable to satisfy all the constraints:
