CSP

Question 1

What are 4 main kinds of variables?

Answer 1

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

Question 2

What is a possible world?

Answer 2

Possible world is a complete assignment of values to a set of variables

Question 3

Describe number of possible states.

Answer 3

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)

Question 4

What are constaints?

Answer 4

Constraints are restrictions on the values that one or more variables can take.

Question 5

Name 2 types of constraints.

Answer 5

1) Unary constraint: restriction involving a single variable

2) k-ary constraint: restriction involving the domain of k different variables.

Question 6

How can we specify constraints?

Answer 6

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

Question 7

Define Constraint Satisfaction Problem.

Answer 7

A constraint satifaction problem consists of

• a set of variables
• a domain dom(v) for each variable
• a set of constraints C

Question 8

What is a model of a CSP?

Answer 8

A model of a CSP is an assignment of values to all of its variables that satisfies all of its constraints.

Question 9

Name several problems that can be solved with CSP.

Answer 9

• 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

Question 10

Why even the simpliest problem of determing whether or not a model exists in a general CSP with finite domains is NP-hard?

Answer 10

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.

Question 11

Describle how generate and Test (GT) algorithms work.

Answer 11

Idea: Systematically check all possible worlds. ( Possible worlds: cross product of domains)

• Generate possible worlds one at a time.
• Test constraints for each one

Question 12

If there are k variables, each with domain size d, and there are c constraint, the complexity of Generate & Test is…

Answer 12

O(cd^k)

Question 13

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?

Answer 13

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

Question 14

Explain how solving CSP using search works.

Answer 14

• 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

Question 15

What is the problem with solving CSP as graph search?

Answer 15

Problem of solving CSP as graph search: Performanve heavily depends on the order in which variables are considered.

Question 16

What does it mean for variable to be domain consistent?

Answer 16

A variable is domain consistent if no value of its domain is ruled impossible by any unary constraints.

Question 17

Define a constraint network.

Answer 17

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

Question 18

Define arc consistency.

Answer 18

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.

Question 19

Can arc consistency rule out any models/solutions?

Answer 19

No, arc consistency does not tule out any models/solutions.

Question 20

Describe the general idea of the arc consistency algorithm.

Answer 20

• 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

Question 21

How can we enforce Arc Consistency?

Answer 21

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

Question 22

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.

Answer 22

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)

Question 23

Can we have an arc consistent network with non-empty domains that has no solutions?

Answer 23

Yes, example: vars A, B, C with domain {1,2} and constraints A != B, B != C, A != C.

Question 24

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.

Answer 24

O(bm): It is DFS

Question 25

Describe domain splitting in arc consistency.

Answer 25

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.

Question 26

Why local search is used to solve CSP?

Answer 26

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.

Question 27

Describe the idea of local search.

Answer 27

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.

Question 28

Define local search problem.

Answer 28

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)

Question 29

Does the local search backtrack?

Answer 29

No, local search does not backtrack.

Question 30

How to determine the neighbor node to be selected in local search?

Answer 30

Use iterative best improvement - select the neighbor that optimizes some evaluation function.

Question 31

Describe the iterative best improvement of the the local search. What is greedy descent, hill climbing?

Answer 31

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.

Question 32

What is the problem with iterative best improvement of the local search? What is the solution?

Answer 32

It gets trapped in locally optimal points (local maxima/minima). Solution is stochastic local search.

Question 33

Describe stochastic local search.

Answer 33

Use greedy steps to find local minima, move to neighbor with best evaluation function value. Use randomness to avoid getting trapped in local minima.