PCC173 - Otimização em Redes · Avisos I Próximaaula: plantãodedúvidas; I Próximaaula+1: Prova1. Marco Antonio M. Carvalho (UFOP) PCC173 25 de abril de 2019 4/38

PCC173 - Otimização em Redes

Marco Antonio M. Carvalho

Departamento de ComputaçãoInstituto de Ciências Exatas e Biológicas

Universidade Federal de Ouro Preto

25 de abril de 2019

Marco Antonio M. Carvalho (UFOP) PCC173 25 de abril de 2019 1 / 38

Avisos

Site da disciplina:I http://www.decom.ufop.br/marco/

Lista de e-mails:I [email protected]

Para solicitar acesso:I http://groups.google.com/group/pcc173


http://www.decom.ufop.br/marco/

[email protected]

http://groups.google.com/group/pcc173

Conteúdo

1 Algoritmo A∗


Avisos

I Próxima aula: plantão de dúvidas;I Próxima aula + 1: Prova 1.


Algoritmo A∗

HistóricoO algoritmo A∗ foi proposto por Peter Hart, Nils Nilsson e BertramRaphael do Stanford Research Institute em 1968, para determinar ocaminho a ser navegado pelo robô Shakey, em uma sala com obstáculos.

O mesmo algoritmo pode ser utilizado para determinar o caminho maiscurto entre um par específico de vértices.

Oriundo da inteligência artificial, este algoritmo é considerado umaextensão do algoritmo de Dijkstra e também é relacionado ao Best-FirstSearch.

Este algoritmo de assemelha ao algoritmo de Dijkstra na medida em quefavorece vértices mais próximos ao vértice inicial e também se assemelha aoBest-First Search na medida em que usa informações sobre os vértices maispróximos do destino.


Algoritmos

#

#

vice versa. A* runs fastest with the fewest graph nodes; grids are ofteneasier to work with but result in lots of nodes. This page covers the A*algorithm but not graph design; see my other page for more aboutgraphs. For the explanations on the rest of the page, I’m going to use gridsbecause it’s easier to visualize the concepts.

Algorithms

There are lots of algorithms that run on graphs. I’m going to cover these:

Breadth First Search explores equally in all directions. Thisis an incredibly useful algorithm, not only for regular pathfinding, but also for procedural map generation, flow fieldpathfinding, distance maps, and other types of mapanalysis.

Dijkstra’s Algorithm (also called Uniform Cost Search) letsus prioritize which paths to explore. Instead of exploring allpossible paths equally, it favors lower cost paths. We canassign lower costs to encourage moving on roads, highercosts to avoid forests, higher costs to discourage going nearenemies, and more. When movement costs vary, we use thisinstead of Breadth First Search.

A* is a modification of Dijkstra’s Algorithm that isoptimized for a single destination. Dijkstra’s Algorithm canfind paths to all locations; A* finds paths to one location. Itprioritizes paths that seem to be leading closer to the goal.

I’ll start with the simplest, Breadth First Search, and add one feature at atime to turn it into A*.

Breadth First Search

The key idea for all of these algorithms is that we keep track of an ex-panding ring called the frontier. On a grid, this process is sometimescalled “flood fill”, but the same technique works for non-grids. Start theanimation to see how the frontier expands:

AlgoritmosI BFS: Explora igualmente todas as direções.I Dijkstra: Prioriza caminhos de menor custo

durante a exploração.I A∗: Prioriza caminhos que parecem levar mais

rapidamente ao destino.


O Robô Shakey

Shakey em ação em outubro de 1969.


O Robô Shakey

O robô Shakey.


Algoritmo de Dijkstra

PrincípioUtiliza uma função g(n) que representa o custo exato do caminho entre ovértice de origem e qualquer vértice n.

O algoritmo explora o grafo considerando sempre o vértice de menor g(n).

A partir do vértice inicial, expande os caminhos até encontrar o destinodesejado e sempre encontra o menor caminho entre os vértices de origem edestino.



O vértice rosa é a origem e o vértice roxo o destino.A área azul mostra caminhos explorados pelo algoritmo, quanto mais claros

os vértices, mais longe do vértice de origem.



O vértice rosa é a origem e o vértice roxo o destino.No caso com obstáculos, o algoritmo de Dijkstra é lento, mas encontra o

caminho mais curto.



AnimaçãoVer animação Frontier Expansion.

cost_so_far[start] = 0

while not frontier.empty(): current = frontier.get()

if current == goal: break for next in graph.neighbors(current): new_cost = cost_so_far[current] + graph.cost(current, next) if next not in cost_so_far or new_cost < cost_so_far[next]: cost_so_far[next] = new_cost priority = new_cost frontier.put(next, priority) came_from[next] = current

Using a priority queue instead of a regular queue changes the way the fron-tier expands. Contour lines are one way to see this. Start the animation tosee how the frontier expands more slowly through the forests, findingthe shortest path around the central forest instead of through it:

Breadth First Search Dijkstra’s Algorithm

< Start animation >

Movement costs other than 1 allow us to explore more interestinggraphs, not only grids. In the map at the top of the page, movement costswere based on the distance from room to room. Movement costs can alsobe used to avoid or prefer areas based on proximity to enemies or allies.

Implementation notes: We want this priority queue to return the lowestvalue first. On the implementation page I show PriorityQueue in Pythonusing heapq to return the lowest value first and also in C++ usingstd::priority_queue configured to return the lowest value first. Also,the version of Dijkstra’s Algorithm and A* I present on this page differsfrom what’s in algorithms textbooks. It’s much closer to what’s calledUniform Cost Search. I describe the differences on the implementationpage.


https://www.redblobgames.com/pathfinding/a-star/introduction.html

Best-First Search

PrincípioUtiliza uma função h(n) que representa uma estimativa do custo docaminho entre o vértice de destino e qualquer vértice n.

O algoritmo explora o grafo considerando sempre o vértice de menor h(n).

A partir do vértice inicial, expande um único caminho até encontrar odestino desejado e não necessariamente encontra o menor caminho entre osvértices de origem e destino.

Embora seja muito mais rápido do que o algoritmo de Dijkstra, o Best-FirstSearch ignora o comprimento do caminho enquanto o expande e, portanto,pode expandir um caminho mais longo.


Best-First Search

O vértice rosa é a origem e o vértice roxo o destino.Vértices amarelos possuem alto valor de estimativa e vértices cinzapossuem baixo valor de estimativa de custo para chegar ao destino.


Best-First Search

O vértice rosa é a origem e o vértice roxo o destino.No caso com obstáculo, o Best-First Search é mais rápido, mas não possui

corretude.


Best-First Search

AnimaçãoVer animações Greedy Best-First Search.

#Heuristic search

With Breadth First Search and Dijkstra’s Algorithm, the frontier expandsin all directions. This is a reasonable choice if you’re trying to find a pathto all locations or to many locations. However, a common case is to finda path to only one location. Let’s make the frontier expand towards thegoal more than it expands in other directions. First, we’ll define a heuris-tic function that tells us how close we are to the goal:

def heuristic(a, b): # Manhattan distance on a square grid return abs(a.x - b.x) + abs(a.y - b.y)

In Dijkstra’s Algorithm we used the actual distance from the start for thepriority queue ordering. Here instead, in Greedy Best First Search, we’lluse the estimated distance to the goal for the priority queue ordering.The location closest to the goal will be explored first. The code uses thepriority queue from Dijkstra’s Algorithm but without cost_so_far :

frontier = PriorityQueue()frontier.put(start, 0)came_from = {}came_from[start] = None

while not frontier.empty(): current = frontier.get()

if current == goal: break for next in graph.neighbors(current): if next not in came_from: priority = heuristic(goal, next) frontier.put(next, priority) came_from[next] = current

Let’s see how well it works:

Breadth First Search Greedy Best-First Search



Algoritmo A∗

PrincípioO algoritmo A∗ utiliza uma função conhecimento-mais-heurística f(n)para estimar o custo do caminho mais curto entre origem e destino quepassa pelo vértice n.

A função possui dois componentes, sendo definida da seguinte maneira:

f(n) = g(n) + h(n)

Em que g(n) representa o custo exato do caminho entre o vértice inicial equalquer vértice n e h(n) representa uma estimativa heurística do custo docaminho entre o vértice n e o vértice de destino.

O algoritmo explora o grafo considerando sempre o vértice de menor f(n).


Algoritmo A∗

O vértice rosa é a origem e o vértice roxo o destino.No caso simples, o A∗ é tão rápido quanto o Best-First Search.


Algoritmo A∗

O vértice rosa é a origem e o vértice roxo o destino.No caso com obstáculos, o A∗ determina um caminho tão bom quanto o

algoritmo de Dijkstra.


Algoritmo A∗

AnimaçãoVer animações A∗ Search.

#

cost_so_far[next] = new_cost priority = new_cost + heuristic(goal, next) frontier.put(next, priority) came_from[next] = current

Compare the algorithms: Dijkstra’s Algorithm calculates the distancefrom the start point. Greedy Best-First Search estimates the distance tothe goal point. A* is using the sum of those two distances.

Dijkstra’s12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

10 11 12 13 14 25 26

9 10 11 12 13 14 15 16 17 18 19 20 24 25

8 9 10 11 12 13 14 15 16 17 18 19 23 24

7 8 9 10 11 12 13 14 15 16 17 18 22 23

6 7 8 9 10 11 12 13 14 15 16 17 21 22

5 6 7 8 9 10 11 12 13 14 15 16 20 21

4 5 6 7 8 9 10 11 12 13 14 15 19 20

3 4 5 6 7 8 9 10 11 12 13 14 18 19

2 3 4 5 6 7 8 9 10 11 12 13 17 18

1 2 3 4 5 6 7 8 9 10 11 12 16 17

0 1 15 16

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Greedy Best-First11 10 9 8 7 6 5 4 3 2

11 10 9 8 7 6 5 4 3 2 1 0

12 11 2

13 12 11 10 9 8 7 6 5

13 12 11 10 9 8 7 6

13 12 11 10 9 8 7

15 14 13 12 11 10 9 8

17 16 15 14 13 12 11 10 9

19 18 17 16 13 12 11 10

21 20 19 18 12 11

23 22 21 20 12

24 23 22

25 24

26

A* Search27 27 27 27 27 27 27 27 27 27

27 25 25 25 25 25 25 25 25 25 25 25

27 25 27

27 25 25 25 25 25 25 25 25

27 25 25 25 25 25 25 25 25

27 25 25 25 25 25 25 25 25

27 25 25 25 25 25 25 25 25

25 25 25 25 25 25 25 25 25

25 25 25 25 27 27 27 27 27 27

25 25 25 25

25 25 25 25

25 25 25

25 25

27

Try opening a hole in the wall in various places. You’ll find that whenGreedy Best-First Search finds the right answer, A* finds it too, exploringthe same area. When Greedy Best-First Search finds the wrong answer(longer path), A* finds the right answer, like Dijkstra’s Algorithm does,but still explores less than Dijkstra’s Algorithm does.

A* is the best of both worlds. As long as the heuristic does not overesti-mate distances, A* finds an optimal path, like Dijkstra’s Algorithm does.A* uses the heuristic to reorder the nodes so that it’s more likely that thegoal node will be encountered sooner.

And … that’s it! That’s the A* algorithm.

More

Are you ready to implement this? Consider using an existing li-brary. If you’re implementing it yourself, I have companion guidethat shows step by step how to implement graphs, queues, andpathfinding algorithms in Python, C++, and C#.

Which algorithm should you use for finding paths on a game map?

If you want to find paths from or to all all locations, use Breadth First



Algoritmo A∗

Considerações sobre a Estimativa HeurísticaAlgumas considerações sobre h(n):I Em um caso extremo, se h(n) = 0, então apenas g(n) guiará o

algoritmo, tornando-o equivalente ao algoritmo de Dijkstra;I Se h(n) é sempre menor ou igual ao custo do caminho mais curto

entre n e o destino, então o algoritmo A∗ garantidamente encontraráo caminho mais curto – denominamos h(n) admissível;

I Quanto menor o valor de h(n) (para todo n), mais vértices serãoexpandidos pelo A∗, tornando-o mais lento.


Algoritmo A∗

Considerações sobre a Estimativa Heurística (continuado)I Se h(n) é exatamente igual ao custo do caminho mais curto entre n e

o destino, então o A∗ expandirá somente o caminho mais curto, setornando muito rápido;

I Se h(n) em algum momento for maior que o custo do caminho maiscurto entre n e o destino, então não há garantia de que o caminhomais curto será encontrado. Porém, será rápido;

I Em outro caso extremo, se h(n) é muito maior do que g(n), entãoapenas h(n) guiará o algoritmo, tornando-o equivalente ao Best-FirstSearch.


Algoritmo A∗

TerminologiaI F : conjunto dos vértices fechados (já examinados);I A: conjunto dos vértices abertos (ainda não examinados);I f(v): função de custo do vértice v;I g(v): distância da origem até o vértice v;I g′(v): distância da origem até o vértice v, usando um vértice

intermediário;I h(v): estimativa heurística do custo do caminho do vértice v até o

vértice de destino;I N(v): conjunto de vértices adjacentes ao vértice v;I dij : distância entre os vértices i e j, de acordo com a matriz D;I rot: vetor utilizado para reconstrução do caminho determinado pelo

algoritmo.


Algoritmo A∗

Entrada: Grafo G = (V , E), vértices de origem e destino o, d, matriz de distâncias D1 F ← ∅;2 A← A ∪ {o};3 Crie um vetor vazio rot;4 g(o)← 0;5 f(o)← g(o) + h(o);6 enquanto A 6= ∅ faça7 atual← i|f(i) < f(j) ∀j ∈ A;8 se atual = d então retorna rot;9 A← A \ {atual};

10 F ← F ∪ {atual};11 para cada vértice v ∈ N(atual) faça12 se v ∈ F então continue;13 g′(v)← g(atual) + datual,v ;14 se v /∈ A ou g′(v) < g(v) então15 rot[v]← atual;16 g(v)← g′(v);17 f(v)← g(v) + h(v);18 se v /∈ A então A← A ∪ {v};19 fim20 fim21 fim22 retorna ERRO;


Algoritmo A∗

ComplexidadeA complexidade de tempo do A∗ depende diretamente da função h(v)usada.

No pior caso, a quantidade de vértices explorados é exponencial notamanho do menor caminho.

Porém, o algoritmo possui complexidade de tempo polinomial se|h(v)− h∗(v)| ≤ O(log h∗(v)), em que h∗(v) é a heurística perfeita.

Em outras palavras, o algoritmo possui complexidade de tempo polinomialse o erro de h(v) não crescer mais rapidamente do que o logaritmo daheurística perfeita.


Heurísticas

Mapas em GradePara mapas em grade, existem estimativas heurísticas adotadasamplamente:I Em grades quadradas, que permitem movimentos em 4 direções,

usamos a distância Manhattan;I Em grades quadradas, que permitem movimentos em 8 direções,

usamos a distância Chebyshev (ou distância Diagonal);I Em grades quadradas, que permitem movimentos em todas as

direções, usamos a distância Euclidiana (que permitem movimentosfora da grade);

I Em grades hexagonais, que permitem movimentos em 6 direções,usamos a distância Manhattan adaptada para grades hexagonais.


Manhattan vs. Euclidiana

Distância Manhattan (vermelho, azul e amarelo) e distância Euclidiana(verde).


Exemplo

Mapa das cidades da Romênia, um exemplo clássico para demonstração doalgoritmo A∗.


Exemplo

Vamos executar o algoritmo A∗ para determinar o caminho mais curto entre ascidades de Arad e Bucharest, utilizando como heurística a distância em linha reta,

que nunca superestima a distância real.


Exemplo


Exemplo


Exemplo


Exemplo


Exemplo

A função f(v) deve ser monotonicamente crescente ao longo do caminho.Vértices internos à área contornada possuem f(v) menor ou igual aos vértices

externos. Nos contornos, f = 380, f = 400 e f = 420.


Mais Visualizações

Visualização dos algoritmos A∗, BFS, Dijkstra e Best-First Search em ummapa rodoviárioI http://kevanahlquist.com/osm_pathfinding/

Visualização dos algoritmos A∗, BFS, Dijkstra e Best-First Search e outrosem um gridI http://qiao.github.io/PathFinding.js/visual/


http://kevanahlquist.com/osm_pathfinding/

http://qiao.github.io/PathFinding.js/visual/

Algoritmo A∗

ReferênciasI Introduction to A∗, from Red Blob Games. Disponível em:

https://www.redblobgames.com/pathfinding/a-star/introduction.html.Acessado em 20 de abril de 2018.



Exercício

Execute o algoritmo A∗ para determinar o caminho mais curto entre as cidades deDobreta e Bucharest. Utilize como heurística a distância em linha reta.


Dúvidas?


Documents

PCC173 - Otimização em Redes · Avisos I Próximaaula: plantãodedúvidas; I Próximaaula+1: Prova1. Marco Antonio M. Carvalho (UFOP) PCC173 25 de abril de 2019 4/38