Busca Cega (Exaustiva) e Heurística Busca – Aula 2

  • View
    116

  • Download
    0

Embed Size (px)

Text of Busca Cega (Exaustiva) e Heurística Busca – Aula 2

  • Slide 1
  • Busca Cega (Exaustiva) e Heurstica Busca Aula 2
  • Slide 2
  • Ao final desta aula a gente deve saber: Conhecer as vrias estratgias de realizar Busca no-informada (Busca Cega) Determinar que estratgia se aplica melhor ao problema que queremos solucionar Evitar a gerao de estados repetidos. Entender o que Busca Heurstica Saber escolher heursticas apropriadas para o problema.
  • Slide 3
  • Busca Cega (Exaustiva) Estratgias para determinar a ordem de expanso dos ns 1. Busca em largura 2. Busca de custo uniforme 3. Busca em profundidade 4. Busca com aprofundamento iterativo
  • Slide 4
  • Critrios de Avaliao das Estratgias de Busca Completude (completeza): a estratgia sempre encontra uma soluo quando existe alguma? Custo do tempo: quanto tempo gasta para encontrar uma soluo? Custo de memria: quanta memria necessria para realizar a busca? Qualidade/otimalidade (optimality): a estratgia encontra a melhor soluo quando existem solues diferentes? menor custo de caminho
  • Slide 5
  • Busca em Largura Ordem de expanso dos ns: 1. N raiz 2. Todos os ns de profundidade 1 3. Todos os ns de profundidade 2, etc Algoritmo: Busca-em-Largura funo Busca-em-Largura (problema) retorna uma soluo ou falha Busca-Genrica (problema, Insere-no-Fim) Busca-Genrica (problema, Insere-no-Fim)
  • Slide 6
  • Exemplo: Jogo dos 8 nmeros 458 16 732 58 416 732 458 716 32 458 6 732 1 Para cima Para baixo direita 123 46 78 5 Para baixodireita
  • Slide 7
  • Busca em Largura Qualidade Esta estratgia completa tima ? Sempre encontra a soluo mais rasa que nem sempre a soluo de menor custo de caminho, caso os operadores tenham valores diferentes. tima se n,n profundidade(n) profundidade(n) custo de caminho(n) custo de caminho (n). A funo custo de caminho no-decrescente com a profundidade do n. Essa funo acumula o custo do caminho da origem ao n atual. Geralmente, isto s ocorre quando todos os operadores tm o mesmo custo (=1)
  • Slide 8
  • Busca em Largura Custo Fator de expanso da rvore de busca: nmero de ns gerados a partir de cada n (b) Custo de tempo: se o fator de expanso do problema = b, e a primeira soluo para o problema est no nvel d, ento o nmero mximo de ns gerados at se encontrar a soluo = 1 + b + b 2 + b 3 + + b d custo exponencial = O (b d ). Custo de memria: a fronteira do espao de estados deve permanecer na memria um problema mais crucial do que o tempo de execuo da busca
  • Slide 9
  • Busca em Largura Esta estratgia s d bons resultados quando a profundidade da rvore de busca pequena. Exemplo: fator de expanso b = 10 1.000 ns gerados por segundo cada n ocupa 100 bytes
  • Slide 10
  • Busca de Custo Uniforme Modifica a busca em largura: expande o n da fronteira com menor custo de caminho na fronteira do espao de estados cada operador pode ter um custo associado diferente, medido pela funo 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: funo Busca-de-Custo-Uniforme (problema) retorna uma soluo ou falha Busca-Genrica (problema, Insere-Ordem-Crescente)
  • Slide 11
  • Busca de Custo Uniforme
  • Slide 12
  • Busca de Custo Uniforme Fronteira do exemplo anterior F = {S} testa se S o estado objetivo, expande-o e guarda seus filhos A, B e C ordenadamente na fronteira F = {A, B, C} testa A, expande-o e guarda seu filho G A ordenadamente obs.: o algoritmo de gerao e teste guarda na fronteira todos os ns gerados, testando se um n o objetivo apenas quando ele retirado da lista! F= {B, G A, C} testa B, expande-o e guarda seu filho G B ordenadamente F= {G B, G A, C} testa G B e para!
  • Slide 13
  • Busca de Custo Uniforme Esta estratgia completa tima se g (sucessor(n)) g (n) custo de caminho no mesmo caminho no decresce i.e., no tem operadores com custo negativo caso contrrio, teramos que expandir todo o espao de estados em busca da melhor soluo. Ex. Seria necessrio expandir tambm o n C do exemplo, pois o prximo operador poderia ter custo associado = -13, por exemplo, gerando um caminho mais barato do que atravs de B Custo de tempo e de memria teoricamente, igual ao da Busca em Largura
  • Slide 14
  • Busca em Profundidade Ordem de expanso dos ns: sempre expande o n no nvel mais profundo da rvore: 1. n raiz 2. primeiro n de profundidade 1 3. primeiro n de profundidade 2, etc. Quando um n final no soluo, o algoritmo volta para expandir os ns que ainda esto na fronteira do espao de estados Algoritmo: funo Busca-em-Profundidade (problema) retorna uma soluo ou falha Busca-Genrica (problema, Insere-no-Comeo)
  • Slide 15
  • Busca em Profundidade
  • Slide 16
  • Esta estratgia no completa nem tima. Custo de memria: mantm na memria o caminho sendo expandido no momento, e os ns irmos dos ns no caminho (para possibilitar o backtracking) necessita armazenar apenas b.m ns para um espao de estados com fator de expanso b e profundidade m, onde m pode ser maior que d (profundidade da 1a. soluo) Custo de tempo: O(b m ), no pior caso. Observaes: Para problemas com vrias solues, esta estratgia pode ser bem mais rpida do que busca em largura. Esta estratgia deve ser evitada quando as rvores geradas so muito profundas ou geram caminhos infinitos.
  • Slide 17
  • Busca com Aprofundamento Iterativo Evita o problema de caminhos muito longos ou infinitos impondo um limite mximo (l) de profundidade para os caminhos gerados. l d, onde l o limite de profundidade e d a profundidade da primeira soluo do problema
  • Slide 18
  • Busca com Aprofundamento Iterativo Esta estratgia tenta limites com valores crescentes, partindo de zero, at encontrar a primeira soluo fixa profundidade = i, executa busca se no chegou a um objetivo, recomea busca com profundidade = i + n (n qualquer) piora o tempo de busca, porm melhora o custo de memria! Igual Busca em Largura para i=1 e n=1
  • Slide 19
  • Busca com Aprofundamento Iterativo Combina as vantagens de busca em largura com busca em profundidade. tima e completa com n = 1 e operadores com custos iguais Custo de memria: necessita armazenar apenas b.d ns para um espao de estados com fator de expanso b e limite de profundidade d Custo de tempo: O(b d ) Bons resultados quando o espao de estados grande e de profundidade desconhecida.
  • Slide 20
  • Busca com Aprofundamento Iterativo
  • Slide 21
  • Comparando Estratgias de Busca Exaustiva
  • Slide 22
  • Como Evitar Gerao de Estados Repetidos?
  • Slide 23
  • Evitar Gerao de Estados Repetidos Problema geral em Busca expandir estados presentes em caminhos j explorados inevitvel quando existe operadores reversveis ex. encontrar rotas, canibais e missionrios, 8-nmeros, etc. a rvore de busca potencialmente infinita Idia podar (prune) estados repetidos, para gerar apenas a parte da rvore que corresponde ao grafo do espao de estados (que finito!) mesmo quando esta rvore finita, evitar estados repetidos pode reduzir exponencialmente o custo da busca
  • Slide 24
  • Evitar Gerao de Estados Repetidos Exemplo: (m + 1) estados no espao => 2 m caminhos na rvore Questes Como evitar expandir estados presentes em caminhos j explorados? Em ordem crescente de eficcia e custo computacional? Espao de estadosrvore de busca
  • Slide 25
  • Evitando operadores reversveis se os operadores so reversveis: conjunto de predecessores do n = conjunto de sucessores do n porm, esses operadores podem gerar rvores infinitas!
  • Slide 26
  • Como Evitar Estados Repetidos ? Algumas Dicas 1. No retornar ao estado pai funo que rejeita gerao de sucessor igual ao pai 2. No criar caminhos com ciclos no gerar sucessores para qualquer estado que j apareceu no caminho sendo expandido 3. No gerar qualquer estado que j tenha sido criado antes (em qualquer ramo) requer que todos os estados gerados permaneam na memria custo de memria: O(b d ) pode ser implementado mais eficientemente com hash tables
  • Slide 27
  • Conflito (trade-off) Problema: Custo de armazenamento e verificao Soluo depende do problema quanto mais loops, mais vantagem em evit-los! X Custo extra de busca
  • Slide 28
  • A seguir... Busca heurstica
  • Slide 29
  • Estratgias de Busca Exaustiva (Cega) Estratgias de Busca Exaustiva (Cega) Encontram solues para problemas pela gerao sistemtica de novos estados, que so comparados ao objetivo; So ineficientes na maioria dos casos: utilizam apenas o custo de caminho do n atual ao n inicial (funo g) para decidir qual o prximo n da fronteira a ser expandido. essa medida nem sempre conduz a busca na direo do objetivo. Como encontrar um barco perdido? no podemos procurar no oceano inteiro... observamos as correntes martimas, o vento, etc... 29
  • Slide 30
  • Estratgias Busca Heurstica (Informada) Utilizam conhecimento especfico do problema na escolha do prximo n a ser expandido barco perdido correntes martimas, vento, etc... Aplicam de uma funo de avaliao a cada n na fronteira do espao de estados essa funo estima o custo de caminho do n atual at o objetivo mais prximo utilizando uma funo heurstica. Funo heurstica estima o custo do caminho mais barato do estado atual at o estado final mais prximo. 30
  • S