2 4 Resolução de Problemas Busca Gulosa e AEstrela

Prévia do material em texto

Inteligência Artificial 
Aula: 
Resolução de Problemas 
Busca Heurística 
Gulosa e A* 
DECOM/UFOP 
Busca Heurística 
Objetivo 
 Minimizar o problema dos métodos cegos: explosão combinatória. 
Como 
 Utilizando conhecimento sobre os problemas. 
 
Tipos de Heurística 
 Heurística genérica 
 Conhecimento que pode ser aplicado à maioria dos problemas. 
 Heurística específica 
 Convicções dos especialistas em uma determinada área. 
 
2 
Função Heurística 
Definição 
 Retorna um valor que indica a relevância de um nodo para se chegar à 
solução. 
 Pode denotar qualidade ou custo. 
Sintaxe: 
 h(Nodo) 
Exemplo: 
 Jogo dos 8 número de peças fora do lugar 
 
3 
Busca de Melhor Primeiro Gulosa 
(Greedy Best First Search) 
• Explora descrição de estado para estimar o quanto o 
nó de busca é “promissor” 
 
• Função heurística de avaliação de custo de nó da 
árvore de busca (notação é h(N) ) 
▫ h(N) é um custo estimado; quanto menor h(N), 
 mais promissor é o caminho que passa pelo nó N 
 
• Busca Melhor Primeiro Gulosa ordena a fronteira em 
ordem crescente de h 
4 
Romênia 
(Mais perto em linha reta….) 
Busca Melhor Primeiro Gulosa 
Greedy Best First Search (GBFS) 
• Utiliza somente função heurística 
▫ Expandir o nó que parece mais próximo (em linha 
reta)… … 
 
 
 
 
 
 
 
 
Navegação com Gulosa 
9 
0 2 1 1 
5 8 7 
7 
3 
4 
7 
6 
7 
6 3 2 
8 
6 
4 5 
2 3 3 
3 6 5 2 4 4 3 5 
5 4 6 
5 
6 
4 
5 
f(N) = h(N), Manhattan 
10 
0 2 1 1 
5 8 7 
7 
3 
4 
7 
6 
7 
6 3 2 
8 
6 
4 5 
2 3 3 
3 6 5 2 4 4 3 5 
5 4 6 
5 
6 
4 
5 7 
0 
Navegação com Gulosa 
GBFS 
• Caso normal: 
▫ GBFS leva rapidamente ao objetivo (pelo caminho 
errado…) 
 
• Pior caso: 
▫ Pode explorar toda a árvore 
▫ Sem checagem de ciclo, pode entrar em loop 
 
A*: observando o passado também 
• GBFS: ordena por h(N) 
▫ olha somente para o futuro 
▫ h(N) = custo estimado do estado representado por N 
até um nó objetivo qualquer 
 
• Busca A*: 
 ordena por f(N) = g(N) + h(N) 
 
▫ g(N) = custo do caminho conhecido e já percorrido do 
inicial até nó N 
▫ Passado e futuro 
Romênia 
(Percorrido + linha reta….) 
 
A* 
A* 
A* 
A* 
A* 
A* 
Como construir f? 
• f(N) estima custo de uma solução para objetivo 
passando por N 
 f(N) = g(N) + h(N), onde 
 g(N) custo do caminho do estado inicial até N 
 h(N) estimativa do custo do caminho de N até um nó 
objetivo 
 
• A princípio, não há limitações para h. 
Mas será que h ajuda mesmo o algoritmo de busca? 
 
20 
A* é ótimo? 
• O que deu errado? 
• Estimativa do custo de pior caminho(5) <= 
Estimativa do custo de melhor caminho (1+6) 
• Estimativas (h=7) SEMPRE tem que ser menores 
que custos reais! 
A 
G S 
1 
3 
h = 6 
h = 0 
5 h = 7 
Heurística Admissível 
• Uma heurística h é admissível (otimista) se: 
 
 
 onde é o custo verdadeiro ao nó objetivo. 
 
 
 
 Nunca sobre-estima! Sempre otimista!!!! 
 
A* é ótimo em árvore com 
heurística admissível (Demonstração) 
• O que pode dar errado? 
▫ O nó subótimo G teria que sair da 
fronteira (ser explorado) antes 
de G* 
 
• Mas isso é impossível! 
▫ Imagine que G está na fronteira 
▫ Algum nó n no subcaminho de 
G* tem que estar na fronteira 
▫ n será expandido antes de G 
… 
Solução ótima 
Busca em Árvore 
24 
O(bm) O(bm) 
Algoritmo Completo Ótimo Tempo Espaço 
BFS S N* 
UCS Custo > 0 S* S 
DFS S N 
A* Custo > 0 S S* 
O(bd) O(bd) 
O(bC*/) O(bC*/) 
O(bd) O(bd) 
Heurística Admissível 
Busca em Grafo 
25 
O(bm) O(bm) 
Algoritmo Completo Ótimo Tempo Espaço 
BFS S N* 
UCS Custo > 0 S* S 
DFS S N 
A* Custo > 0 S S* 
O(bd) O(bd) 
O(bC*/) O(bC*/) 
O(bd) O(bd) 
Heurística Consistente 
Problema: A busca em Grafo não garante soluções ótimas 
com Heurística Admissível 
 
Resolvendo o problema: Consistência 
• Como fazer para evitar que um outro caminho ainda não explorado 
possa ser melhor? 
 
 Consistência (Mais forte que admissibilidade) 
 
• Definição de Consistência: V n e n’ (sucessor de n) o Custo real 
sempre tem que ser maior ou igual à redução no valor da heurística. 
 
 𝑐𝑢𝑠𝑡𝑜 𝑛, 𝑎𝑐ã𝑜, 𝑛′ ≥ ℎ 𝑛 − ℎ(𝑛′) 
 
n 
n’ 
G 
3 
h(n’) = 6 
h(n) = 10 
g = 10 
h(n’) = 8 
 É a mesma ideia da Desigualdade triangular ( vértices: n n’ G ) 
 ℎ 𝑛 ≤ 𝑐𝑢𝑠𝑡𝑜 𝑛, 𝑎𝑐ã𝑜, 𝑛′ + ℎ(𝑛′) 
 
- 
Exemplo: Jogo dos 8 (8-puzzle) 
 
 
 
 
 
▫ h1(n) = número de peças fora do lugar = 6 
 
▫ h2(n) = somatório das distâncias de Manhattan 
 = 2 + 3 + 0 + 1 + 3 + 0 + 3 + 1 = 13 
 
27 
1 4 
7 
5 
2 
6 3 
8 
 Início 
6 4 
7 
1 
5 
2 
8 
3 
Objetivo 
Exemplo: Jogo dos 8 (8-puzzle) 
Custo típico de busca: 
 ( d = profundidade da solução ) 
 
 d = 14 
 IDS = 3.473.941 nós 
 A*(h1) = 539 nós 
 A*(h2) = 113 nós 
 
 d = 24 
 IDS = 54.000.000.000 nós 
 A*(h1) = 39.135 nós 
 A*(h2) = 1.641 nós 
 
 
28 
Dominância de Heurísticas 
• Dominância: ha ≥ hc se 
 
 
• Heurísticas formam um semi-reticulado: 
▫ Max de admissíveis é admissível 
 
 
 
• Heurísticas triviais 
▫ Fundo do reticulado é zero (o que é?) 
▫ Topo é o custo exato 
Resumo: Otimalidade de A* 
• Árvore de busca: 
▫ A* é ótima se h é admissível (e não-negativa) 
▫ UCS é um caso especial com h=0 
 
• Grafo de busca: 
▫ A* é ótima se h é consistente 
▫ UCS é um caso especial (h = 0 é consistente) 
 
• Consistência implica em admissibilidade. Em geral, 
heurísticas admissíveis são também consistentes, em especial 
se vêm de versões relaxadas do problema. 
 
• É otimamente eficiente dada uma heurística. 
 
Exercício 
31 
Apresente a árvore de busca parcial gerada pelo método A* e a solução final. 
Os nodos devem ser enumerados (numeração romana) na ordem em que são 
escolhidos para expansão. Junto a cada nodo coloque o valor de f(N) em 
números arábicos. Os movimentos válidos são: Cima, Baixo, Direita e Esquerda. 
 
f(N) = g(N) + h(N), onde g(N) = distância percorrida (cada movimento = 1) 
 h(N) = distância de Manhattan (n° nos quadrados) 
1 2 3 4 5 6 7 8 9 10 11 
5 
4 
3 
2 
1 
0 2 1 1 
5 8 7 
7 
3 
4 
7 
6 
7 
6 3 2 
8 
6 
4 5 
2 3 3 
3 6 5 2 4 4 3 5 
5 4 6 
5 
6 
4 
5 
Inicio 
nodo (2, 1) 
Objetivo 
nodo (3, 7)