Busca em Redes

Prévia do material em texto

Redes e Busca BásicaRedes e Busca Básica
Marco H. terraMarco H. terra
Introdução à Inteligência Artificial
IntroduçãoIntrodução
nn Este capEste capíítulo trata de como achar caminhos atravtulo trata de como achar caminhos atravéés de s de 
redes para resolver problemas de busca. Nestes problemas redes para resolver problemas de busca. Nestes problemas 
buscabusca--se soluse soluçções numa estrutura de rede semântica.ões numa estrutura de rede semântica.
nn A busca A busca éé um mecanismo genum mecanismo genéérico usado para resolurico usado para resoluçção de ão de 
problemas na falta de um mproblemas na falta de um méétodo mais direto. Neste todo mais direto. Neste 
capcapíítulo serão discutidas as seguintes estrattulo serão discutidas as seguintes estratéégias:gias:
uMétodos de busca cega: busca sistemática sem 
orientação da melhor maneira de realizá-la.
uMétodos de busca heuristicamente informados: 
busca sistemática onde as opções a serem exploradas 
são ordenadas, investigando-se inicialmente 
caminhos mais promissores.
n Exemplo: Deseja-se achar o caminho da cidade S para a 
cidade G usando o mapa abaixo. Para encontrar um 
caminho entre as cidades deve se levar em conta:
� O custo de computação para encontrar a resposta;
� O custo de viagem para cruzar o caminho escolhido.
n Este tipo de problema pode ser representado empregando-
se árvore de busca.
n Para se resolver o problema especifica-se os caminhos que 
resultam em “loops” e arranja-se todas as possíveis 
soluções a partir do nó inicial numa árvore de busca.
nUma árvore de busca é uma representação em árvore 
semântica na qual:
= Os nós denotam caminhos;
= Ramos conectam caminhos para caminhos de um 
passo de extensão;
= Tem escritores que conectam um caminho a uma 
descrição de caminho;
= Tem leitores que produzem uma descrição de 
caminho.
n Exemplo de uma árvore de busca feita a partir de uma rede 
como na Figura 1.
= Cada nó denota um caminho;
= Cada nó filho denota uma extensão de um passo no 
caminho;
= Uma rede se transforma numa árvore considerando-se 
todos os caminhos que não resultem em “loops”.
Terminologia de Árvores de BuscaTerminologia de Árvores de Busca
� Um nó filho denota um caminho de um passo de extensão 
a partir de seu nó pai;
� Tem as mesmas definições que árvore semântica de nó
raiz, nós folhas, ancestral e descendente;
� Nó com fator de ramificação b: nó com b filhos;
� Árvore cujo fator de ramificação é b: todos os nós não-
folhas possuem b filhos;
� Caminho parcial é aquele que não atinge o nó meta. 
Quando este é alcançado tem-se o caminho total. 
Métodos de Busca CegaMétodos de Busca Cega
nBusca em Profundidade (Depth-first search);
� Parte-se do princípio que todos os caminhos têm 
importâncias idênticas. Escolhe-se um dos filhos de 
qualquer nó considerado e passa-se a trabalhar a partir 
deste ponto. Abandona-se temporariamente outras 
alternativas no mesmo nível. Segue-se neste processo até
atingir um nó folha. No mesmo nível procura-se da 
esquerda para direita. Quando se atinge um nó folha que 
não é um nó meta retorna-se até o nível hierárquico com 
nós filhos ainda não explorados e reinicia-se o processo.
� Exemplo:
• Escolhe-se o filho mais à esquerda (A) a partir do nó
raiz (S);
• Repete-se a operação anterior chegando-se ao nó folha 
(C);
• Retorna-se ao ancestral que ainda tenha nós filhos não 
explorados (B) e repete-se o processo;
• Para-se o processo ao achar um nó folha = nó meta (G).
n Para se conduzir uma Busca em Profundidade:
� Forme uma fila de um elemento consistindo de um 
caminho de comprimento nulo contendo apenas o nó raiz;
� Até o 1o caminho na fila terminar em um nó meta ou até a 
fila estar vazia:
• Remova o primeiro caminho da rede; crie caminhos 
novos estendendo o primeiro caminho a todos os 
vizinhos do nó terminal;
• Rejeite todos os caminhos novos com LOOPS;
• Adicione novos caminhos, se existirem, na frente da fila;
� Anuncie sucesso ou fracasso.
Métodos de Busca CegaMétodos de Busca Cega
nBusca em Amplitude (Breath-first search);
� Este tipo de busca cega investiga todos os possíveis 
caminhos de um dado comprimento antes de se mover ao 
longo de qualquer caminho específico. Em outras palavras, 
considera-se todas as opções em um mesmo nível 
hierárquico antes de mudar de nível. O método encerra a 
busca quando o primeiro nó meta for encontrado no nível 
hierárquico mais superior. Neste método, também se segue 
a convenção de se caminhar da esquerda para a direita.
� Exemplo (Figura 4): a movimentação para os níveis 
hierárquicos mais baixos acontecem nível a nível, até que 
se atinja o objetivo. 
n Para se conduzir uma Busca em Amplitude:
� Forme uma fila de um elemento consistindo de um 
caminho de comprimento nulo contendo apenas o nó raiz;
� Até o 1o caminho na fila terminar em um nó meta ou até a 
fila estar vazia:
• Remova o primeiro caminho da fila; crie novos 
caminhos estendendo o primeiro caminho a todos os 
vizinhos do nó terminal;
• Rejeite todos os caminhos com LOOPS;
• Adicione novos caminhos, se existirem, no final da fila;
� Anuncie sucesso ou fracasso, se a meta for atingida ou 
não, respectivamente.
Busca em Amplitude
Escolha da Estratégia de Busca AdequadaEscolha da Estratégia de Busca Adequada
nBusca em Profundidade é:
� Adequada: Se existir segurança que todos os caminhos 
possíveis se encerram ou chegam ao objetivo após um 
número razoável de passos.
� Inadequada: Se existir caminhos longos ou infinitamente 
longos.
nBusca em Amplitude é:
� Adequada: Se existir segurança que o fator de ramificação 
é pequeno.
� Inadequada: Se o fator de ramificação for alto ou infinito.
nVantagens da busca em Profundidade:
� Requer menos memória uma vez que apenas os nós do 
caminho presente precisam ser armazenados;
� Pode encontrar a solução sem precisar examinar grande 
parte do espaço de busca, especialmente quando existem 
muitas soluções aceitáveis.
nVantagens da busca em Amplitude:
� Não explora um beco sem saída, não correndo o risco de 
seguir um caminho sem solução por um longo período;
� Encontra sempre uma solução, se ela existir. A solução 
encontrada é a que exige menor número de passos dentre 
todas as possíveis soluções.
n Exemplo - Problema do Caixeiro Viajante: um vendedor 
tem uma lista de cidades que precisa visitar uma única vez. 
Há estradas diretas entre cada par de cidades da lista. 
Encontre a rota que o vendedor deverá seguir para que a 
viagem seja a menor possível, e que comece e termine em 
uma mesma cidade, que poderá ser qualquer uma da lista.
� Solução: Uma estrutura de controle simples, sistemática, 
que cause movimento tal que explore todas as 
possibilidades possíveis. Ela só é adequada para um 
pequeno número de cidades. Para N cidades existe (N-1)! 
possíveis caminhos. Se N=11 => tem-se 3.628.800 
possíveis caminhos.
Busca Não-Determinística (Nondeterministic search)Busca Não-Determinística (Nondeterministic search)
n Serve para pesquisa em ramos centrais em estágios mais 
iniciais da busca. Neste tipo de busca se expande um nó
aberto escolhido aleatoriamente (expandir um nó significa 
determinar seus filhos).
n Este algoritmo é idêntico aos dois anteriormente mostrados 
exceto pela instrução de adição de novos caminhos, que se 
transforma em:
� Adicione os novos caminhos em lugares aleatórios na lista.
Métodos Heuristicamente Informados (Heuristically
Informed Methods)
Métodos Heuristicamente Informados (Heuristically
Informed Methods)
nMétodo Subida de Encosta (Hill-Climbing)
� Este método é idêntico ao método de busca em 
profundidade, exceto no detalhe de ordenamento das 
escolhas do caminho de busca. Neste método se considera 
alguma medida heurística da distância ao objetivo. As 
menores distâncias guiam a busca.
n Exemplo: Seja o problema de determinação da rota de uma 
cidade a outra. São conhecidas as distâncias em linha reta 
(Figura 5) de todas as cidades consideradas até a cidade 
objetivo (G).n Solução: O método sempre opta pelo nó, dentre os nós de 
um mesmo nível hierárquico, que tiver menor distância em 
linha reta para o nó meta:
� E se o caminho escolhido não chegar em G ?
� Este método pode também ser entendido como uma 
variação do método gerar-e-testar, onde uma função 
heurística avalia a proximidade do estado presente em 
relação ao estado objetivo. Esta distância guia a escolha do 
caminho a ser seguido no espaço de busca.
n Procedimento do método Subida de Encosta:
Para conduzir uma busca de Subida de Encosta:
� Forme uma lista de um único elemento que consiste do 
caminho de comprimento zero contendo apenas o nó raiz;
� Até o primeiro caminho na fila terminar no nó meta ou a 
lista estar vazia:
• Remova o primeiro caminho da lista; crie novos caminhos 
estendendo o primeiro caminho a todos os vizinhos do nó
terminal;
• Rejeite todos os caminhos com LOOPS;
• Ordene os caminhos, se eles existirem, levando em conta as 
distâncias estimadas entre seus nós terminais e a meta;
• Adicione novos caminhos, se existirem, no começo da lista;
� Se a meta é alcançada anuncie sucesso, se não for atingida 
anuncie fracasso.
n Este método é conveniente quando se tem uma boa função 
heurística para avaliar estados e nenhum outro 
conhecimento útil está disponível.
n Exemplo: Pessoa em cidade desconhecida, sem mapa, 
desejando-se chegar ao centro da cidade.
� Solução: Procura-se os prédios mais altos.
� Função Heurística: Distância entre a posição corrente e a 
posição dos prédios altos. Os estados desejáveis são 
aqueles nos quais a distância é minimizada.
Limitações:Limitações:
n Este método encontra limitações em situações como as 
comentadas a seguir:
� O problema das encostas pequenas (foothill problem): 
Existência de picos secundários no caminho. Estes pontos 
são máximos locais, e não globais, que impossibilitam a 
evolução do problema.
� O problema das planícies (the plateau problem): 
Existência de áreas planas separando os picos. Em casos 
extremos os picos parecem pilastras num campo de 
futebol. A operação local de escolha não funciona.
� O problema da cuminheira (ridge problem): Um mapa de 
contorno mostra que qualquer passo padrão leva a uma 
piora de estado, mesmo não havendo máximo local ou 
global.
nNestes casos pode se retornar a nós anteriores e tentar 
outros caminhos. Contudo, às vezes, inúmeros caminhos 
levam aos mesmos problemas.
n Para se checar um máximo local pode-se empregar busca 
não-determinística a partir daquele ponto.
n Pode-se usar Subida de Encosta pela Trilha mais Íngrime
(steepest-ascent hill climbing).
Busca em Feixe (beam search)Busca em Feixe (beam search)
n Esta busca avança nível a nível como na busca em 
amplitude. Contudo, quando muda de nível o método só
considera os w melhores nós em cada nível para prosseguir 
na busca.
n Exemplo de busca em Feixe. Nela a investigação ocorre 
nível a nível, mas apenas para os w=2 melhores caminhos.
Busca em Feixe
Busca em Feixe
Busca pela Melhor Escolha (best-first search)Busca pela Melhor Escolha (best-first search)
n Esta estratégia combina as vantagens das buscas em 
profundidade e em amplitude. Neste método, o movimento 
se dá a partir do melhor nó aberto, não interessando se o 
nó está na árvore parcialmente desenvolvida.
nA busca pela melhor escolha emprega uma função 
heurística apropriada para cada um dos nós gerados.
n Exemplo: Nó, Valor da função heurística associada ao nó.
� Passo 1: existe um só nó;
� Passo 2: faz-se busca orientada em amplitude;
� Passo 3 em diante: considera-se o nó com menor valor 
da função heurística. 
n Este método é muito semelhante à busca pela Subida da 
Encosta. Note porém, que na subida de encosta os 
movimentos rejeitados num nível não voltam a ser 
considerados posteriormente.
nResumo de Adequação de Alternativas de Busca.
� Busca em Profundidade é adequada quando caminhos 
parciais improdutivos não são nunca muito longos;
� Busca em Amplitude é conveniente quando o fator de 
ramificação não é muito alto;
� Busca Não-Determinística é interessante quando não se 
sabe qual das anteriores é a melhor;
� Busca Heurística é boa se existe uma medida natural entre 
cada nó e o nó meta;
� Busca por Subida de Encosta deve ser usada se a medida 
acima existe e um bom caminho é provável estar entre os 
caminhos parciais que aparentam ser bons em cada ponto 
de escolha;
nResumo de Adequação de Alternativas de Busca (cont.)
� Busca em Feixe é útil quando a distância acima existe e 
um bom caminho é provável estar entre os caminhos 
parciais que parecem bons em todos os níveis, nos nós 
considerados;
� Busca pela Melhor Escolha é propícia quando existe a 
função acima e um bom caminho parcial pode parecer uma 
opção ruim antes de caminhos mais promissores serem 
descartados.
Procedimentos cegos Procedimentos heurísticos
Busca em 
Profundidade
Busca em 
Amplitude
Busca Não 
Determinística
Subida de 
Encosta
Busca em 
Feixe Melhor 
Escolha
Pesquisa ótimaPesquisa ótima
n Procedimento de pesquisa limite e caminho (branch-and-
bound): 
� Forme uma lista de um único elemento que consiste do 
caminho de comprimento zero contendo apenas o nó raiz;
� Até o primeiro caminho na fila terminar no nó meta ou a 
lista estar vazia:
• Remova o primeiro caminho da lista; crie novos caminhos 
estendendo o primeiro caminho a todos os vizinhos do nó
terminal;
• Rejeite todos os caminhos com LOOPS;
• Adicione os novos caminhos restantes, se houver, à lista;
• Agrupe a lista inteira pelo tamanho do caminho colocando os 
caminhos com menor custo à frente;
� Se a meta é alcançada anuncie sucesso, se não for atingida 
anuncie fracasso.
n Procedimento de pesquisa limite e caminho (branch-and-
bound) com uma estimativa do limite inferior: 
� Forme uma lista de um único elemento que consiste do 
caminho de comprimento zero contendo apenas o nó raiz;
� Até o primeiro caminho na fila terminar no nó meta ou a 
lista estar vazia:
• Remova o primeiro caminho da lista; crie novos caminhos 
estendendo o primeiro caminho a todos os vizinhos do nó
terminal;
• Rejeite todos os caminhos com LOOPS;
• Adicione os novos caminhos restantes, se houver, à lista;
• Agrupe a lista inteira pela soma do tamanho do caminho e 
uma estimativa do limite inferior do custo restante, com os 
caminhos de menor custo à frente;
� Se a meta é alcançada anuncie sucesso, se não for atingida 
anuncie fracasso.
nO princípio da programação dinâmica: 
nO melhor caminho através de um caminho específico entre 
dois lugares é o melhor caminho para o objetivo do lugar 
de onde se inicia, seguido pelo melhor caminho de onde se 
está para o objetivo. Não existe necessidade de se 
inspecionar outros caminhos estando em um lugar 
intermediário entre o início e o objetivo. 
n Procedimento de pesquisa limite e caminho (branch-and-
bound) com programação dinâmica: 
� Forme uma lista de um único elemento que consiste do caminho de 
comprimento zero contendo apenas o nó raiz;
� Até o primeiro caminho na fila terminar no nó meta ou a lista estar vazia:
• Remova o primeiro caminho da lista; crie novos caminhos estendendo o primeiro 
caminho a todos os vizinhos do nó terminal;
• Rejeite todos os caminhos com LOOPS;
• Adicione os novos caminhos restantes, se houver, à lista;
• Se dois ou mais caminhos alcançam um nó comum, delete 
todos os caminhos que não alcancem o nó comum com o 
custo mínimo;
• Agrupe a lista inteira pelo tamanho do caminho com os 
caminhos de menor custo à frente;
� Se a meta é alcançada anuncie sucesso, se não for atingida 
anuncie fracasso.
• Pesquisa A*
Sub-estimativa e programação dinâmica para melhorar a 
pesquisa limite e caminho
...
- Se dois ou mais caminhos alcançam um nó comum, delete 
todos os caminhos que não alcancem o nó comum com o 
custo mínimo;
- Agrupe a lista toda pela soma do tamanho do caminho e 
uma estimativa do limite inferior do custo restante, com os 
caminhos de custo mínimo à frente;...
• Pesquisa A*
Sub-estimativa e programação dinâmica para melhorar a 
pesquisa limite e caminho
...
- Se dois ou mais caminhos alcançam um nó comum, delete 
todos os caminhos que não alcancem o nó comum com o 
custo mínimo;
- Agrupe a lista toda pela soma do tamanho do caminho e 
uma estimativa do limite inferior do custo restante, com os 
caminhos de custo mínimo à frente;
...