Teoria dos GrafosAula 9

Aula passada

Corretude de Dijkstra

Fila de prioridades

Heap binário

Dijkstra eficiente

Aula de hojeProblema do labirinto (path finding)Busca informadaBest-first searchA*

Figueiredo – 2014

Problema do Labirinto(Path finding)

Problema: Encontrar caminho mais curto em um labirinto

Representação com grafos (direção, pesos)

BFS ou Dijkstra to the rescue!

Figueiredo – 2014

Problema com BFS e DijkstraExpandem em “todas as direções” até encontrar destino

Exploram muitos vértices desnecessários

Meio ineficiente (na prática)!

vértices na fila(descobertos)

Figueiredo – 2014

Algoritmos InformadosBFS e Dijsktra são algoritmos de busca não-informados

não conhecem nada sobre destino

Não podem fazer melhor!

Em muitos contextos, existe informação sobre o destino da busca

Como explorar isto?

Algoritmos de busca informados: vértices possuem informação

Exemplos?Locais em uma cidade: coordenadas (lat., long.)

Figueiredo – 2014

ExemploGrid em duas dimensões

Informação disponível: coordenada de cada vértice, coordenada do destino

Algoritmo de busca utiliza estas informações

Bem mais eficiente!

Figueiredo – 2014

Best-first SearchAlgoritmo para ideia anterior?

1.Best_first_search(G,s,d)2.Para cada vértice v3. dist[v] = infinito4.Define conjunto S = 0 // vazio5.dist[s] = heuristica(s,d)6.Enquanto S != V7. Selecione u em V-S, tal que dist[u] é mínima8. Se u == d, pare9. Adicione u em S10. Para cada vizinho v de u faça11. dist[v] = heuristica(v,d)

Funciona? Encontra menor caminho?

Explora vértices na ordem dada pela heurística

Ex. distância de manhattan entre u e v (distância no grid)

Estimativa de distância entre v e d (destino)

Figueiredo – 2014

Exemplo Best-First Search

Best-first search não garante menor caminho

Best-first mais eficiente que BFS

Tradeoff: eficiência x optimalidade

BFS

Best-first

Figueiredo – 2014

Melhorando Best-FirstIdeias para melhorar Best-First Search?

Problema: Best-first não utiliza o que foi descoberto, confia cegamente na heurística

Usar o que já foi descoberto!

Considere s origem, d destino, e v um vértice qualquer

dist[v] = “distância entre s e v” + heuristica(v,d)

Estimativa de distância entre s e d, passando por v e utilizando o menor caminho entre s e v

Se heuristica(v,d) = 0, o que temos?

Dijkstra!

Figueiredo – 2014

Algoritmo A*Muito famoso (início anos 70), muito utilizado, diversas aplicações em IA (ex. xadrez)

Generaliza Dijkstra e possui propriedades importantes (a saber)

Implementação demanda dois vetores de distânciasdist_s[v]: distância de s até v

dist[v]: estimativa de distância de s até d passando por v

dist_s[v]: mesmo vetor mantido por alg. de Dijkstra

dist[v]: define ordem de exploração dos vértices

Figueiredo – 2014

Algoritmo A*“Show me the code”

1.A_star(G,s,d)2.Para cada vértice v3. dist_s[v] = dist[v] = infinito4.Define conjunto S = 0 // vazio5.dist_s[s] = 06.dist[s] = 0 + heuristica(s,d)7.Enquanto S != V8. Selecione u em V-S, tal que dist[u] é mínima9. Se u == d, pare10. Adicione u em S11. Para cada vizinho v de u faça12. Se dist_s[v] > dist_s[u] + w(u,v) então13. dist_s[v] = dist_s[u] + w(u,v)14. dist[v] = dist_s[v] + heuristica(v,d)

Ex. distância de manhattan entre u e v (distância no grid)

Importante: extrai mínimo utilizando estimativa de distância

Figueiredo – 2014

Exemplo do A*

A* encontrou caminho mínimo

Explorou muito menos que BFS

BFS

A*

Maravilha sempre?

Figueiredo – 2014

Propriedades do A*A* obtém caminho mínimo quando heurística nunca sobre-estima o valor da distância (no grafo)

heurística admissível (se para todo vértice u, v)

heurística(u,d) <= distância(u,v) + heurística(v,d)

Comprimento do menor caminho no grafo entre u e v

Sempre verdade no plano (distância Euclideana) ou grid (distância de Manhattan)

Em geral, difícil encontrar heurísticas admissíveis

ex. jogo de xadrez

A* pode falhar em encontrar caminho mínimo

mas é mais eficiente que Dijkstra (tradeoff)

Figueiredo – 2014

Explorando BuscasWebsite: Red Blob Games - Amit Patel

“I explore visual and interactive ways of explaining math and computer algorithms, especially those used in computer games. I want to learn by playing with things.”

A* search: http://www.redblobgames.com/pathfinding/a-star/introduction.html

Explorem este e outros recursos deste website!

* imagens destes slides obtidos em exemplos do website