O GoConqr está de visual novo! Conte para nós o que você achou.

Registre-se grátis

Flashcards

Artificial intelligence - Constraint Satisfaction Problems

Wojciech Gryncze Artificial intelligence A-Level Inglês 19 flashcards

Artificial intelligence - Constraint Satisfaction Problems

Flashcards do conjunto (19)

  1. 1What is a CSP• A set of variables, defined over domains
    • A set of constraints over the variables
  2. 2What is a solution?• A solution is a consistent assignment of values to the variables
    • Consistent assignment : does not violate any constraint
  3. 3Types of CSP• Discrete and finite domains
    • Discrete and infinite domains
    • Continuous (and infinite) domains
  4. 4Types of constraints• Unary constraints
    • Binary constraints
    • Higher-order constraints
  5. 5CSP as a search problemCSP as a search problem
  6. 6Backtracking search AlgoBacktracking search Algo
  7. 7Backtracking search : how reduce the search space?We can reduce the search space by choosing the right value for the variables
  8. 8Variable OrderingVariable Ordering
  9. 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.
  10. 10Constraint Propagation: Techinques to reduce the size of the domain• Arc consistency
    • Path consistency
    • Node consistent
    • Bound consistency
    • Global constraint
  11. 11Arc consistency AlgoTime complexity: O(n2d3)Arc consistency Algo
  12. 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.    Forward checking
  13. 13Intelligent BacktrackingIntelligent Backtracking
  14. 14Local Search for CSPLocal Search for CSP
  15. 15Min-ConflictMin-Conflict
  16. 16Min-Conflict AlgoMin-Conflict Algo
  17. 17Structure of the problemsStructure of the problems
  18. 18Removing nodesRemoving nodes
  19. 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

Informações

Descrição
A-Level Artificial intelligence FlashCards sobre Artificial intelligence - Constraint Satisfaction Problems, criado por Wojciech Gryncze em 10-01-2016.
Visualizações
2
Tags
ia
Avaliação

Fale Conosco

Sobre o que é sua mensagem?

O que você acha do novo visual?

Você gostou?