Introdução aos Agentes Inteligentes Busca Cega (Exaustiva) Flávia Barros

  • View
    105

  • Download
    1

Embed Size (px)

Text of Introdução aos Agentes Inteligentes Busca Cega (Exaustiva) Flávia Barros

  • Slide 1
  • Introduo aos Agentes Inteligentes Busca Cega (Exaustiva) Flvia Barros
  • Slide 2
  • Busca Cega (Exaustiva) Estratgias para determinar a ordem de expanso dos ns 1. Busca em largura 2. Busca de custo uniforma 3. Busca em profundidade 4. Busca com aprofundamento iterativo Como evitar gerao de Estados Repetidos
  • Slide 3
  • 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 4
  • 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 5
  • Exemplo: Jogo dos 8 nmeros 458 16 732 58 416 732 458 716 32 458 6 732 1 up down right 123 46 78 5 downright
  • Slide 6
  • 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 7
  • 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 8
  • 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 9
  • 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 10
  • Busca de Custo Uniforme
  • Slide 11
  • 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 12
  • 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 13
  • 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 14
  • Busca em Profundidade
  • Slide 15
  • 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 16
  • 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 17
  • 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 18
  • Busca com Aprofundamento Iterativo Combina as vantagens de busca em largura com busca em profundidade. Esta estratgia completa tima para 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 ) Tem bons resultados quando o espao de estados grande e de profundidade desconhecida.
  • Slide 19
  • Busca com Aprofundamento Iterativo
  • Slide 20
  • Comparando Estratgias de Busca Exaustiva
  • Slide 21
  • Como Evitar Gerao de Estados Repetidos?
  • Slide 22
  • Evitar Gerao de Estados Repetidos Problema geral em Busca expandir estados presentes em caminhos j explorados inevitvel quando existe operadores reversveis conjunto de predecessores do n = conjunto de sucessores do n ex. encontrar rotas, canibais e missionrios, 8-nmeros, etc. Problema: esses operadores podem gerar rvores infinitas! Temos problemas tambm quando existem muitos estados finais (objetivos) espalhados pela rvore de busca.
  • Slide 23
  • Evitar Gerao de Estados Repetidos 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
  • 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 26
  • 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 27
  • A seguir... Busca heurstica