1 Busca Heurística - Informada Estratégias de Busca Exaustiva (Cega) encontram soluções para problemas pela geração sistemática de novos estados, que são

  • View
    214

  • Download
    1

Embed Size (px)

Text of 1 Busca Heurística - Informada Estratégias de Busca Exaustiva (Cega) encontram soluções para...

  • Busca Heurstica - Informada 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...

  • Busca Heurstica - Informada Estratgias de Busca Heursticautilizam conhecimento especfico do problema na escolha do prximo n a ser expandidobarco perdidocorrentes martimas, vento, etc... Aplica de uma funo de avaliao a cada n na fronteira do espao de estadosessa funo estima o custo de caminho do n atual at o objetivo mais prximo utilizando uma funo heurstica.

  • Funes Heursticas Funo heurstica - h estima o custo do caminho mais barato do estado atual at o estado final mais prximo. Funes heursticas so especficas para cada problema Exemplo: encontrar a rota mais barata de Jeremoabo a Cajazeirashdd(n) = distncia direta entre o n n e o n final.

  • Funes HeursticasComo escolher uma boa funo heurstica?ela deve ser admissveli.e., nunca superestimar o custo real da soluoDistncia direta (hdd) admissvel porque o caminho mais curto entre dois pontos sempre uma linha reta Veremos mais sobre isso na prxima aula

  • Busca Heurstica Classes de algoritmos para busca heurstica:1. Busca pela melhor escolha (Best-First search)2. Busca com limite de memria3. Busca com melhora iterativa

  • Busca pela Melhor Escolha (BME) Best-First SearchBusca genrica onde o n de menor custo aparente na fronteira do espao de estados expandido primeiroDuas abordagens bsicas:1. Busca Gulosa (Greedy search) 2. Algoritmo A*Algoritmo:Funo-Insere - ordena ns com base na Funo-Avaliao funo Busca-Melhor-Escolha (problema,Funo-Avaliao) retorna uma soluo Busca-Genrica (problema, Funo-Insere)

  • BME: Busca GulosaSemelhante busca em profundidade com backtrackingTenta expandir o n mais prximo do n final com base na estimativa feita pela funo heurstica hAlgoritmo: funo Busca-Gulosa (problema) retorna uma soluo ou falha Busca-Melhor-Escolha (problema, h)Exemplo: encontrar a rota mais barata de Canudos a Petrolndia hdd(n) = distncia direta entre o n n e o n finalhdd admissvel!

  • Busca Gulosa

  • Busca GulosaCusto de busca mnimo!no expande ns fora do caminho

    Porm no tima:escolhe o caminho que mais econmico primeira vistaBelm do S. Francisco, Petrolndia = 4,4 unidadesporm, existe um caminho mais curto de Canudos a PetrolndiaJeremoabo, P. Afonso, Petrolndia = 4 unidades

    A soluo via Belm do S. Francisco foi escolhida por este algoritmo porque hdd(BSF) = 1,5 u., enquanto hdd(Jer) = 2,1 u.

  • Busca GulosaNo completa:pode entrar em looping se no detectar a expanso de estados repetidospode tentar desenvolver um caminho infinito

    Custo de tempo e memria: O(bd)guarda todos os ns expandidos na memria

  • BME: Algoritmo A*Tenta minimizar o custo total da soluo combinando:Busca Gulosaeconmica, porm no completa nem timaBusca de Custo Uniformeineficiente, porm completa e timaFuno de avaliao:f (n) = g (n) + h (n)g (n) = distncia de n ao n inicialh (n) = distncia estimada de n ao n finalA* expande o n de menor valor de f na fronteira do espao de estados

  • Algoritmo A*Se h admissvel, f (n) nunca ir superestimar o custo real da melhor soluo atravs de n.Neste caso, a rota escolhida entre Canudos e Petrolndia de fato a mais curta, uma vez que:f (BSF) = 2,5 u + 1,5 u = 4 uf (Jeremoabo) = 1,5 u + 2,1 u = 3,6 uAlgoritmo: funo Busca-A* (problema) retorna uma soluo ou falha Busca-Melhor-Escolha (problema, g+h)

  • Algoritmo A*: exemploIr de Arad a Bucharest

  • Se fosse pela Busca Gulosa...

  • Usando A*

  • Algoritmo A*: funo de avaliaoA funo heurstica h monotnica seh (n) h (sucessor(n))isso vale para a maioria das funes heursticasTransferindo-se esse comportamento para a funo de avaliao f =g+h, temos quef (sucessor(n)) f(n)uma vez que g no decrescenteEm outras palavraso custo de cada n gerado no mesmo caminho nunca diminuiQuando h no monotnica, para se garantir a monotonicidade de f, temos:quando f(suc(n)) < f (n) usa-se f(suc(n)) = max ( f(n), g(suc(n)) + h(suc(n)) )

  • Algoritmo A*: anlise do comportamentoA estratgia completa e timaCusto de tempo:exponencial com o comprimento da soluo, porm boas funes heursticas diminuem significativamente esse custoo fator de expanso fica prximo de 1Custo memria: O (bd) guarda todos os ns expandidos na memriapara possibilitar o backtrackingEficincia timas expande ns com f(n) f*, onde f* o custo do caminho timof no decrescentenenhum outro algoritmo timo garante expandir menos ns

  • A* define Contornos. f(n) f* (f admissvel) fator de expanso prximo de 1

  • Busca com Limite de Memria Memory Bounded SearchIDA* (Iterative Deepening A*)igual ao aprofundamento iterativo, porm seu limite dado pela funo de avaliao (f) , e no pela profundidade (d).necessita de menos memria do que A*

    SMA* (Simplified Memory-Bounded A*) O nmero de ns guardados em memria fixado previamente

  • IDA* - Iterative Deepening A*

  • SMA* - Simplified Memory-Bounded A*