Fichas
04 Constraint Satisfaction Problems
Fichas del conjunto (11)
- 1What are the differences between CSPs and standard search problems? What is the advantage here?-Factored representations of each state (variables with values)
-Goal test: value for each variable that satisfies all constraints of the problem
-Path is irrelevant, every solution appears at depth n with n variables (use depth-first)
Benefit: general-purpose algorithms by exploiting internal structure of the states - 2How does the standard search formulation for all CSPs (Naive Search Approach) look like?-Initial state: empty assignment
-Successor function: assigns value to unassigned variable not conflicting with current assignment
-Goal test: current assignment is complete - 3When can Backtracking be applied and how does the method look like?For CSPs with single-variable assignments (commutative)
1.Which variable should be assigned next: first degree heuristic (largest number of constraints), then minimum-remaining-values (MRV) heuristic (fail-first)
2.In what order should values be tried: least constraining value (fail-last) - 4What is inference and which two techniques are there?Act or process of deriving logical conclusions from known premises
-Forward Checking
-Arc Consistency - 5How does Forward Checking work?Consistency (between variable X and variables Y) check eliminations of domains improve the search
- 6How does Arc Consistency work?If for every value in the one reduced domain there exists a value in the other, which satisfies binary constraint
-Procedure: check consistency, remove if inconsistent value, check with other neighbors - 7How can tree-structured CSPs be solved?1.Topological sort: choose variable as a root & order from root to leave
2.Make obtained variable order direct arc-consistent
3.March down list of variables & choose any remaining value (no backtracking required!) - 8What are two approaches for nearly tree-structured CSPs?-Conditioning
-Tree decomposition - 9How does Conditioning work?1.Choose subset - graph becomes tree after removal of S
2.Remove values from other domains if assignment is constraint-satisfying to variables in S - if remaining CSP has solution, return it with the one of S - 10How does Tree Decomposition work?1.Set of connected subproblems connected by a super-tree
2.Solve each subproblem independently
3.If every subproblem is solved, attempt of global solution using efficient algorithm for trees - 11What must be satisfied for the application of Tree Decomposition?-every part of the original problem must appear in at least one subproblem
-connected parts of the orginial problem must be connected in at least one subproblem
-if variable appears in two subproblems, it must appear in every subproblem along this path
-if any subproblem has no solution, the entire problem has no solution
Información
- Descripción
- Artificial Intelligence Fichas sobre 04 Constraint Satisfaction Problems, creado por Timo Bierwirth el 22/02/2018.
- Creado por
- Timo Bierwirth
- Visitas
- 0
- Valoración