Sistemas Inteligentes Busca Cega (Exaustiva). Busca Cega (Exaustiva) Estratégias para determinar a ordem de expansão dos nós 1. Busca em largura 2. Busca

  • View
    214

  • Download
    1

Embed Size (px)

Text of Sistemas Inteligentes Busca Cega (Exaustiva). Busca Cega (Exaustiva) Estratégias para determinar a...

  • Sistemas InteligentesBusca Cega (Exaustiva)

  • Busca Cega (Exaustiva)Estratgias para determinar a ordem de expanso dos ns1. Busca em largura2. Busca de custo uniforme3. Busca em profundidade4. Busca com aprofundamento iterativoComo evitar gerao de Estados Repetidos

  • Critrios de Avaliao das Estratgias de BuscaCompletude (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

  • Busca em LarguraOrdem de expanso dos ns:1. N raiz2. Todos os ns de profundidade 13. Todos os ns de profundidade 2, etcAlgoritmo:funo Busca-em-Largura (problema) retorna uma soluo ou falha Busca-Genrica (problema, Insere-no-Fim)

  • Exemplo: Jogo dos 8 nmeros

  • Busca em LarguraQualidadeEsta 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 sen,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.Isto ocorre usualmente quando todos os operadores tm o mesmo custo (=1)

  • Busca em LarguraCustoFator 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 + b2 + b3 + + bd custo exponencial = O (bd). Custo de memria:a fronteira do espao de estados deve permanecer na memria um problema to crucial quanto o tempo de execuo da busca

  • Busca em LarguraEsta estratgia s d bons resultados quando a profundidade da rvore de busca pequena.Exemplo:fator de expanso b = 101.000 ns gerados por segundocada n ocupa 100 bytes

    Profundidade

    Ns

    Tempo

    Memria

    0

    1

    1 milissegundo

    100 bytes

    2

    111

    0.1 segundo

    11 quilobytes

    4

    11111

    11 segundos

    1 megabytes

    6

    106

    18 minutos

    111 megabytes

    8

    108

    31 horas

    11 gigabytes

    10

    1010

    128 dias

    1 terabyte

    12

    1012

    35 anos

    111 terabytes

    14

    1014

    3500 anos

    11111 terabytes

  • Busca de Custo UniformeModifica a busca em largura: expande o n da fronteira com menor custo de caminho na fronteira do espao de estadoscada 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 nNa 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)

  • Busca de Custo Uniforme

  • Busca de Custo UniformeFronteira do exemplo anteriorF = {S}testa se S o estado objetivo, expande-o e guarda seus filhos A, B e C ordenadamente na fronteiraF = {A, B, C}testa A, expande-o e guarda seu filho GA ordenadamenteobs.: 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, GA, C}testa B, expande-o e guarda seu filho GB ordenadamenteF= {GB, GA, C}testa GB e para!

  • Busca de Custo UniformeEsta estratgia completa

    tima seg (sucessor(n)) g (n) custo de caminho no mesmo caminho no decrescei.e., no tem operadores com custo negativocaso contrrio, teramos que expandir todo o espao de estados em busca da melhor soluoObs.: necessrio continuar a busca at que todos os caminhos tenham custo maior que a soluo j encontrada anteriormente

    Custo de tempo e de memriateoricamente, igual ao da Busca em Largura

  • Busca em ProfundidadeOrdem de expanso dos ns:sempre expande o n no nvel mais profundo da rvore:1. n raiz2. primeiro n de profundidade 13. 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 estadosAlgoritmo:funo Busca-em-Profundidade (problema) retorna uma soluo ou falha Busca-Genrica (problema, Insere-no-Comeo)

  • Busca em Profundidade

  • Busca em ProfundidadeEsta 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(bm), 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.

  • Busca com Aprofundamento IterativoEvita o problema de caminhos muito longos ou infinitos impondo um limite mximo (l) de profundidade para os caminhos gerados.

  • Busca com Aprofundamento Iterativo Esta estratgia tenta limites com valores crescentes, partindo de zero, at encontrar a primeira soluofixa profundidade = i, executa busca se no chegou a um objetivo, retoma a busca com profundidade = i + n (n qualquer)

    Igual Busca em Largura para i=1 e n=1

  • Busca com Aprofundamento IterativoCombina as vantagens de busca em largura com busca em profundidade. tima e completacom n = 1 e operadores com custos iguaisCusto de memria:necessita armazenar apenas b.d ns para um espao de estados com fator de expanso b e limite de profundidade dCusto de tempo:O(bd)Bons resultados quando o espao de estados grande e de profundidade desconhecida.

  • Busca com Aprofundamento Iterativo

  • Comparando Estratgias de Busca Exaustiva

    Critrio

    Largura

    Custo Uniforme

    Profun-didade

    Aprofun-damento Iterativo

    Tempo

    bd

    bd

    bm

    bd

    Espao

    bd

    bd

    bm

    bd

    Otima?

    Sim

    Sim*

    No

    Sim

    Completa?

    Sim

    Sim

    No

    Sim

  • Busca BidirecionalBusca em duas direes:para frente, a partir do n inicial, e para trs, a partir do n final (objetivo)A busca pra quando os dois processos geram um mesmo estado intermedirio. possvel utilizar estratgias diferentes em cada direo da busca.

  • Busca BidirecionalCusto de tempo:Se fator de expanso b nas duas direes, e a profundidade do ltimo n gerado d: O(2bd/2) = O(bd/2)Custo de memria: O(bd/2)

    Problemas:Podem gerar rvores infinitas!Limitaes srias quando existem muitos estados finais (objetivos) no problema.

  • Como Evitar Gerao de Estados Repetidos?

  • Evitar Gerao de Estados RepetidosProblema geral em Buscaexpandir 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

  • Como Evitar Estados Repetidos ? Algumas Dicas1. No retornar ao estado paifuno que rejeita gerao de sucessor igual ao pai2. No criar caminhos com ciclosno gerar sucessores para qualquer estado que j apareceu no caminho sendo expandido3. No gerar qualquer estado que j tenha sido criado antes (em qualquer ramo)requer que todos os estados gerados permaneam na memriacusto de memria: O(bd) pode ser implementado mais eficientemente com hash tables

  • Conflito (trade-off)Problema:Custo de armazenamento e verificao Soluodepende do problemaquanto mais loops, mais vantagem em evit-los!X Custo extra de busca

  • A seguir... Busca heurstica