Modelo2

INTELIGÊNCIA ARTIFICIAL
Francisco Barretto [e-mail] Aula 04: Definição de Problemas: Satisfação de
Restrições

Sumário
¨༊
¨༊
¨༊
¨༊
¨༊
¨༊

Preâmbulo
O que é um problema em IA?
Como formular um problema?
Tipos de problemas
Implementação
Como procurar a solução de um problema?
¤༊

Satisfação de restrições

Preâmbulo
¨༊

O agente reativo ...
¤༊ Escolhe

suas ações com base apenas nas percepções

atuais
¤༊ não tem estado interno
¤༊ portanto, não pode pensar no futuro
¤༊ Não sabe “aonde vai”

Preâmbulo
¨༊

O agente solucionador de problemas ...
¤༊ busca

uma seqüência de ações que leve a estados desejáveis (objetivos)
C
C

Estado inicial

B
A
C

A
A
B
B

C
A
B

A

⇒

B

A
B

C

A
C

B

C
C
B
A

B
A

C

A

A

A
A

Estado final

B
B
C

C

B
C

B

C
A

C

A

B
C
A

B

C
B

A
C
B

Preâmbulo
¨༊

Métodos de Busca
¤༊ Busca

é uma das mais poderosas abordagens para resolução de problemas em IA
¤༊ Busca é um mecanismo de resolução de problemas universal que: n༆ Sistematicamente

explora as alternativas n༆ Encontra a seqüência de passos para uma solução

Preâmbulo
¨༊

Espaço de problemas
¤༊ Uma

atividade simbólica orientada a objetivo ocorre em um espaço de problemas
¤༊ Busca em um espaço de problemas é visto como um modelo geral de inteligência

Preâmbulo
¨༊

Problemas clássicos
¤༊ Jogo

dos 8 números
¤༊ Torre de Hanoi
¤༊ Missionários e Canibais
¤༊ Jarro d’água
¤༊ Mundo do aspirador
¤༊ Mundo de Wumpus

• Mundo dos blocos
• Caixeiro viajante
• Labirinto
• Cripto-aritmética
• Problema de Einstein
• Xadrez, Bridge, etc

Preâmbulo
¨༊

Exemplo: O mundo do aspirador
¤༊ O

mundo consiste em duas salas
¤༊ Cada sala pode estar suja
¤༊ O agente pode estar em apenas uma das salas de cada vez
¤༊ Existem 8 estados possíveis ¤༊ O agente pode