Critérios de avaliação das Estratégias de Busca
Completude
a estratégia sempre encontra uma solução quando existe alguma?
Qualidade (optimality)
a estratégia encontra a melhor solução quando existem diferentes soluções?
ex: solução de menor custo de caminho
Custo do tempo
quanto tempo gasta para encontrar a 1ª solução?
Custo de memória
quanta memória é necessária para realizar a busca?
Busca em Largura
Ordem de expansão dos nós
- Nó raiz
- Todos os nós de profundidade 1
- Todos os nós de profundidade 2, etc...
Algoritmo
função BuscaEmLargura (problema) retorna uma solução ou falha
BuscaGenérica (problema, InsereNoFim)
Como essa estratégia é avaliada?
É completa
Não vai entrar em loop e se perder
Sempre encontra uma solução quando ela existe
É ótima?
Nem sempre
Sempre encontra a solução mais "rasa"
que nem sempre é a solução de menor caminho
É ótima quando os operadores têm o mesmo custo
Custo computacional
Custo de tempo e de memória
Métricas que atualmente têm pouca importância para tratar problemas mais simples
Visto o poder computacional disponível
Todavia, principalmente considerando mémoria (problema mais crucial)
é uma estratégia computacionalmente cara
Só dá bons resultados quando a profundidade da árvore de busca é pequena
Busca de Custo Uniforme
O que faz
Modifica a busca em largura
Expande o nó da fronteira com menor custo de caminho na fronteira do espaço de estados
Cada operador pode ter um custo associado diferente
medido pela função g(n) para o nó n
onde g(n) dá o custo do caminho da origem ao nó n
na busca em largura, g(n) = profundidade(n)
Algoritmo
BuscaGenérica (problema, InsereEmOrdemCrescente)
Como essa estratégia é avaliada?
É completa
Não vai entrar em loop e se perder
Sempre encontra uma solução quando ela existe
É ótima?
Nem sempre
É ótima contanto que
o custo de caminho no mesmo caminho não decresça
Custo computacional
Teoricamente os mesmos da busca em largura
Só dá bons resultados quando a profundidade da árvore de busca é pequena
ou seja, não tenha operadores com custo negativo
pois têm custos com crescimento exponencial de acordo com a quantidade de nós
Busca em Profundidade
Ordem de expansão dos nós
- nó raiz
- primeiro nó de profundidade 1
- primeiro nó de profundidade 2, etc
Algoritmo
função BuscaEmProfundidade (problema) retorna uma solução ou falha
BuscaGenérica (problema, InsereNoInicio)
Como essa estratégia é avaliada?
Não é completa nem é ótima
Pode entrar em loop e se perder
Pode retornar solução em profundidade maior na árvore de busca do que a mais rasa viável
Custo computacional
Observações
Custo de memória
Melhor (menor) que a da busca em largura
Armazena menos nós
Custo de tempo
Melhor que o da busca em largura
Apesar disso, ainda é relativamente alto
Para problemas com várias soluções, esta estratégia pode ser bem mais rápida do que a busca em largura
Deve ser evitada quando as árvores geradas são muito profundas ou geram caminhos infinitos
Busca com aprofundamento iterativo
O que faz
Evita o problema de caminhos muito longos
pois impõe um limite máximo (l) de profundidade para os caminhos gerados
Tenta limites com valores crescentes
parte de 0
até encontrar solução
se não chegou a um objetivo, recomeça a busca aumentando o limite de profundidade
Piora o tempo de busca
Mas melhora o custo de memória
Combina as vantagens de busca em largura com busca em profundidade
Como essa estratégia é avaliada?
É completa
Não pode entrar em loop
Pode retornar solução em profundidade maior na árvore de busca do que a mais rasa viável
É ótima?
Nem sempre
É ótima quando os operadores têm o mesmo custo
Custo computacional
Custo de memória
Melhor (menor) que a da busca em largura
Custo de tempo
Ainda é relativamente alto (continua sendo exponencial)
Observações
Tem bons resultados quando
espaço de estados é grande
e de profundidade desconhecida
Como evitar geração de estados repetidos
Problema geral em busca
expandir estados presentes em caminhos já explorados
Inevitável quando existem operadores reversíveis
quando, a partir de uma operação, você pode retornar ao estado anterior
exemplos
Olinda-Recife; Recife-Olinda
Atravessar missionário-Voltar missionário
Ideia
podar (prune) estados repetidos
evitar estados repetidos pode reduzir exponencialmente o custo da busca
Dicas (passo a passo)
- Não retornar ao estado pai
Função que rejeita geração de sucessor igual ao pai
- Não criar caminhos com ciclos
Não gerar sucessores para qualquer estado que já apareceu no caminho
É viável se guardarmos na estrutura "nó" todos os nós do caminho sendo percorrido
- Não gerar qualquer estado que já tenha sido criado antes em qualquer ramo da árvore
Requer que todos os estados gerados permaneçam na memória
O que causa alto custo de memória
Pode ser implementado mais eficientemente usando hash tables
Conflito (trade-off)
Problema
Custo de armazenamento X Custo extra de busca e verificação
Solução
depende do problema
quanto mais "loops", mais vantagem em evitá-los!