FACENS – Engenharia da Computação
Inteligência Artificial
Busca
Formulação do Problema
• Definição dos objetivos
• Cuidado com os fatores irrelevantes
• Representação do mundo em um dado
instante como um estado em um grafo
• Obter a solução é realizar uma busca
neste grafo de estados
Formulação do Problema
• Algumas definições:
— Espaço de estados: todos os estados
acessíveis do inicial
— Caminho: seqüência de estados conectados
por ações
— Solução Ótima: menos custo entre todas as
possíveis soluções
— Custo do Passo: custo numérico para executar
uma deteminada ação em um estado
Formulação do Problema
• Componentes formais:
— Estado inicial: como o problema começa, em
um determinado estado
— Função Sucessor: possíveis ações, funções
que, dado um estado e uma ação levam para
outro estado
— Teste de Objetivo: verificar se o estado
alcançado corresponde a um objetivo
— Custo de Caminho: um custo numérico para
cada caminho
Classes de problemas
• Miniproblemas: para teste de algoritmos
— Jogo de blocos
— 8 rainhas
• Problemas do mundo real:
—
—
—
—
Roteamento
Tour (Caixeiro viajante)
Navegação de robôs
Busca na Internet
Buscando a solução
• Árvore de Busca e Grafo de Busca
• Mesmo um grafo finito pode gerar uma
árvore infinita
• Busca em árvore:
— Verificar se o estado é o objetivo
— Senão, aplicar a função sucessor ao estado
com todas as ações possíveis
— Adicionar estados alcançáveis à pilha ou fila
(profundidade ou largura) e ir para um dos
novos estados
• Busca pode ser sem informação ou
heurística
Buscando a solução
• Busca sem informação
— Busca em extensão: utiliza fila para percurso
em largura no grafo/árvore
— Busca de custo uniforme: expande o nó com o
caminho de custo mais baixo
— Busca em profundidade: utiliza pilhas para
caminho em profundidade
— Busca em profundidade limitada: a busca é
limitada a uma profundidade determinada
— Busca de aprofundamento iterativo: o limite
da profundidade é aumentado a cada passo
— Busca bidirecional
Bidirecional
• Partir com uma busca do estado inicial, e
outra do estado desejado
• Quando as duas se cruzam, o caminho
pode ser traçado
• Entretanto, nem sempre o objetivo é um
estado simples
Leitura recomendada
• Capítulo 3 (p. 62-93), Russel & Norvig.