Buscando Soluções Busca Heurística. - ppt carregar
PublicouKauê Sergio Alterado mais de 4 anos atrás
Apresentação em tema: "Buscando Soluções Busca Heurística."— Transcrição da apresentação:
1 Buscando Soluções Busca Heurística
2 Busca Heurística ou Informada
3 Busca Heurística Estratégias de Busca Heurística
4 Funções Heurísticas Função heurística (h) Exemplo:
5 Busca pela Melhor Escolha (BME) Best-First Search
6 Busca Gulosa Semelhante à busca em profundidade com backtracking
Tenta expandir o nó mais próximo do nó final com base na estimativa feita pela função heurística h Algoritmo: função Busca-Gulosa (problema) retorna uma solução ou falha Busca-Melhor-Escolha (problema, h)
7 Exemplo: Ir de Arad a Bucharest
8 Busca Gulosa...
9 Busca Gulosa Custo de busca mínimo! Porém não é ótima: Não é completa:
No exemplo, não expande nós fora do caminho Porém não é ótima: No exemplo escolhe o caminho que é mais econômico à primeira vista, via Fagaras porém, existe um caminho mais curto via Rimnicu Vilcea Não é completa: pode entrar em loop se não detectar a expansão de estados repetidos pode tentar desenvolver um caminho infinito Custo de tempo e memória: O(bd)
10 Algoritmo A* É ainda a técnica de busca mais usada
11 Algoritmo A* Se h é admissível, f (n) nunca irá superestimar o custo real da melhor solução através de n. Algoritmo: função Busca-A* (problema) retorna uma solução ou falha Busca-Melhor-Escolha (problema, g+h)
14 Algoritmo A* : análise do comportamento
15 A* define Contornos . fator de expansão próximo de 1
16 Busca com Limite de Memória Memory Bounded Search
18 Inventando Funções Heurísticas
Como escolher uma boa função heurística h? h depende de cada problema particular. h deve ser admissível não superestimar o custo real da solução Existem estratégias genéricas para definir h: 1) Relaxar restrições do problema; 2) Usar informação estatística; 3) Identificar os atributos mais relevantes do problema
19 (1) Relaxando o problema
20 Heurísticas para jogo 8 números
21 (2) Usando informação estatística
22 (3) Usando atributos/características
23 Qualidade da função heurística
24 Experimento com 100 problemas 8-números
25 Escolhendo Funções Heurísticas
26 Heurística... por toda IA A noção de heurística sempre foi além da busca e de uma formalização via função de um estado Heurística escolha, prioridade, estratégia na busca de uma solução razoável onde não há solução ótima ou recurso para determiná-la No dia a dia: heurística 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 viés de generalização (aprendizagem) ...