Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4 – Russell & Norvig Seção 4.1 Estratégias de Busca Exaustiva

  • View
    216

  • Download
    1

Embed Size (px)

Text of Busca Heurística Prof. Valmir Macário Filho. 2 Busca com informação e exploração Capítulo 4...

  • Busca HeursticaProf. Valmir Macrio Filho

  • *Busca com informao e exploraoCaptulo 4 Russell & NorvigSeo 4.1Estratgias de Busca Exaustiva (Cega)

  • * Estratgias de Busca Exaustiva (Cega)So ineficientes na maioria dos casos:Utilizam apenas o custo de caminho do n atual ao n inicial para decidir qual o prximo n da fronteira a ser expandido.Essa medida nem sempre conduz a busca na direo do objetivo.

  • Busca com informao (ou heurstica)Utiliza conhecimento especfico sobre o problema para encontrar solues de forma mais eficiente do que a busca cega.Conhecimento especfico alm da definio do problema.

    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.

    *

  • *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 escolhaIdia: usar uma funo de avaliao f(n) para cada n.estimativa do quanto aquele n desejvelExpandir n mais desejvel que ainda no foi expandido

    Implementao:Insere novos ns na fronteira ordenados com base na funo de avaliao f(n)Casos especiais:Busca gulosa pela melhor escolhaBusca A**

  • *BME: Busca GulosaSemelhante busca em profundidade com backtrackingTenta expandir o n mais prximo do n final com base na estimativa feita pela funo heurstica hFuno-Avaliaofuno heurstica h

  • *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 Garannhuns a Recifehdd(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

  • Romnia com custos em km*Distncia em linha reta para Bucareste

  • Exemplo de busca gulosa pela melhor escolha*

  • Exemplo de busca gulosa pela melhor escolha*

  • Exemplo de busca gulosa pela melhor escolha*

  • Exemplo de busca gulosa pela melhor escolha*

  • Busca gulosa pela melhor escolhaNo tima, pois segue o melhor passo considerando somente o estado atual. Pode haver um caminho melhor seguindo algumas opes piores em alguns pontos da rvore de busca.Minimizar h(n) suscetvel a falsos incios.Ex. Ir de Iasi a FagarasHeurstica sugerir ir a Neamt, que um beco sem sada.Se repeties no forem detectadas a busca entrar em loop.*

  • Propriedades da busca gulosa pela melhor escolhaCompleta? No pode ficar presa em loops, ex., Iasi Neamt Iasi NeamtTempo? O(bm) no pior caso, mas uma boa funo heurstica pode levar a uma reduo substancialEspao? O(bm) mantm todos os ns na memriatima? No*

  • *BME: Algoritmo A*A* expande o n de menor valor de f na fronteira do espao de estadosTenta minimizar o custo total da soluo combinando:Busca Gulosa (h)econmica, porm no completa nem timaBusca de Custo Uniforme (g)ineficiente, porm completa e timaf - Funo de avaliao do A*:f (n) = g (n) + h (n)g (n) = distncia de n ao n inicialh (n) = distncia estimada de n ao n final

  • Exemplo de busca A**

  • Exemplo de busca A**

  • Exemplo de busca A**

  • Exemplo de busca A**

  • Exemplo de busca A**

  • Exemplo de busca A**

  • Heurstica AdmissvelUma heurstica h(n) admissvel se para cada n n, h(n) h*(n), onde h*(n) o custo verdadeiro de alcanar o estado objetivo a partir de n.Uma heurstica admissvel nunca superestima o custo de alcanar o objetivo, isto , ela otimista.Exemplo: hDLR(n) (distncia em linha reta nunca maior que distncia pela estrada).Teorema: Se h(n) admissvel, A* usando algoritmo BUSCA-EM-ARVORE tima.*

  • *Algoritmo A*: Anlise do comportamentoCusto 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 memria, para possibilitar o backtracking

  • Propriedades da Busca A*Completa? Sim (a no ser que exista uma quantidade infinita de ns com f f(G) )Tempo? Exponencial no pior casoEspao? Mantm todos os ns na memriatima? SimOtimamente eficienteNenhum outro algoritmo de busca timo tem garantia de expandir um nmero de ns menor que A*. Isso porque qualquer algoritmo que no expande todos os ns com f(n) < C* corre o risco de omitir uma soluo tima.

    *

  • Inventando Funes HeursticasComo escolher uma boa funo heurstica h ?h depende de cada problema particular.h deve ser admissvel i.e., no superestimar o custo real da soluo Existem estratgias genricas para definir h :1) Relaxar restries do problema2) Aprender a heurstica pela experincia Aprendizagem de mquina*

  • Estratgias para definir h (1) Relaxando o problemaProblema Relaxado:verso simplificada do problema original, onde os operadores so menos restritivosExemplo: jogo dos 8 nmeros Operador originalum nmero pode mover-se de A para B se A adjacente a B e B est vaziobusca exaustiva 322 estados possveisOperadores relaxados:1. um nmero pode mover-se de A para B se A adjacente a B (h2)2. um nmero pode mover-se de A para B se B est vazio3. um nmero pode mover-se de A para B (h1)*

  • Estratgias para definir h (1) Relaxando o problema*Heursticas para o jogo dos 8 nmeros h1 = no. de elementos fora do lugar (h1=7)h2 = soma das distncias de cada nmero posio final (h2 = 2+3+3+2+4+2+0+2=18)

  • Estratgias para definir h (1) Relaxando o problemaO custo de uma soluo tima para um problema relaxado sempre uma heurstica admissvel para o problema original.Existem softwares capazes de gerar automaticamente problemas relaxadosSe o problema for definido em uma linguagem formalExistem tambm softwares capazes de gerar automaticamente funes heursticas para problemas relaxados*

  • Escolhendo Funes Heursticas sempre melhor usar uma funo heurstica com valores mais altosi.e., mais prximos do valor real do custo de caminho** contanto que ela seja admissvel ** No exemplo anterior, h2 melhor que h1"n, h2(n) h1(n) A* com h2 expande menos ns do que com h1hi domina hk hi(n) hk(n) "n no espao de estadosh2 domina h1*

  • Escolhendo Funes Heursticas Caso existam muitas funes heursticas para o mesmo problema,e nenhuma delas domine as outras, usa-se uma heurstica composta:h(n) = max (h1(n), h2(n),,hm(n))Assim definida, h admissvel e domina cada funo hi individualmenteExistem software capazes de gerar automaticamente problemas relaxadosSe o problema for definido em uma linguagem formal*

  • Estratgias para definir h (2) Aprendendo a heurstica Definindo h com aprendizagem automtica (1) Criar um corpus de exemplos de treinamentoResolver um conjunto grande de problemase.g., 100 configuraes diferentes do jogo dos 8 nmerosCada soluo tima para um problema prov exemplosCada exemplo consiste em um par (estado no caminho soluo, custo real da soluo a partir daquele ponto)*

  • Estratgias para definir h (2) Aprendendo a heurstica (2) Treinar um algoritmo de aprendizagem indutivaQue ento ser capaz de prever o custo de outros estados gerados durante a execuo do algoritmo de busca*

  • Qualidade da funo heurstica Medida atravs do fator de expanso efetivo (b*)b* o fator de expanso de uma rvore uniforme com N ns e nvel de profundidade dN = 1 + b* + (b*)2 + ... + (b*)d , onde N = total de ns expandidos para uma instncia de problemad = profundidade da soluoMede-se empiricamente a qualidade de h a partir do conjunto de valores experimentais de N e d. uma boa funo heurstica ter o b* muito prximo de 1*

  • Qualidade da funo heursticaObservaes:Se o custo de execuo da funo heurstica for maior do que expandir os ns, ento ela no deve ser usada. uma boa funo heurstica deve ser eficiente e econmica.*