Busca Cega (Exaustiva) e Heurística - ppt carregar
Busca Cega (Exaustiva) e Heurística
PublicouNicholas Vila Alterado mais de 3 anos atrás
Apresentação em tema: "Busca Cega (Exaustiva) e Heurística"— Transcrição da apresentação:
1 Busca Cega (Exaustiva) e Heurística
Busca – Aula 2
2 Ao final desta aula a gente deve saber:
Conhecer as várias estratégias de realizar Busca não-informada (Busca Cega) Determinar que estratégia se aplica melhor ao problema que queremos solucionar Evitar a geração de estados repetidos. Entender o que é Busca Heurística Saber escolher heurísticas apropriadas para o problema.
3 Busca Cega (Exaustiva)
Estratégias para determinar a ordem de expansão dos nós 1. Busca em largura 2. Busca de custo uniforme 3. Busca em profundidade 4. Busca com aprofundamento iterativo
4 Critérios de Avaliação das Estratégias de Busca
Completude (completeza): a estratégia sempre encontra uma solução quando existe alguma? Custo do tempo: quanto tempo gasta para encontrar uma solução? Custo de memória: quanta memória é necessária para realizar a busca? Qualidade/otimalidade (optimality): a estratégia encontra a melhor solução quando existem soluções diferentes? menor custo de caminho
5 Busca em Largura Busca-Genérica (problema, Insere-no-Fim)
Ordem de expansão dos nós: 1. Nó raiz 2. Todos os nós de profundidade 1 3. Todos os nós de profundidade 2, etc… Algoritmo: função Busca-em-Largura (problema) retorna uma solução ou falha Busca-Genérica (problema, Insere-no-Fim)
6 Exemplo: Jogo dos 8 números
4 5 8 1 6 7 3 2 Para cima Para baixo direita
7 Busca em Largura Qualidade
Esta estratégia é completa É ótima ? Sempre encontra a solução mais "rasa" ® que nem sempre é a solução de menor custo de caminho, caso os operadores tenham valores diferentes. É ótima se n,n' profundidade(n')  profundidade(n)  custo de caminho(n')  custo de caminho (n). A função custo de caminho é não-decrescente com a profundidade do nó. Essa função acumula o custo do caminho da origem ao nó atual. Geralmente, isto só ocorre quando todos os operadores têm o mesmo custo (=1)
8 Busca em Largura Custo Fator de expansão da árvore de busca:
número de nós gerados a partir de cada nó (b) Custo de tempo: se o fator de expansão do problema = b, e a primeira solução para o problema está no nível d, então o número máximo de nós gerados até se encontrar a solução = 1 + b + b2 + b3 + … + bd custo exponencial = O (bd). Custo de memória: a fronteira do espaço de estados deve permanecer na memória é um problema mais crucial do que o tempo de execução da busca
9 Busca em Largura Esta estratégia só dá bons resultados quando a profundidade da árvore de busca é pequena. Exemplo: fator de expansão b = 10 1.000 nós gerados por segundo cada nó ocupa 100 bytes
Modifica a busca em largura: expande o nó da fronteira com menor custo de caminho na fronteira do espaço de estados cada operador pode ter um custo associado diferente, medido pela função g(n), para o nó n. onde g(n) dá o custo do caminho da origem ao nó n Na busca em largura: g(n) = profundidade (n) Algoritmo: função Busca-de-Custo-Uniforme (problema) retorna uma solução ou falha Busca-Genérica (problema, Insere-Ordem-Crescente)
11 Busca de Custo Uniforme
12 Busca de Custo Uniforme Fronteira do exemplo anterior
13 Busca de Custo Uniforme
14 Busca em Profundidade função Busca-em-Profundidade (problema)
Ordem de expansão dos nós: sempre expande o nó no nível mais profundo da árvore: 1. nó raiz 2. primeiro nó de profundidade 1 3. primeiro nó de profundidade 2, etc…. Quando um nó final não é solução, o algoritmo volta para expandir os nós que ainda estão na fronteira do espaço de estados Algoritmo: função Busca-em-Profundidade (problema) retorna uma solução ou falha Busca-Genérica (problema, Insere-no-Começo)
15 Busca em Profundidade
16 Busca em Profundidade Esta estratégia não é completa nem é ótima.
Custo de memória: mantém na memória o caminho sendo expandido no momento, e os nós irmãos dos nós no caminho (para possibilitar o backtracking) necessita armazenar apenas b.m nós para um espaço de estados com fator de expansão b e profundidade m, onde m pode ser maior que d (profundidade da 1a. solução) Custo de tempo: O(bm), no pior caso. Observações: Para problemas com várias soluções, esta estratégia pode ser bem mais rápida do que busca em largura. Esta estratégia deve ser evitada quando as árvores geradas são muito profundas ou geram caminhos infinitos.
17 Busca com Aprofundamento Iterativo
Evita o problema de caminhos muito longos ou infinitos impondo um limite máximo (l) de profundidade para os caminhos gerados. l ³ d, onde l é o limite de profundidade e d é a profundidade da primeira solução do problema
18 Busca com Aprofundamento Iterativo
Esta estratégia tenta limites com valores crescentes, partindo de zero, até encontrar a primeira solução fixa profundidade = i, executa busca se não chegou a um objetivo, recomeça busca com profundidade = i + n (n qualquer) piora o tempo de busca, porém melhora o custo de memória! Igual à Busca em Largura para i=1 e n=1
19 Busca com Aprofundamento Iterativo
Combina as vantagens de busca em largura com busca em profundidade. É ótima e completa com n = 1 e operadores com custos iguais Custo de memória: necessita armazenar apenas b.d nós para um espaço de estados com fator de expansão b e limite de profundidade d Custo de tempo: O(bd) Bons resultados quando o espaço de estados é grande e de profundidade desconhecida.
20 Busca com Aprofundamento Iterativo
21 Comparando Estratégias de Busca Exaustiva
22 Como Evitar Geração de Estados Repetidos?
23 Evitar Geração de Estados Repetidos
Problema geral em Busca expandir estados presentes em caminhos já explorados É inevitável quando existe operadores reversíveis ex. encontrar rotas, canibais e missionários, 8-números, etc. a árvore de busca é potencialmente infinita Idéia podar (prune) estados repetidos, para gerar apenas a parte da árvore que corresponde ao grafo do espaço de estados (que é finito!) mesmo quando esta árvore é finita, evitar estados repetidos pode reduzir exponencialmente o custo da busca
24 Evitar Geração de Estados Repetidos
Exemplo: (m + 1) estados no espaço => 2m caminhos na árvore Questões Como evitar expandir estados presentes em caminhos já explorados? Em ordem crescente de eficácia e custo computacional? Espaço de estados Árvore de busca
25 Evitando operadores reversíveis
se os operadores são reversíveis: conjunto de predecessores do nó = conjunto de sucessores do nó porém, esses operadores podem gerar árvores infinitas!
26 Como Evitar Estados Repetidos ? Algumas Dicas
1. Não retornar ao estado "pai" função que rejeita geração de sucessor igual ao pai 2. Não criar caminhos com ciclos não gerar sucessores para qualquer estado que já apareceu no caminho sendo expandido 3. Não gerar qualquer estado que já tenha sido criado antes (em qualquer ramo) requer que todos os estados gerados permaneçam na memória custo de memória: O(bd) pode ser implementado mais eficientemente com hash tables
27 Conflito (trade-off) Problema: Solução
Custo de armazenamento e verificação Solução depende do problema quanto mais "loops", mais vantagem em evitá-los! X Custo extra de busca
28 A seguir... Busca heurística
29 Estratégias de Busca Exaustiva (Cega)
30 Estratégias Busca Heurística (Informada)
31 Busca Heurística Classes de algoritmos para busca heurística:
32 Busca pela Melhor Escolha Best-First Search
33 Busca pela Melhor Escolha Algoritmo geral
34 BME: Busca Gulosa Semelhante à busca em profundidade com backtracking
35 Funções Heurísticas Função heurística - h estima o custo do caminho mais barato do estado atual até o estado final mais próximo. Funções heurísticas são específicas para cada problema Exemplo: encontrar a rota mais barata de Canudos a Petrolândia hdd(n) = distância direta entre o nó n e o nó final.
36 Funções Heurísticas Como escolher uma boa função heurística?
37 Exemplo: encontrar a rota mais barata de Canudos a Petrolândia
38 Busca Gulosa Custo de busca mínimo! Porém não é ótima:
39 Busca Gulosa Não é completa: Custo de tempo e memória: O(bd)
40 BME: Algoritmo A* A* expande o nó de menor valor de f na fronteira do espaço de estados Tenta minimizar o custo total da solução combinando: Busca Gulosa (h) econômica, porém não é completa nem ótima Busca de Custo Uniforme (g) ineficiente, porém completa e ótima f - Função de avaliação do A*: f (n) = g (n) + h (n) g (n) = distância de n ao nó inicial h (n) = distância estimada de n ao nó final
41 Algoritmo A* Se h é admissível, então f (n) é admissível também
42 Algoritmo A*: outro exemplo
43 Se fosse pela Busca Gulosa...
44 Usando A*
45 Algoritmo A*: Análise do comportamento
46 Algoritmo A* Análise do comportamento
47 Algoritmo A* Análise do comportamento
f = g + h deve ser não decrescente g é não decrescente (para operadores não negativos) custo real do caminho já percorrido h deve ser não-crescente (consistente, monotônica) h (n) ³ h (sucessor(n)) i.e., quanto mais próximo do nó final, menor o valor de h isso vale para a maioria das funções heurísticas Quando h não é consistente, para se garantir otimalidade do A*, temos: quando f(suc(n)) < f (n) usa-se f(suc(n)) = max ( f(n), g(suc(n)) + h(suc(n)) )
48 A* define Contornos f(n)  C* fator de expansão próximo de 1
49 Busca com Limite de Memória Memory Bounded Search
50 IDA* - Iterative Deepening A*
51 SMA* - Simplified Memory-Bounded A*
52 Próxima aula Vamos ver como criar nossas próprias funções heurísticas
Algoritmos de Melhorias Iterativas Para não perder o costume... Lembrem de imprimir os slides, certo? 