Grafos - Buscas
1 - Conceitos e termos
2 - Aplicações
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
Quebra Cabeças
 Qual seria uma implementação de busca adeuqada?
2
8
3
1
6
4
5
7
1
2
3
4
5
6
7
8