INF 1771 – Inteligência Artificial
Aula 04 – Busca Heurística
Edirlei Soares de Lima
<elima@inf.puc-rio.br>
Métodos de Busca
•
Busca Cega ou Exaustiva:
–
Não sabe qual o melhor nó da fronteira a ser expandido. Apenas
distingue o estado objetivo dos não objetivos.
•
•
Busca Heurística:
–
Estima qual o melhor nó da fronteira a ser expandido com base em
funções heurísticas.
Busca Local:
–
Operam em um único estado e movem-se para a vizinhança deste
estado.
Busca Heurística
•
Algoritmos de Busca Heurística:
–
Busca Gulosa
–
A*
•
•
A busca heurística leva em conta o objetivo para decidir qual
caminho escolher.
Conhecimento extra sobre o problema é utilizado para guiar o
processo de busca.
Busca Heurística
•
Como encontrar um barco perdido?
–
–
Busca Cega -> Procura no oceano inteiro.
Busca Heurística -> Procura utilizando informações
relativas ao problema.
•
Exemplo: correntes marítimas, vento, etc.
Busca Heurística
•
•
Função Heurística (h)
–
Estima o custo do caminho mais barato do estado atual até
o estado final mais próximo.
–
São específicas para cada problema.
Exemplo:
–
Encontrar a rota mais curta entre duas cidades:
•
h(n) = distância em linha reta direta entre o nó n e o nó final.
Função Heurística
Estado Atual
Estado Objetivo
Busca Heurística
•
Algoritmos de Busca Heurística:
–
–
Busca Gulosa
A*
Busca Gulosa
•
Estratégia:
–
Expande os nós que se encontram mais próximos do
objetivo (uma linha reta conectando os dois pontos no
caso de distancias), desta maneira é provável que a busca
encontre uma solução rapidamente.
•
A implementação do algoritmo se assemelha ao utilizado na
busca cega, entretanto utiliza-se uma função heurística para
decidir qual o nó deve ser expandido.
Busca Gulosa
Arad
366
Sibiu
253
Timissoara
329
Zerind
374
Arad
366
0
Mehadia
Neamt
Oradea
Pitesti
241
234
380
100
Arad
66
Fagaras
176
Oradea
380
Rimnicu Vilcea
Bucharest
193
3
Craiova
Drobeta
Eforie
160
242
161
176
77
Rimnicu Vilcea 193
Sibiu
263
Bucharest
0
Fagaras
Giurgiu
Iasi
Sibiu
253
329
199
374
80
Timisoara
Vaslui
226
244
151
Função Heurística (h):
Distancia em linha reta
Lugoj
Zerind
Hirsova
Urziceni
Busca Gulosa
•
•
Custo de busca mínimo:
– No exemplo, não expande nós fora do caminho.
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.
Busca Gulosa
•
Ir de Iasi para Fagaras?
Busca A*
•
Estratégia:
–
Combina o custo do caminho g(n) com o valor da
heurística h(n)
–
–
g(n) = custo do caminho do nó inicial até o nó n
h(n) = valor da heurística do nó n até um nó objetivo
(distancia em linha reta no caso de distancias espaciais)
–
f(n) = g(n) + h(n)
•
É a técnica de busca mais utilizada.
Busca A*
Arad
0+366=366
Sibiu
Timissoara
Zerind
1
40+253=393 118+329=447 75+374=449
Arad
Fagaras
Oradea
Rimnicu Vilcea
220+193=413
2
80+366=646 239+176=415 291+380=671
Arad
366
0
Mehadia
Neamt
Oradea
Pitesti
241
234
380
100
Bucharest
Craiova
Drobeta
Eforie
Sibiu
38+253=591
Bucharest
Craiova
Pitesti
Sibiu
160
242
161
176
77
3
450+0=450
366+160=526 317+100=417 300+253=553
Rimnicu Vilcea 193
Bucharest
418+0=418
Craiova
Rimnicu Vilcea
414+193=607
Fagaras
Giurgiu
Iasi
Sibiu
253
329
199
374
80
455+160=615
Timisoara
Vaslui
226
244
151
Lugoj
Zerind
Hirsova
Urziceni
Busca A*
•
•
A estratégia é completa e ótima.
Custo de tempo:
–
Exponencial com o comprimento da solução, porém boas funções heurísticas
diminuem significativamente esse custo.
•
•
Custo memória:
– Guarda todos os nós expandidos na memória.
Nenhum outro algoritmo ótimo garante expandir menos nós.
Definindo Heurísticas
•
•
•
Cada problema exige uma função
heurística diferente.
Não se deve superestimar o custo
real da solução.
Como escolher uma boa função
heurística para o jogo 8-Puzzle?
Definindo Heurísticas
Estado Atual
Estado Objetivo
A quantidade de
peças for a do lugar
7
Definindo Heurísticas
Definindo Heurísticas
2
Outra Heurística?
Definindo Heurísticas
Número de movimentos
necessários para colocar
cada peça no seu lugar
2
10
Definindo Heurísticas
1
0
2
9
2
Definindo Heurísticas
•
Como escolher uma boa função
heurística para o jogo 8-Puzzle?
–
–
h¹ = número de elementos fora do lugar.
h² = soma das distâncias de cada número à
sua posição final (movimentação horizontal e
vertical).
•
Qual das heurísticas é melhor?
Exemplo - A*
1
2 3 4 5
X
1
2
☺
3
4
Exemplo - A*
•
•
•
Qual é o espaço de estados?
Quais são as ações possíveis?
Qual será o custo das ações?
Exemplo - A*
•
•
Heurística do A*: f(n) = g(n) + h(n)
–
g(n) = custo do caminho
–
h(n) = função heurística
Qual seria a função heurística h(n) mais adequada
para este problema?
–
A distancia em linha reta é uma opção.
Exemplo - A*
•
Como calcular a heurística h(n)?
–
Distancia de Manhattan
Exemplo - A*
•
O próximo passo é gerar a árvore de busca e
expandir os nós que tiverem o menor valor
resultante da função heurística f(n).
–
f(n) = g(n) + h(n)
Exemplo - A*
[
1,1]
[
2,1]
[
1,2]
[
[
1,2] = f(n) = ?? + ??
2,1] = f(n) = ?? + ??
Exemplo - A*
1
2 3 4 5
X
1
2
☺
3
4
Exemplo - A*
[
1,1]
[
2,1]
[
1,2]
[
1,1]
[2,2]
[
[
1,1] = f(n) = ?? + ??
2,2] = f(n) = ?? + ??
Exemplo - A*
1
2 3 4 5
1
2
☺
X
3
4
Exercícios
•
(1) Qual seria uma boa heurística para o jogo
da velha?
Exercícios
•
(2) Supondo que é necessário utilizar um algoritmo de busca
para resolver um problema no qual são necessárias respostas
instantâneas. Mas, mesmo utilizando o A* com uma boa
função heurística, o tempo gasto com o processo de busca
ainda está muito grande. O que pode ser feito para otimizar
esse processo?
–
–
Caminhos pré-calculados.
Custos pré-calculados.
Caminhos Pré-Calculados
•
•
Tabela pré-calculada com os melhores caminhos.
Armazena-se somente o próximo nó que deve ser seguindo do nó
atual ao nó destino.
Custos Pré-Calculados
•
•
Saber qual o melhor caminho entre dois nós somente é útil
quando se sabe onde se deseja ir.
Uma tabela pré-calculada com os custos de locomoção entre
quaisquer dois nós também é uma informação muito util.
Leitura Complementar
•
Russell, S. and Novig, P. Artificial Intelligence: a
Modern Approach, 2nd Edition, Prentice-Hall,
2003.
•
Capítulo 4: Informed Search and Exploration