summary Flashcards
What is a standard search problem?
Standard search problem:
State is a “black box” – any data structure that supports goal
test, eval, successor
What is a Constraint Satisfaction Problem (CSP)?
A CSP is defined by variables Xi, each with values from a domain Di, and a goal test defined by constraints specifying allowable combinations of values for subsets of variables.
What are the advantages of CSP representation?
CSPs allow the use of general-purpose algorithms, additional pruning strategies, and structured problem-solving approaches.
What is the graph-coloring problem?
Given an undirected graph G=(V, E) and a set of colors C, assign colors to vertices such that no two adjacent vertices (connected by an edge) share the same color.
What are practical examples of the graph-coloring problem?
Compiler optimization (e.g., registry allocation) and scheduling (e.g., assigning jobs to time slots).
What is the map-coloring problem?
A special case of graph-coloring where regions (vertices) on a map are assigned colors such that no two adjacent regions share the same color.
What is the definition of a CSP in terms of a triple (X, D, C)?”
A CSP is represented as X = {X1, …, Xn} (variables), D = {D1, …, Dn} (domains of values), and C = {C1, …, Cm} (constraints on allowable value combinations).
What is the scope of a constraint?
The scope of a constraint is the k-tuple of variables it relates to, denoted as tj = (Xo, …, Xp).
The “scope of a constraint” in Constraint Satisfaction Problems (CSPs) refers to the set of variables that are involved in or affected by the constraint
What is the definition of an assignment in CSPs?
what is a consistent and complete assignment?
An assignment maps variables Xi to values vi in their respective domains Di.
An assignment in a Constraint Satisfaction Problem (CSP) is consistent if it satisfies all the constraints that apply to the variables included in the assignment. It ensures that no conflicts exist between the assigned values for the variables involved.
An assignment is complete if it assigns a value to every variable in the problem, regardless of whether it satisfies the constraints or not.
To solve a CSP, we aim for an assignment that is both consistent and complete, meaning all variables are assigned values and all constraints are satisfied.
What is a constraint graph?
A visual representation where nodes are variables, and edges represent constraints between pairs of variables.
What is a binary CSP?
A CSP where each constraint relates two variables.
What are examples of discrete CSPs with finite domains?
Boolean CSPs (e.g., satisfiability problems), job scheduling, and map coloring.
What are examples of CSPs with infinite discrete domains?
CSPs where variables represent integers, strings, or other discrete entities, like job start/end days.
What are continuous domain CSPs?
CSPs where variables represent continuous values, such as time intervals for scheduling telescope observations.
What are the types of constraints?
Unary (single variable), binary (two variables), and higher-order (3+ variables).
What is backtracking search?
Backtracking search is a fundamental algorithm used in Constraint Satisfaction Problems (CSPs) to find solutions by systematically exploring possible variable assignments while ensuring constraints are not violated.
Key Characteristics of Backtracking Search:
1. Incremental Assignment:
• The algorithm assigns values to one variable at a time, starting with an empty assignment.
• After assigning a value to a variable, it checks whether the assignment is consistent with the problem’s constraints.
2. Constraint Checking:
• At each step, the algorithm verifies if the partial assignment satisfies all constraints.
• If a constraint is violated, the algorithm “backtracks” to the previous variable and tries a different value.
3. Systematic Exploration:
• It systematically explores all possible assignments in a depth-first manner.
• Variables are assigned values from their domain in a specific order.
4. Termination:
• The algorithm stops when a complete assignment satisfying all constraints is found or when all possibilities are exhausted (indicating no solution).
Steps of Backtracking Search:
1. Start with an empty assignment.
2. Choose an unassigned variable.
3. Assign a value to the variable from its domain.
4. Check for consistency:
• If the assignment is consistent with constraints, proceed to the next variable.
• If the assignment is inconsistent, backtrack by removing the last assigned value and trying the next value in the domain.
5. Repeat until all variables are assigned (solution found) or all options are exhausted (no solution).
Example:
Consider a CSP with variables , domains , and constraints .
1. Assign a value to  from .
2. Check if ’s value satisfies .
3. Assign a value to  from , ensuring  is satisfied.
4. If ’s assignment leads to inconsistency, backtrack to  and try another value.
5. Continue this process for  and other variables.
Advantages:
• Simple and easy to implement.
• Guarantees a solution if one exists by exploring all possibilities.
Limitations:
• Inefficiency: Explores many unnecessary branches.
• Exponential Time: In the worst case, explores all possible assignments.
Enhancements to Backtracking:
To improve efficiency, several techniques can be used:
1. Forward Checking: Prune values from the domains of unassigned variables that would violate constraints.
2. Constraint Propagation: Use algorithms like Arc-Consistency (AC-3) to propagate constraints and reduce domain sizes.
3. Variable and Value Ordering:
• MRV (Minimum Remaining Values): Choose the variable with the fewest legal values.
• LCV (Least Constraining Value): Choose the value that leaves the most options for other variables.
Backtracking search is the backbone of many CSP solvers and serves as the foundation for more advanced algorithms.
What is the Minimum Remaining Values (MRV) heuristic?
A variable selection heuristic that chooses the variable with the fewest legal values remaining.
What is the (DEG) degree heuristic?
A variable selection heuristic that chooses the variable involved in the most constraints with other unassigned variables.
choosing the variable with the most constraints on remaining variables—i.e., the variable that is involved in the largest number of constraints with unassigned variables.
What is the (LCV) least constraining value heuristic?
- LCV selects the value that minimally restricts the options for other unassigned variables.
- It evaluates the potential effects of assigning each value to a variable and prefers the one that leaves the most flexibility for subsequent assignments.
Explanation of LCV:
* The LCV heuristic selects the value that minimizes the constraints imposed on other unassigned variables. In other words, it prefers values that leave the greatest flexibility for the remaining variables to be assigned.
* It aims to reduce the likelihood of future conflicts, thereby decreasing the chances of needing to backtrack.
Steps for Applying LCV:
1. Choose a variable to assign a value (using some variable selection heuristic like Minimum Remaining Values (MRV)).
2. For each value in the variable’s domain, compute how many remaining values in the domains of other unassigned variables will be eliminated if this value is chosen.
3. Sort the values in the domain of the chosen variable in increasing order of the number of constraints they impose on others.
4. Assign values to the variable in this sorted order.
What is forward checking?
When a value is assigned to a variable, forward checking:
1. Looks ahead to the unassigned variables that are connected to the current variable by constraints.
2. Removes any values from their domains that are inconsistent with the current assignment.
By pruning the domains of the unassigned variables, forward checking ensures that no invalid assignments are made later, which helps to detect potential dead-ends earlier in the search.
What is arc consistency in CSPs?
Arc consistency: Xi is arc-consistent with respect to another
variable Xj if for every value in the current domain Di there is
some value in the domain Dj that satisfies the binary
constraint on the arc (Xi , Xj )
What is the AC-3 algorithm?
An algorithm that enforces arc consistency by iteratively removing inconsistent values from variable domains.
What is the complexity of the AC-3 algorithm?
O(c * d^3), where c is the number of arcs and d is the domain size. It can be reduced to O(c * d^2) using the AC-4 algorithm.
What are tree-structured CSPs? what is the complexity at which they can be solved?
CSPs with no loops in their constraint graph. These can be solved in O(n * d^2) time, where n is the number of variables and d is the domain size.
