CSP Flashcards
What are 4 main kinds of variables?
1) Boolean: |dom(V)| = 2
2) Finite: the domain contains a finite number of values
3) Infinite but discrete: the domain is countably infinite
4) Continuous: e.g real numbers between 0 and 1
What is a possible world?
Possible world is a complete assignment of values to a set of variables
Describe number of possible states.
Number of possible state is a product of cardinality of each domain, always exponential on the number of variables. (size of the domain)^(number of V)
What are constaints?
Constraints are restrictions on the values that one or more variables can take.
Name 2 types of constraints.
1) Unary constraint: restriction involving a single variable
2) k-ary constraint: restriction involving the domain of k different variables.
How can we specify constraints?
Constraints can be specified by:
- giving a function that returns true when given values for each variable which satisfy the constraint
- giving a list of valid domain values for each variable participating in the constraint
Define Constraint Satisfaction Problem.
A constraint satifaction problem consists of
- a set of variables
- a domain dom(v) for each variable
- a set of constraints C
What is a model of a CSP?
A model of a CSP is an assignment of values to all of its variables that satisfies all of its constraints.
Name several problems that can be solved with CSP.
- determine whether or not a model exists
- find a model
- find all of the models
- count the number of models
- find the best model, given some measure of model quality (optimization problem)
- determine whether some property of the variables holds in all models
Why even the simpliest problem of determing whether or not a model exists in a general CSP with finite domains is NP-hard?
Because there is no known algorithms with worst case polynomial time. we can’t hope to find an algorithm that is polynomial for all CSP’s.
Describle how generate and Test (GT) algorithms work.
Idea: Systematically check all possible worlds. ( Possible worlds: cross product of domains)
- Generate possible worlds one at a time.
- Test constraints for each one
If there are k variables, each with domain size d, and there are c constraint, the complexity of Generate & Test is…
O(cd^k)
When representing CSP as a search problem what are states, start state, successor function, goal state, and soltuion? Which algorithm would be most appropriate for this formulation?
States: partial assignment of values to variables.
Start state: empty assignment.
Successor function: states with the next variable assigned
Goal state: complete assignment of values to variables that satisfy all constraints
Solution: assignment
Depth-first search is the most appropriate because:
- no cycles
- Possibly very very large branching factor b
- All solutions are at the same depth
Explain how solving CSP using search works.
- Explore search space vie DFS but evaluate each constraint as soon as all its variables are bound.
- Any partial assignment that doesn’t satisfy the constraint can be pruned
What is the problem with solving CSP as graph search?
Problem of solving CSP as graph search: Performanve heavily depends on the order in which variables are considered.
What does it mean for variable to be domain consistent?
A variable is domain consistent if no value of its domain is ruled impossible by any unary constraints.
Define a constraint network.
A constraint network is defined by a graph, with
- one node for every variable (drawn as circle)
- one node for every constraint (drawn as rectangle)
- undirected edges running between variable nodes and constraint nodes
Define arc consistency.
An arc is arc consistent if for each value x in dom(X) there is some value y in dom(Y) such that r(x,y) is satisfied.
A network is arc consistent if all its arcs are arc consistent.
Can arc consistency rule out any models/solutions?
No, arc consistency does not tule out any models/solutions.
Describe the general idea of the arc consistency algorithm.
- Go through all the arcs in the network
- Make each arc consistent by pruning the appropriate domain when needed
- Reconsider arcs that could be turned back to being inconsistent
- Eventually reach a ‘fixed point’ : all arcs consistent
How can we enforce Arc Consistency?
If an arc is not arc consistent:
- Delete all values x in dom(X) for which there is no corresponding value in dom(Y)
- This deletion makes the arc arc consistent
- This removal can never rule out any models/solutions
Let the max size of a variable domain be d, and number of variables to be n. What is the worst-case complexity of Backtracking (DFS with pruning) ? What is the worst-case complexity of arc consistency algorithm? Explain.
Worst-case time complexity of Backtracking is O(d^n).
Worst-case time complexity of Arc Consistency Algorithm is O(n^2 * d^3).
The max number of binary constraints - (n * (n-1))/2
The time the same arc can be inserted in the ToDoArc list - O(d)
The number of steps involved in checking the consistency of an arc - O(d^2)
Can we have an arc consistent network with non-empty domains that has no solutions?
Yes, example: vars A, B, C with domain {1,2} and constraints A != B, B != C, A != C.
For search by domain splitting, how many CSP’s do we need to keep around at a time? Assume solution at depth m and b children at each split.
O(bm): It is DFS
Describe domain splitting in arc consistency.
A technique used when one of the variables in the result of arc consistency has more that one value in the domain. Split the problem in a number of disjoint cases. Solution to CSP is the union of solutions to CSPi.
Why local search is used to solve CSP?
Solving CSPs is NP-hard:
- search for many CSPs is huge
- exponential in the number of variables
- even arc consistency with domain splitting is not enough.
Local search searches the space locally, rather than systematically. It often finds a solution quickly, but are nor guaranteed to find a solution of one exists (thus cannot prove that there is a solution). Best method for many constraint satisfaction and constraint optimization problems.
Describe the idea of local search.
Idea:
- Consider the space of complete assignments of values to variables (all possible worlds)
- Neighbors of a current node are similar variable assignments.
- Move from one node to another according to a function that scores how good each assignment is.
Define local search problem.
Definition: A local search problem consists of a:
- CSP: a set of variables, domains for these variables, and constraints on their joint values.
- A node in the search space will be a complete assignment to all of the variables.
- Neighbor relation: and edge in the search space will exist when the neighbor relation holds between a pair on nodes.
- Scoring function: h(n), judges cost of a node ( e.g. the number of constraints violated in node n, the cost of a state in an optimization context)
Does the local search backtrack?
No, local search does not backtrack.
How to determine the neighbor node to be selected in local search?
Use iterative best improvement - select the neighbor that optimizes some evaluation function.
Describe the iterative best improvement of the the local search. What is greedy descent, hill climbing?
Choose the neighbor with minimal number of constraint violations.
Greedy descent: evaluate h(n) for each neighbor, pick the neighbor n with the minimal h(n).
Hill climbing: equivalent algorithm for maximization problems. Everything that is said for hill climbing is also true for greedy descent.
What is the problem with iterative best improvement of the local search? What is the solution?
It gets trapped in locally optimal points (local maxima/minima). Solution is stochastic local search.
Describe stochastic local search.
Use greedy steps to find local minima, move to neighbor with best evaluation function value. Use randomness to avoid getting trapped in local minima.
