1 Buscando Soluções Busca Heurística. 2 Busca Heurística ou Informada Estratégias de Busca Cega encontram soluções para problemas pela geração sistemática

  • View
    102

  • Download
    0

Embed Size (px)

Text of 1 Buscando Soluções Busca Heurística. 2 Busca Heurística ou Informada Estratégias de Busca Cega...

  • Slide 1
  • 1 Buscando Solues Busca Heurstica
  • Slide 2
  • 2 Busca Heurstica ou Informada Estratgias de Busca Cega encontram solues para problemas pela gerao sistemtica de novos estados, que so comparados ao objetivo; so ineficientes na maioria dos casos: so capazes de calcular 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 no necessariamente conduz a busca na direo do objetivo. Como encontrar um barco perdido? no podemos procurar no oceano inteiro...
  • Slide 3
  • 3 Busca Heurstica Estratgias de Busca Heurstica utilizam conhecimento especfico do problema na escolha do prximo n a ser expandido barco perdido correntes martimas, vento, etc... Aplica 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 Heurstica do grego heuriskein, encontrar, descobrir introduzida em IA por George Polya em 1957 (livro How to Solve It) conhecimento e, por isso, marcou quebra da IA com a pesquisa operacional
  • Slide 4
  • 4 Funes Heursticas Funo heurstica (h) estima o custo do caminho mais barato do estado atual at o estado final mais prximo. so especficas para cada problema Exemplo: encontrar a rota mais curta entre duas cidades h dd (n) = distncia direta entre o n n e o n final. Como escolher uma boa funo heurstica? ela deve ser admissvel, i.e., nunca superestimar o custo real da soluo ex. distncia direta (h dd ) admissvel porque o caminho mais curto entre dois pontos sempre uma linha reta
  • Slide 5
  • 5 Busca pela Melhor Escolha (BME) Best-First Search Busca genrica onde o n de menor custo aparente na fronteira do espao de estados expandido primeiro Duas abordagens bsicas: 1. Busca Gulosa (Greedy search) 2. Algoritmo A* e suas variantes Algoritmo: Funo-InsereFuno-Avaliao Funo-Insere - ordena ns com base na Funo-Avaliao Busca-Melhor-EscolhaFuno-Avaliao funo Busca-Melhor-Escolha (problema,Funo-Avaliao) retorna uma soluo Busca-GenricaFuno-Insere Busca-Genrica (problema, Funo-Insere)
  • Slide 6
  • 6 Busca Gulosa Semelhante busca em profundidade com backtracking Tenta expandir o n mais prximo do n final com base na estimativa feita pela funo heurstica h Algoritmo: Busca-Gulosa funo Busca-Gulosa (problema) retorna uma soluo ou falha Busca-Melhor-Escolha Busca-Melhor-Escolha (problema, h)
  • Slide 7
  • Exemplo: Ir de Arad a Bucharest
  • Slide 8
  • Busca Gulosa...
  • Slide 9
  • 9 Busca Gulosa Custo de busca mnimo! No exemplo, no expande ns fora do caminho Porm no tima: No exemplo escolhe o caminho que mais econmico primeira vista, via Fagaras porm, existe um caminho mais curto via Rimnicu Vilcea No completa: pode entrar em loop se no detectar a expanso de estados repetidos pode tentar desenvolver um caminho infinito Custo de tempo e memria: O(b d )
  • Slide 10
  • 10 Algoritmo A* ainda a tcnica de busca mais usada Tenta minimizar o custo total da soluo combinando: Busca Gulosa: econmica, porm no completa nem tima Busca de Custo Uniforme (Djikstra): ineficiente, porm completa e tima Funo de avaliao: f (n) = g (n) + h (n) g (n) = distncia de n ao n inicial h (n) = distncia estimada de n ao n final A* expande o n de menor valor de f na fronteira do espao de estados.
  • Slide 11
  • 11 Algoritmo A* Se h admissvel, f (n) nunca ir superestimar o custo real da melhor soluo atravs de n. Algoritmo: Busca-A* funo Busca-A* (problema) retorna uma soluo ou falha Busca-Melhor-Escolha Busca-Melhor-Escolha (problema, g+h)
  • Slide 12
  • 12 Algoritmo A* : exemplo Ir de Arad a Bucharest
  • Slide 13
  • Usando A*
  • Slide 14
  • 14 Algoritmo A* : anlise do comportamento A estratgia completa e tima Custo de tempo: exponencial com o comprimento da soluo, porm boas funes heursticas diminuem significativamente esse custo o fator de expanso fica prximo de 1 Custo memria: O (b d ) guarda todos os ns expandidos na memria para possibilitar o backtracking Eficincia tima s expande ns com f(n) f*, onde f* o custo do caminho timo f no decrescente nenhum outro algoritmo timo garante expandir menos ns
  • Slide 15
  • 15 A* define Contornos. fator de expanso prximo de 1
  • Slide 16
  • 16 Busca com Limite de Memria Memory Bounded Search IDA* (Iterative Deepening A*) igual ao aprofundamento iterativo, porm seu limite dado pela funo de avaliao (f) (contornos), e no pela profundidade (d). necessita de menos memria do que A* mas continua tima SMA* (Simplified Memory-Bounded A*) O nmero de ns guardados em memria fixado previamente conforme vai avanando, descarta os piores ns (embora guarde informaes a respeito deles) e atualiza os melhores valores dos caminhos completa e tima se a memria alocada for suficiente
  • Slide 17
  • 17 SMA* (Simplified Memory-Bounded A*)
  • Slide 18
  • 18 Inventando Funes Heursticas Como escolher uma boa funo heurstica h? h depende de cada problema particular. h deve ser admissvel no superestimar o custo real da soluo Existem estratgias genricas para definir h: 1) Relaxar restries do problema; 2) Usar informao estatstica; 3) Identificar os atributos mais relevantes do problema
  • Slide 19
  • 19 Problema Relaxado: verso simplificada do problema original, onde os operadores so menos restritivos Exemplo: jogo dos 8 nmeros: operador original: um nmero pode mover-se de A para B se A adjacente a B e B est vazio busca exaustiva 3 20 estados possveis Fator de ramificao 3 e d 20 passos Operadores relaxados: 1. um nmero pode mover-se de A para B (h1) 2. um nmero pode mover-se de A para B se A adjacente a B (h2) 458 16 732 (1) Relaxando o problema
  • Slide 20
  • 20 Heursticas possveis 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) Manhattan Distance d de dois pontos (x,y) e (u,v), d = |x-u| + |y-v| Heursticas para jogo 8 nmeros
  • Slide 21
  • 21 (2) Usando informao estatstica Funes heursticas podem ser melhoradas com informao estatstica: executar a busca com um conjunto de treinamento (e.g., 100 configuraes diferentes do jogo), e computar os resultados. se, em 90% dos casos, quando h (n) = 14, a distncia real da soluo 18, ento, quando o algoritmo encontrar 14 para o resultado da funo, vai substituir esse valor por 18. Informao estatstica expande menos ns, porm elimina admissibilidade: em 10% dos casos do problema acima, a funo de avaliao poder superestimar o custo da soluo, no sendo de grande auxlio para o algoritmo encontrar a soluo mais barata.
  • Slide 22
  • 22 (3) Usando atributos/caractersticas Caractersticas do problema podem ser usadas para mensurar o quo se est prximo da soluo ex. xadrez nmero de peas de cada lado somatrio dos pesos das peas de cada lado (Peo-1,..., Rainha-9) nmero de peas sob ataque Quando no se conhece a importncia das caractersticas, pode-se aprend-las (w 1 f 1 +w 2 f 2 +...+w n f n )
  • Slide 23
  • 23 Qualidade da funo heurstica 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 d N = 1 + b* + (b*) 2 +... + (b*) d, onde N = total de ns expandidos para uma instncia de problema d = profundidade da soluo; Mede-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. Se o custo de execuo da funo heurstica for maior do que expandir ns, ento ela no deve ser usada. uma boa funo heurstica deve ser eficiente
  • Slide 24
  • Experimento com 100 problemas 8-nmeros Uma boa funo heurstica ter o b* muito prximo de 1.
  • Slide 25
  • 25 Escolhendo Funes Heursticas sempre melhor usar uma funo heurstica com valores mais altos, contanto que ela seja admissvel. ex. h2 melhor que h1 h i domina h k h i (n) h k (n) n no espao de estados h 2 domina h 1 no exemplo anterior Caso existam muitas funes heursticas para o mesmo problema, e nenhuma delas domine as outras, usa-se uma heurstica composta: h (n) = max (h 1 (n), h 2 (n),,h m (n)) Assim definida, h admissvel e domina cada funo h i individualmente
  • Slide 26
  • 26 Heurstica... por toda IA A noo de heurstica sempre foi alm da busca e de uma formalizao via funo de um estado Heurstica escolha, prioridade, estratgia na busca de uma soluo razovel onde no h soluo tima ou recurso para determin- la No dia a dia: heurstica para dirigir, namorar, estudar,... Em IA: em todas as reas como conhecimento de controle ex. escolha de regras a serem disparadas (SBC) ex. escolha de vis de generalizao (aprendizagem)...
  • Slide 27
  • 27 Qual seria uma boa heurstica para o jogo da velha? X 0