Sumários

Constraint Satisfaction Problems

20 outubro 2016, 09:30 • Luís Manuel Marques Custódio

Formulation of a CSP problem

Constraint Graph

Constraint propagation: AC-3 algorithm

CSP as a search problem:

  • backtrack search
  • MRV and LCV heuristics
  • Forward checking and maintaining arc consistency

Local search for CSP

Adversarial Search

18 outubro 2016, 11:00 • Luís Manuel Marques Custódio

Alpha-Beta algorithm

Introduction to CSP problems

Solving search problems

13 outubro 2016, 11:00 • Luís Manuel Marques Custódio

Formulation of three search problems: Hanoi towers, Missionaries and Cannibals and Robot Navigation


Solving a search problem using uninformed search algorithms: DFS, BFS and Uniform Cost

Problem solving by search (cont)

13 outubro 2016, 09:30 • Luís Manuel Marques Custódio

A* complexity

Memory-bounded A*

  • ID A*
  • Recursive best-first
  • SMA*

Heuristic functions

Effective branching factor

Relaxed problems to find heuristics

Adversarial Search 

  • MiniMax algorithm

Problem solving by search (cont)

11 outubro 2016, 11:00 • Luís Manuel Marques Custódio

Depth-first search variants:

  • depth-limited search
  • iterative deepening search

Bidirectional search

Comparison among uninformed search strategies

Informed search

  • Greedy search
  • A *
  • Heuristic function properties:
    • admissibility 
    • consistency