Estratégia de Busca - Sem informação

Prévia do material em texto

Estratégias de Busca 
sem Informaçãosem Informação
Prof. Pedro Luiz Santos Serra
Introdução
� Busca sem informação (busca cega) ���� estratégias
sem nenhuma informação adicional às apresentadas na
formulação do problema. Geram sucessores e
distinguem um estado objetivo de um estado não-
objetivo.
Busca com informação ���� estratégias que distinguem
Prof. Pedro L. S. Serra 2
� Busca com informação ���� estratégias que distinguem
um estado-não-objetivo “mais promissor” de outro.
Também conhecida como busca heurística.
� Todas as estratégias de busca se distinguem pela
ordem em que os nós são expandidos.
Busca em Extensão
� O nó raiz é expandido primeiro, em seguida todos os
sucessores do nó raiz são expandidos, depois os
sucessores destes nós e assim por diante.
� Pode ser implementada chamando-se BUSCA-EM-
ÁRVORE com uma borda vazia que seja uma fila do tipo
FIFO, assegurando-se que os nós visitados primeiro,
Prof. Pedro L. S. Serra 3
FIFO, assegurando-se que os nós visitados primeiro,
serão expandidos primeiro.
Busca em Extensão
� Completeza: a busca em extensão é completa. Se o nó-
objetivo mais raso estiver em alguma profundidade
finita d, a busca o encontrará após expandir todos os
nós mais rasos (desde que o fator de ramificação b seja
finito).
� Otimização:
Prof. Pedro L. S. Serra 4
� Otimização:
� o nó-objetivo mais raso não é, necessariamente o nó
ótimo.
� A busca em extensão será ótima se o custo do
caminho for uma função não-decrescente da
profundidade
� Ex.: todas ações tem o mesmo custo.
Busca em Extensão
� Complexidade de tempo e espaço:
� Espaço de estados hipotético � Cada estado tem b sucessores.
� Raíz � b nós no primeiro nível;
� Cada nó gera outros b nós no segundo nível, totalizando b2 nós 
no segundo nível;
� Cada um desses nós gera outros b nós no terceiro nível, 
totalizando b3 nós.
Prof. Pedro L. S. Serra 5
totalizando b3 nós.
� Suponha que a solução esteja na profundidade d. O número 
total de nós gerados é:
b + b2 + b3 + ... + bd +( bd+1 – b) = O(bd+1)
� Todo nó gerado deve permanecer na memória �a
complexidade de espaço é igual à complexidade de tempo
(mais um nó para a raiz).
Busca em Extensão
� Ex.: Tempo e Memória para um algoritmo de busca em 
extensão para um fator de ramificação b=10.
Prof. Pedro L. S. Serra 6
Busca de custo uniforme
� Não se importa com o número de passos que um 
caminho tem, mas apenas com seu custo total.
� Pode ficar paralizada em um laço de repetição infinito se 
um nó que tenha ação de custo zero levando de volta ao 
mesmo estado.
� Completeza: O algorítmo é completo uma vez que o 
Prof. Pedro L. S. Serra 7
� Completeza: O algorítmo é completo uma vez que o 
custo de cada passo seja maior ou igual a alguma 
constante positiva e pequena ε.
� Otimização: O ítem anterior garante que o algoritmo é 
ótimo. 
Busca em Profundidade
Prof. Pedro L. S. Serra 8
Busca em Profundidade
� Pode ser implementada por BUSCA-EM-ÁRVORE com 
uma lista LIFO (Pilha).
� Requisitos de memória modestos ���� Necessário 
armazenar um único caminho da raiz até um nó de 
folha (juntamente com os nós irmãos não expandidos 
restantes de cada nó no caminho).
Prof. Pedro L. S. Serra 9
restantes de cada nó no caminho).
� Uma vez expandido, um nó pode ser removido, uma 
vez que todos os seus descendentes foram explorados.
� Exige apenas o armazenamento de b.m+1 nós.
b � fator de ramificação
m � profundidade máxima.
Busca em Profundidade Limitada
� Trata-se de uma variação do modelo de busca em 
profundidade com o estabelecimento de um limite de 
profundidade predeterminado l.
� Visa a solução do problema de caminhos infinitos na 
busca em profundidade, no entanto também introduz 
uma fonte adicional de incompleteza se escolhermos 
Prof. Pedro L. S. Serra 10
uma fonte adicional de incompleteza se escolhermos 
l < d.
� Nós da profundidade l são tratados como se não 
tivessem sucessores.
� Complexidade de tempo: O(bl).
� Complexidade de espaço: O(bl)
Busca em Profundidade Limitada
Prof. Pedro L. S. Serra 11
Busca em Profundidade Limitada
� A busca em profundidade limitada pode se basear no 
conhecimento que se tem do problema. Por exemplo: 
� No mapa da Romênia há 20 cidades. Portanto, sabe-se 
que existe uma solução e deve ter o comprimento 19 no 
caso mais longo � l=19 é uma escolha possível.
� No entanto sabemos (através de um prévio estudo do 
Prof. Pedro L. S. Serra 12
� No entanto sabemos (através de um prévio estudo do 
mapa) que qualquer cidade pode ser alcançada a partir de 
qualquer outra cidade em no máximo 9 passos. Esse 
número é conhecido por diâmetro e a partir dele pode-se 
estabelecer um limite melhor de profundidade 
proporcionando maior eficiência do algorítmo.
Busca em Aprofundamento iterativo
� Também conhecido por busca em profundidade por 
aprofundamento iterativo ou busca em profundidade 
iterativa;
� Combina os benefícios da busca em profundidade e da 
busca em extensão.
Prof. Pedro L. S. Serra 13
Busca em Aprofundamento iterativo
Prof. Pedro L. S. Serra 14
Busca em Aprofundamento Iterativo
� Tem como principais características:
� O aumento gradual do limite – primeiro 0 – depois 1 –
depois 2 – e assim por diante até encontrar um objetivo;
� O objetivo ocorrerá quando o limite de profundidade “d” for 
alcançado (a profundidade do nó objetivo mais raso);
� O algoritmo é completo quando o número de ramificações for 
finito;
Prof. Pedro L. S. Serra 15
finito;
� O algoritmo é ótimo quando o custo de caminho é uma 
função não decrescente da profundidade do nó;
� Embora pareça um desperdício pela geração do estado 
várias vezes, o custo deste recurso não é muito alto, pois, os 
nós no nível inferior (profundidade d) são gerados uma vez. 
Os nós do penúltimo nível, duas e assim por diante até os 
filhos da raiz, que são gerados d vezes.
Busca em Aprofundamento Iterativo
� O número total de nós gerados é:
N(BAI) = (d).b + (d-1)b2 + ... + (1).bd���� O(bd)
� Na busca em extensão, o número de nós gerados é:
N(BE) = b + b2 + b3 + ... + (bd+1 – b)
� Na extensão são gerados alguns nós na profundidade 
Prof. Pedro L. S. Serra 16
� Na extensão são gerados alguns nós na profundidade 
b+1, enquanto que no aprofundamento iterativo não.
� Exemplo: para b=10 e d=5, tem-se:
N(BAI) = 50 + 400 + 3000 + 20000 + 100000 = 125450
N(BE) = 10 + 100 + 1000 + 10000 + 100000 + 999990 = 1111100
Comparação entre as estratégias de busca
Prof. Pedro L. S. Serra 17