Aula4 IA Problemas Classicos

Universidade Federal de Santa Catarina
Disciplina de Inteligência Artificial
Campus Araranguá

Problemas clássicos de

Inteligência Artificial
Profª Eliane Pozzebon [e-mail] Aplicações do método de Busca
 Exemplos de problemas clássicos de IA
 Canibais e Missionários
 Jogo ou Quebra-Cabeça de 8 Jogo das n rainhas
 Jogo dos n números (n-puzzle)
 Torre de Hanoi
 Palavras Cruzadas
 Cubo Mágico
 Caixeiro-Viajante
 ... etc.

2

Aplicações de Busca em problemas reais





Cálculo de Rotas






Rotas em redes de computadores
Sistemas de planejamento de viagens
Planejamento de rotas de aviões
Caixeiro-viajante
Jogos de computadores (rota dos personagens)



Salas de aula




Generalização do problema da navegação
Robôs movem-se em espaços contínuos, com um conjunto
(infinito) de possíveis ações e estados.

Alocação

Navegação de rôbos





Montagem de objetos complexos por robôs




Controlar os movimentos de um robô no chão, e de seus braços e pernas requer espaço multi-dimensional

etc

Ordenar a montagem de diversas partes de um objeto
3

Problemas clássicos de IA
 O quebra-cabeça de 8 é um tabuleiro quadrado com 9 divisões onde são colocadas oito peças quadradas, numeradas de 1 a 8. A nona divisão permanece descoberta. Cada peça tem um número. A peça adjacente ao espaço em branco pode ser deslocada para aquele espaço. O jogo consiste em uma posição inicial e uma posição-meta. O objetivo é transformar a posição inicial em posição-meta, deslocando as peças até que elas atinjam o local desejado.
4

Problemas clássicos de IA
 O Problema dos Baldes de Água: Você tem dois baldes, um de 4 litros e um de 3 litros. Nenhum deles tem qualquer marcação de medidas. Há uma bomba que pode ser usada para encher os baldes com água. Como é que você consegue colocar exatamente 2 litros de água no balde de 4 litros?
5

Problemas clássicos de IA
 O Problema do Caixeiro-Viajante: Um vendedor tem uma lista de cidades que precisa visitar exatamente