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
