Constraint Satisfaction Flashcards
(32 cards)
What is a Constraint Satisfaction Problem (CSP)?
A CSP is defined as:
* a set of m distinct variables: X = {x1, x2, …, xm}
* a set of m domains associated with each variable: D = {D1, …, Dm}
* a set of constraints imposed on the variables: C = {C | Cj(X1, X2, …, Xn)}
CSPs are used to model complex problems in various fields, making them closer to natural problem statements.
What are the main characteristics of industrial problems in constraint satisfaction?
Industrial problems are characterized by:
* Large number of parameters involved
* Large number of constraints imposed on parameters
* Goals are often not known in detail
* Need for efficient solutions
* Natural problem representation for easy development and maintenance
These characteristics make modeling and solving these problems quite complex.
What is the ultimate goal of constraint satisfaction?
The ultimate goal is to have programming tools where the problem is stated in a natural representation and the computer efficiently solves it
This reflects the desire for user-friendly interfaces in problem-solving.
What is an example of a constraint in a class schedule problem?
A constraint could be:
* Teachers cannot teach two classes at once
* Students should not be taught more than five hours in a row
* Only one class can be taught in one classroom
These constraints ensure the feasibility of scheduling.
What are the types of constraints in constraint satisfaction?
Constraints can be:
* Unary: involving one variable
* Binary: involving two variables
* n-ary: involving more than two variables
Examples include constraints like X > 10 (unary) or X + Y = 30 (binary).
What is the process of assigning values in CSP called?
The process is often called labelling
Labelling involves assigning values to variables from their domains while satisfying all constraints.
What is the difference between finite and continuous domains in constraint satisfaction?
Finite domains deal with discrete values, while continuous domains involve real numbers and complex values
Finite domains are more common in industrial applications, while continuous domains require more complex mathematical techniques.
What is a generate-and-test strategy?
A generate-and-test strategy involves generating all possible combinations of values and testing whether they satisfy the constraints
This method is often inefficient due to the large number of possible combinations.
What is the Min-Conflicts Heuristic?
The Min-Conflicts Heuristic is a local search algorithm that starts with a random assignment and attempts to reduce the number of violated constraints
This heuristic can still fall into local minima, leading to incomplete solutions.
What is the purpose of consistency checking in CSP?
Consistency checking aims to exploit knowledge regarding the solution by removing inconsistent values from variable domains based on constraints
This helps reduce the search space and improve efficiency.
What are the advantages of Constraint Logic Programming (CLP)?
Advantages of CLP include:
* Declarativeness
* Short development time
* Maintainability
* Ideal platform for constraint programming
* Elegant solution to efficiency problems in logic programming
CLP allows users to express problems naturally without needing to specify how to solve them.
Fill in the blank: A solution to a CSP is an _______ of values to the variables from their given domain.
assignment
The assignment must satisfy all constraints simultaneously.
True or False: All constraints in CSP are independent.
False
Constraints often share variables and are rarely independent.
What is the goal of the classic search algorithms in CSP?
The goal is to assign values to unbound variables such that all constraints on the variable are satisfied
Classic search algorithms typically involve depth-first search (DFS) or breadth-first search (BFS).
What is one common application of constraint satisfaction problems?
Common applications include:
* Scheduling
* Resource allocation
* Crew rotation
* Planning
CSPs are widely used in various industries due to their ability to handle complex constraints.
What is the significance of the ACM’s identification of constraint programming?
It has been identified as one of the strategic directions in computer research
This highlights the growing importance and relevance of constraint programming in the field.
What does the term ‘labelling’ refer to in CSP?
Labelling refers to the process of assigning values to variables from their domains while satisfying constraints
This is a crucial step in finding a solution to a CSP.
What module is used to support the Finite Domain Solver in SWI-Prolog?
library(bounds)
This module is essential for working with finite domain constraints.
How is a variable declared to be in a specific range in SWI-Prolog?
Var in Range where Range is denoted by L..U
L and U are integers defining the lower and upper bounds of the range.
What is the syntax to declare a list of variables restricted to a specific range?
[Vars] in Range
Example: [X,Y] in 1..10 restricts both X and Y to the range 1 to 10.
What does the constraint ?Expr #> ?Expr signify?
greater than
This is one of the binary constraint relations used in arithmetic expressions.
Which arithmetic operator is used to denote equality in SWI-Prolog constraints?
=
This operator checks if two expressions are equal.
What does the constraint sum(+Vars, +Op, ?Value) do?
It computes the sum of variables in Vars constrained by Op to equal Value
Op can be one of the binary constraint relation symbols.
What is the purpose of the all_different(+Vars) constraint?
Constrains all variables in Vars to be pair-wise not equal
This is useful in problems where unique values are required.
