Flashcards in CSP Deck (33):

1

## 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

2

## What is a possible world?

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

3

## 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)

4

## What are constaints?

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

5

## 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.

6

## 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

7

## 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

8

## 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.

9

## 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

10

## 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.

11

## 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

12

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

### O(cd^k)

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?

###
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

14

## 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

15

## 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.

16

## 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.

17

## 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

18

## 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.

19

## Can arc consistency rule out any models/solutions?

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

20

## 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

21

## 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

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.

###
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)

23

## 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.

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.

### O(bm): It is DFS

25

## 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.

26

## 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.

27

## 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.

28

## 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)

29

## Does the local search backtrack?

### No, local search does not backtrack.

30

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

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

31

## 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.

32

## 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.

33