CSP

Question 1

Discrete CSP

Answer 1

If all the variables have countable domains (finite and infinite domains)

Question 2

Continuous CSP

Answer 2

If domain is uncountable

Question 3

Time complexity

Answer 3

Linear constraints are solvable in polynomial time (nd). Non linear is exponential (d^n)

Question 4

Types of constraints

Answer 4

Unary
Binary
Higher order
Preferences (Soft)

Question 5

Example of crypt arithmetic puzzles

Answer 5

SEND+MORE=MONEY

Question 6

When are auxiliary variables used

Answer 6

When there are higher order constraints >=5
Higher-order constraints can be transformed into equi-satisfiable binary constraints using auxiliary variables.

Question 7

What is a binary CSP?

Answer 7

A CSP where each constraint is binary or unary

Question 8

What is a constraint graph

Answer 8

The graph formed from binary CSP (A CSP where each constraint is binary or unary) whose nodes are variables and edges are constraints

Question 9

Examples of real world CSP

Answer 9

1. Job scheduling
2. Class timetabling
3. Queens or Rook placement on chess board
4. Assignment problems

Question 10

Define Constraint network

Answer 10

A constraint network is a triple <V, D, C>
Variables, Domains, and constraints (relations on the domain of the variables)

Question 11

Satisfying constraints

Answer 11

If the assignment is consistent with all the constraints

Question 12

What is a consistent and total assignment

Answer 12

If the assignment holds tru for all variables and respects all the constraints - Consistent

If all variables are assigned - Total

Question 13

How to view CSP as search problem

Answer 13

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

Question 14

Backtracking search in CSP

Answer 14

DFS for CSP with single variable assignment extension. It is the basic uninformed algorithm for CSPs. It can solve the 𝑛-queens problem for ≊𝑛,25

Question 15

How to make backtracking better?

Answer 15

Heuristics: Minimum Remaining Values (Which Variable) and Least Constraining Value Heuristic (Value Ordering)

Question 16

Minimum Remaining Values (Which Variable)

Answer 16

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.

Question 17

Why does MRV work?

Answer 17

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.

Question 18

Explain degree heuristic

Answer 18

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.

Question 19

Least Constraining Value Heuristic (Value Ordering)

Answer 19

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

Question 20

Constraint Propagation

Answer 20

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.

Question 21

Explain tightness in Constraint Networks

Answer 21

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

Question 22

What are the conditions for γ′ to be tighter than γ

Answer 22

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 γ

Question 23

Equivalent Constraint Networks

Answer 23

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

Question 24

What are the inference methods on constraint networks?

Answer 24

Forward checking, arc consistency and decomposition

Question 25

Forward Checking

Answer 25

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 .

Question 26

Is forward checking sound?

Answer 26

Yes. An inference procedure is called sound if every conclusion it derives is guaranteed to be true, provided the premises (or inputs) are true.

Question 27

What is the problem with forward checking?

Answer 27

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

Question 28

What is Arc consistency. How does it work? and how is it more better?

Answer 28

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.

Question 29

What are the different arc consistency available?

Answer 29

AC-1 and AC-3

Question 30

What is the time complexity of AC-1

Answer 30

O(k^2) where k is the domain size

Question 31

How does AC-3 work

Answer 31

watch
https://www.youtube.com/watch?v=4cCS8rrYT14&t=170s

Question 32

What is the run time of AC-3

Answer 32

With m constraints and d domain values
O(md^3)

Question 33

what is the disadvantage of AC-1

Answer 33

every pair of constraint gets checked again once the domain is changed (algorithm is revised)

Question 34

What is decomposition

Answer 34

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.

Question 35

Tree-structured CSPs

Answer 35

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.

Question 36

Algorithm for Tree-structured CSPs

Answer 36

1. Choose a variable as the root and arrange variables from root to leaves (like in a tree).
2. Apply a procedure to remove inconsistencies as you go down the tree.
3. Then assign values to the variables as you go back up, ensuring consistency.

Question 37

Nearly Tree-structured CSPs

Answer 37

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.

Question 38

Cutset Conditioning

Answer 38

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

Question 39

Time complexity for acyclic constraint graph

Answer 39

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.

Question 40

Acyclic graph algorithm

Answer 40

Steps:
1. Build a tree from the constraint graph by choosing a root variable and directing edges outward.

2. Order the variables topologically (from parent to children).
3. Ensure consistency by revising the constraints as you move from the leaves to the root.

Question 41

What type pf problem is cutest conditioning

Answer 41

Finding the optimal cutset is computationally hard (NP-hard), but good approximations exist, meaning we can often solve these problems efficiently in practice.

Question 42

CSP with Local search

Question 43

Min-complexity heuristic

Question 44

Min Complexity run time

Answer 44

Constant and then explosive