Karteikarten
Artificial intelligence - Constraint Satisfaction Problems
Karten in diesem Stapel (19)
- 1What is a CSP• A set of variables, defined over domains
• A set of constraints over the variables - 2What is a solution?• A solution is a consistent assignment of values to the variables
• Consistent assignment : does not violate any constraint - 3Types of CSP• Discrete and finite domains
• Discrete and infinite domains
• Continuous (and infinite) domains - 4Types of constraints• Unary constraints
• Binary constraints
• Higher-order constraints - 5CSP as a search problem
- 6Backtracking search Algo
- 7Backtracking search : how reduce the search space?We can reduce the search space by choosing the right value for the variables
- 8Variable Ordering
- 9Constraint PropagationThe objective is to reduce the search space. To achieve that, we will try to find an equivalent CSP
to the original one with smaller domains of variables. - 10Constraint Propagation: Techinques to reduce the size of the domain• Arc consistency
• Path consistency
• Node consistent
• Bound consistency
• Global constraint - 11Arc consistency AlgoTime complexity: O(n2d3)
- 12Forward checkingWhen X is assigned a value v:
• Look at each unassigned variable T connected to X (with binary constraint).
• Remove from Y’s domain the value inconsistent with the valuer chosen for X.
• With MRV, failure occurs if a domain becomes empty.
- 13Intelligent Backtracking
- 14Local Search for CSP
- 15Min-Conflict
- 16Min-Conflict Algo
- 17Structure of the problems
- 18Removing nodes
- 19Grouping nodes• Each variable appears in at least one subproblems
• Two variable connected by a constraint must appear together in at least one subproblem
• If a variable appears in two subproblems, ti must appears in all subproblem on the path to
connected these subproblem
Informationen
- Beschreibung
- A-Level Artificial intelligence Karteikarten am Artificial intelligence - Constraint Satisfaction Problems, erstellt von Wojciech Gryncze am 10/01/2016.
- Erstellt von
- Wojciech Gryncze
- Aufrufe
- 2
- Tags
- Bewertung