Algoritmo A* » Histórico » Revisão 4
Revisão 3 (Antonio de Souza Gomes Pereira, 08/03/2020 17:16 h) → Revisão 4/9 (Antonio de Souza Gomes Pereira, 08/03/2020 17:45 h)
# Algoritmo A*
## Introdução
A* é um algoritmo para planejamento de trajetórias em um grid contendo o destino, caminhos livres e obstáculos. Sendo amplamente utilizado para encontrar o caminho mais curto (aproximação), de uma maneira rápida e inteligente. Antes de descrever o funcionamento do mesmo, começamos com o algoritmo de Dijkstra e depois como ele pode ser derivado no A*.
## Algoritmo de Dijkstra
Dado um grafo e um vértice de origem, como podemos achar a mínima distância dele para todos os outros vértices?
Começamos a implementação criando uma lista aberta e uma lista fechada:
* A lista fechada terá como objetivo simplesmente armazenar o estado que o vértice possui, se sua miníma distância foi calculada ou não (True/False), podendo ser simplesmente um vetor de booleans ou uma hash table.
* A lista aberta conterá todos os outros vértices que já foram visitados e não estão na lista fechada, sendo composta de um par (distância, índice). Durante a execução do algoritmo, precisaremos várias vezes saber o vértice de menor distância na lista, por isso sendo de grande utilidade utilizar uma priority queue como lista fechada, pois os elementos ficarão ordenados e basta pegarmos o primeiro.
Podemos descrever o algoritmo da seguinte forma:
```
1) Initialize distances of all vertices as infinite.
2) Create an empty set. Every item of set is a pair
(weight, vertex). Weight (or distance) is used used
as first item of pair as first item is by default
used to compare two pairs.
3) Insert source vertex into the set and make its
distance as 0.
4) While Set doesn't become empty, do following
a) Extract minimum distance vertex from Set.
Let the extracted vertex be u.
b) Loop through all adjacent of u and do
following for every vertex v.
// If there is a shorter path to v
// through u.
If dist[v] > dist[u] + weight(u, v)
(i) Update distance of v, i.e., do
dist[v] = dist[u] + weight(u, v)
(i) If v is in set, update its distance
in set by removing it first, then
inserting with new distance
(ii) If v is not in set, then insert
it in set with new distance
5) Print distance array dist[] to print all shortest
paths.
```
Vamos usar o grafo abaixo como exemplo do funcionamento:
A primeira coisa a se fazer é setar todas as distâncias para +INFINITO, excetuando a origem (vértice v1), que será inserida na lista aberta e terá sua distância como 0.
| LISTA ABERTA |
|--- |
| (0 , 1) |
| LISTA FECHADA |
|--- |
Após isso, retiraremos o vértice de menor valor da lista aberta e o inserimos na lista fechada, nesse caso o v1, e calculamos a distância de todos os vértices adjacentes ao recém retirado, os vértices v6, v3 e v2, respectivamente com distâncias 14, 9 e 7, inserindo-os na lista aberta.
| LISTA ABERTA |
|--- |
| (9 , 3) |
| (13 , 2) |
| (14 , 6) |
| LISTA FECHADA |
|--- |
| 1 |
Agora devemos repetir o processo, retirando o vértice de menor valor da lista aberta e o inserindo na fechada, nesse caso o v3, e então atualizar as distâncias dos vértices adjacentes de v3. V5 não foi inicializado ainda, basta então adicioná-lo na lista aberta com a distância de 9 + 2 = 11. V2 tem, em relação a v3, distância 9 + 10 = 19, maior que o valor de 13 já existente, portanto mantemos a distância como 13. V6 tem, em relação a v3, distância 9 + 2 = 11, menor que o valor de 14 já existente, portanto substituímos o valor dele na lista aberta por 11.
| LISTA ABERTA |
|--- |
| (11 , 5) |
| (11 , 6) |
| (13 , 2) |
| (20 , 4) |
| LISTA FECHADA |
|--- |
| 1 |
| 3 |
Repetimos o processo até a lista aberta estar vazia e todos os vértices estejam na lista fechada, assim encontrando as menores distâncias de cada vértice. Veja que não encontramos o caminho específico que leva a menor distância, se quisermos fazer isso, basta criar um vetor com os índices dos vértices que sempre é atualizado quando o valor da distância também é atualizado.
## Derivando o A*
O A* é uma modificação do Dijkstra que é otimizado para apenas um destino. Enquanto o Dijkstra pode encontrar caminhos para todas, o A* encontra apenas para uma, priorizando os caminhos que estão levando mais próximo do objetivo, usando a distância do início e a distância estimada até o objetivo.
A grande diferença na implementação é que a lista aberta não conterá mais o par (distância, índice), e sim o par (f, índice), sendo o parâmetro f a soma de outros dois, o g e o h.
* g -> A distância percorrida até chegar aquele determinado vértice, exatamente igual à anterior.
* h -> A distância estimada para, a partir daquele vértice, chegar ao objetivo. Para isso podemos calcular a distância euclidiana entre os dois pontos ou usar outro tipo de métrica, como por exemplo a distância da geometria do taxista. Para fazer o cálculo, ignoramos a presença de obstáculos, por isso se tratando apenas de uma aproximação para privilegiar caminhos mais próximos do objetivo.
Segue abaixo a descrição do algoritmo:
```
// A* Search Algorithm
1. Initialize the open list
2. Initialize the closed list
put the starting node on the open
list (you can leave its f at zero)
3. while the open list is not empty
a) find the node with the least f on
the open list, call it "q"
b) pop q off the open list
c) generate q's 8 successors and set their
parents to q
d) for each successor
i) if successor is the goal, stop search
successor.g = q.g + distance between
successor and q
successor.h = distance from goal to
successor (This can be done using many
ways, we will discuss three heuristics-
Manhattan, Diagonal and Euclidean
Heuristics)
successor.f = successor.g + successor.h
ii) if a node with the same position as
successor is in the OPEN list which has a
lower f than successor, skip this successor
iii) if a node with the same position as
successor is in the CLOSED list which has
a lower f than successor, skip this successor
otherwise, add the node to the open list
end (for loop)
e) push q on the closed list
end (while loop)
```
Abaixo está um caminho gerado pelo algoritmo, considerando a distância euclideana:
Queremos partir da célula azul e chegar na vermelha. O grid acima pode ser considerado um grafo, no qual cada célula está conectada com sua vizinha, excetuando os casos em que esta é um obstáculo (pintadas de cinza)
## Referências