Please enable JavaScript.
Coggle requires JavaScript to display documents.
Aula 4 - Busca Cega, Como evitar geração de estados repetidos, Critérios…
Aula 4 - Busca Cega
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!
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
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
pois têm custos com crescimento exponencial de acordo com a quantidade de nós
Só dá bons resultados quando a profundidade da árvore de busca é pequena
Ordem de expansão dos nós
Nó raiz
Todos os nós de profundidade 1
Todos os nós de profundidade 2, etc...
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
ou seja, não tenha operadores com
custo negativo
Custo computacional
Teoricamente os mesmos da busca em largura
Só dá bons resultados quando a profundidade da árvore de busca é pequena
Algoritmo
função BuscaEmLargura (problema) retorna uma solução ou falha
BuscaGenérica (problema, InsereNoFim)
Busca em Profundidade
Ordem de expansão dos nós
nó raiz
primeiro nó de profundidade 1
primeiro nó de profundidade 2, etc
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
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
Observações
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
Algoritmo
função BuscaEmProfundidade (problema) retorna uma solução ou falha
BuscaGenérica (problema, InsereNoInicio)