CSP Flashcards
Discrete CSP
If all the variables have countable domains (finite and infinite domains)
Continuous CSP
If domain is uncountable
Time complexity
Linear constraints are solvable in polynomial time (nd). Non linear is exponential (d^n)
Types of constraints
Unary
Binary
Higher order
Preferences (Soft)
Example of crypt arithmetic puzzles
SEND+MORE=MONEY
When are auxiliary variables used
When there are higher order constraints >=5
Higher-order constraints can be transformed into equi-satisfiable binary constraints using auxiliary variables.
What is a binary CSP?
A CSP where each constraint is binary or unary
What is a constraint graph
The graph formed from binary CSP (A CSP where each constraint is binary or unary) whose nodes are variables and edges are constraints
Examples of real world CSP
- Job scheduling
- Class timetabling
- Queens or Rook placement on chess board
- Assignment problems
Define Constraint network
A constraint network is a triple <V, D, C>
Variables, Domains, and constraints (relations on the domain of the variables)
Satisfying constraints
If the assignment is consistent with all the constraints
What is a consistent and total assignment
If the assignment holds tru for all variables and respects all the constraints - Consistent
If all variables are assigned - Total
How to view CSP as search problem
We can view a constraint network as a search problem, if we take the states as the variable assignments, the actions as assignment extensions, and the goal states as consistent assignments.
โทIdea: Every constraint network induces a single state problem.
Given a constraint network
๐พ :=ใ๐,๐ท,Cใ,
then ฮ ๐พ :=ใ๐ฎ๐พ,๐๐พ,๐ฏ๐พ,โ๐พ,๐ข๐พใis called the search problem induced by ๐พ, iff
โทStates ๐ฎ๐พ are variable assignments
โทActions ๐๐พ: extend ๐โ๐ฎ๐พ by a pair ๐ฅโฆ๐ฃ not conflicted with ๐.
โทTransition model ๐ฏ(๐,๐)=๐,๐ฅโฆ๐ฃ (extended assignment)
โทInitial state โ๐พ: the empty assignment ๐.
โทGoal states ๐ข๐พ: the total assignments
Backtracking search in CSP
DFS for CSP with single variable assignment extension. It is the basic uninformed algorithm for CSPs. It can solve the ๐-queens problem for โ๐,25
How to make backtracking better?
Heuristics: Minimum Remaining Values (Which Variable) and Least Constraining Value Heuristic (Value Ordering)
Minimum Remaining Values (Which Variable)
The minimum remaining values (MRV) heuristic for backtracking search always chooses the variable with the fewest legal values, i.e. a variable ๐ฃ that given an initial assignment ๐ minimizes its domain count.
Why does MRV work?
By choosing a most constrained variable ๐ฃ first, we reduce the branching factor (number of sub trees generated for ๐ฃ) and thus reduce the size of our search tree.
Explain degree heuristic
Used as a tie breaker in MRV. The degree heuristic in backtracking search always chooses a most constraining variable, i.e. given an initial assignment ๐ always pick a variable ๐ฃ with
maximum constraints. By choosing a most constraining variable first, we detect inconsistencies earlier on and thus reduce the size of our search tree.
Least Constraining Value Heuristic (Value Ordering)
Given a variable ๐ฃ, the least constraining value heuristic chooses the least constraining value for ๐ฃ: the one that rules out the fewest values in the remaining variables, i.e. for a given initial assignment ๐ and a chosen variable ๐ฃ pick a value ๐โ๐ท๐ฃ that minimizes the domain count
Constraint Propagation
Constraint propagation (inference in constraint networks) is deriving additional constraints, that follow from the already known constraints, i.e. that are satisfied in all solutions.
We say that two constraint networks
๐พ:=ใ๐,๐ท,๐ถใand ๐พโ:=ใ๐,๐ทโ,๐ถโใsharing the same set of variables are equivalent, (๐พโโก๐พ), if they have the same solutions.
Explain tightness in Constraint Networks
Tighter means the constraints or allowed values in one network (ฮณโฒ) are stricter or more limiting compared to the other network (ฮณ).
Constraint Propagation is tightening up without losing solutions
What are the conditions for ฮณโฒ to be tighter than ฮณ
Domain: The domain of ฮณโฒ is a subset of ฮณ (so the domain could have same or lesser number of values)
Constraints: The constrains of ฮณโฒ are either a subset of ฮณ and new constraints can be added to ฮณโฒ that are not part of ฮณ
Equivalent Constraint Networks
Let ๐พ and ๐พโ be constraint networks such that ๐พโโก๐พ and๐พโโ๐พ. Then ๐พโ has the same solutions as, but fewer consistent assignments than, ๐พ.
โทโคณ๐พโ is a better encoding of the underlying problem.
โทTwo equivalent constraint networks
What are the inference methods on constraint networks?
Forward checking, arc consistency and decomposition
Forward Checking
When you assign a value to a variable, forward checking immediately looks ahead at the neighboring (or future) variables to ensure that the current assignment doesnโt violate any constraints with unassigned variables.
Suppose youโre assigning a value to variable Xi. Once you assign a value to
Xi , forward checking looks at the variables that havenโt been assigned yet (letโs call them Xj) and checks the constraints between Xi and Xj. If any value in the domain of Xj is incompatible with the current assignment of Xi , that value is removed from the domain of Xj .
Is forward checking sound?
Yes. An inference procedure is called sound if every conclusion it derives is guaranteed to be true, provided the premises (or inputs) are true.
What is the problem with forward checking?
Forward checking only checks the immediate neighbors and It only makes inferences from assigned to unassigned variables. There is a better inference technique. Arc consistency
What is Arc consistency. How does it work? and how is it more better?
A variable v is arc consistent relative to another variable w if there is either no direct arc (constraint) between them or for every value in the domain of v has a value in the domain of w that satisfies the constraints
Ensures consistency for all arcs (constraints) between variables in the entire CSP, not just immediate neighbors.
What are the different arc consistency available?
AC-1 and AC-3
What is the time complexity of AC-1
O(k^2) where k is the domain size
How does AC-3 work
watch
https://www.youtube.com/watch?v=4cCS8rrYT14&t=170s
What is the run time of AC-3
With m constraints and d domain values
O(md^3)
what is the disadvantage of AC-1
every pair of constraint gets checked again once the domain is changed (algorithm is revised)
What is decomposition
The process of decomposing a constraint network into components is called decomposition.
The idea behind decomposing a constraint graph is to break it down into smaller subgraphs (or components) that can be solved independently or combined later. The most common approach is to find parts of the graph that are only loosely connected to the rest and solve these parts separately.
If youโre coloring a map, and Tasmania is not connected to the rest of Australia, you can color Tasmania separately without affecting the rest of the map.
Tree-structured CSPs
A CSP is tree-structured if its constraint graph has no loops (itโs acyclic).
Tree-structured CSPs are much easier to solve and can be done in time proportional to the size of the problem (O(n*dยฒ)), compared to general CSPs, which are much harder to solve.
Algorithm for Tree-structured CSPs
- Choose a variable as the root and arrange variables from root to leaves (like in a tree).
- Apply a procedure to remove inconsistencies as you go down the tree.
- Then assign values to the variables as you go back up, ensuring consistency.
Nearly Tree-structured CSPs
This is a method where you โfixโ a variable by assigning it a value and pruning the options for its neighbors. This makes the problem easier, as it can reduce it to a simpler (tree-like) structure.
Cutset Conditioning
Cutset conditioning is a technique where you remove certain variables (the cutset) to break cycles in the constraint graph, leaving a tree structure that can be solved easily. The process involves solving smaller sub-problems recursively.
Figure out which node in the graph I should solve first, so that the subgraph becomes acyclic and then I can solve the rest of the graph easily (Australia map SA)
Cutest is basically converting constraint graphs into acyclic graph
Time complexity for acyclic constraint graph
If a CSP has an acyclic constraint graph, it can be solved in polynomial time (O(nkยฒ)), making it much easier to solve than a general CSP.
Acyclic graph algorithm
Steps:
1. Build a tree from the constraint graph by choosing a root variable and directing edges outward.
- Order the variables topologically (from parent to children).
- Ensure consistency by revising the constraints as you move from the leaves to the root.
What type pf problem is cutest conditioning
Finding the optimal cutset is computationally hard (NP-hard), but good approximations exist, meaning we can often solve these problems efficiently in practice.
CSP with Local search
Min-complexity heuristic
Min Complexity run time
Constant and then explosive
