Projeto

Geral

Perfil

Algoritmo A* » Histórico » Versão 3

Antonio de Souza Gomes Pereira, 08/03/2020 17:16 h

1 1 Antonio de Souza Gomes Pereira
# Algoritmo A*
2
3 2 Antonio de Souza Gomes Pereira
## Introdução
4
5
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*.
6
7
## Algoritmo de Dijkstra
8
9
Dado um grafo e um vértice de origem, como podemos achar a mínima distância dele para todos os outros vértices?
10
Começamos a implementação criando uma lista aberta e uma lista fechada:
11
12
* 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. 
13
14 3 Antonio de Souza Gomes Pereira
* 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. 
15 2 Antonio de Souza Gomes Pereira
16
Podemos descrever o algoritmo da seguinte forma:
17
18
19
```
20
1) Initialize distances of all vertices as infinite.
21
22
2) Create an empty set.  Every item of set is a pair
23
  (weight, vertex). Weight (or distance) is used used
24
  as first item  of pair as first item is by default 
25
  used to compare two pairs.
26
27
3) Insert source vertex into the set and make its
28
   distance as 0.
29
30
4) While Set doesn't become empty, do following
31
    a) Extract minimum distance vertex from Set. 
32
       Let the extracted vertex be u.
33
    b) Loop through all adjacent of u and do 
34
       following for every vertex v.
35
36
           // If there is a shorter path to v
37
           // through u. 
38
           If dist[v] > dist[u] + weight(u, v)
39
40
               (i) Update distance of v, i.e., do
41
                     dist[v] = dist[u] + weight(u, v)
42
               (i) If v is in set, update its distance
43
                   in set by removing it first, then
44
                   inserting with new distance
45
               (ii) If v is not in set, then insert
46
                    it in set with new distance
47
               
48
5) Print distance array dist[] to print all shortest
49
   paths. 
50
```
51
52
53
54
Vamos usar o grafo abaixo como exemplo do funcionamento:
55
56
![](exgrafo.png)
57
58
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.
59
60
| LISTA ABERTA |
61
|---           |
62
|   (0 , 1)    |   
63
64
65
| LISTA FECHADA |
66
|---            |
67
68
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.
69 3 Antonio de Souza Gomes Pereira
![](grafoit1.png)
70 2 Antonio de Souza Gomes Pereira
71 1 Antonio de Souza Gomes Pereira
| LISTA ABERTA |
72 2 Antonio de Souza Gomes Pereira
|---           |
73
|   (9 , 3)    | 
74 3 Antonio de Souza Gomes Pereira
|   (13 , 2)   | 
75 2 Antonio de Souza Gomes Pereira
|   (14 , 6)   |   
76
77
78
79
| LISTA FECHADA |
80
|---            |
81
|   1           | 
82
83
    
84
85 3 Antonio de Souza Gomes Pereira
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.  
86 2 Antonio de Souza Gomes Pereira
87 1 Antonio de Souza Gomes Pereira
88 3 Antonio de Souza Gomes Pereira
![](grafoit2.png)
89 2 Antonio de Souza Gomes Pereira
90 1 Antonio de Souza Gomes Pereira
| LISTA ABERTA |
91 2 Antonio de Souza Gomes Pereira
|---           | 
92 3 Antonio de Souza Gomes Pereira
|   (11 , 5)   | 
93
|   (11 , 6)   | 
94
|   (13 , 2)   | 
95
|   (20 , 4)   | 
96
 
97 2 Antonio de Souza Gomes Pereira
  
98 1 Antonio de Souza Gomes Pereira
| LISTA FECHADA |
99
|---            |
100
|   1           | 
101 3 Antonio de Souza Gomes Pereira
|   3           | 
102 1 Antonio de Souza Gomes Pereira
103
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.
104
105
## Derivando o A*
106
107 3 Antonio de Souza Gomes Pereira
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.
108
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.
109 1 Antonio de Souza Gomes Pereira
110 3 Antonio de Souza Gomes Pereira
* g -> A distância percorrida até chegar aquele determinado vértice, exatamente igual à anterior.
111
* 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.
112
113
Segue abaixo a descrição do algoritmo:
114
115
```
116
// A* Search Algorithm
117
1.  Initialize the open list
118
2.  Initialize the closed list
119
    put the starting node on the open 
120
    list (you can leave its f at zero)
121
122
3.  while the open list is not empty
123
    a) find the node with the least f on 
124
       the open list, call it "q"
125
126
    b) pop q off the open list
127
  
128
    c) generate q's 8 successors and set their 
129
       parents to q
130
   
131
    d) for each successor
132
        i) if successor is the goal, stop search
133
          successor.g = q.g + distance between 
134
                              successor and q
135
          successor.h = distance from goal to 
136
          successor (This can be done using many 
137
          ways, we will discuss three heuristics- 
138
          Manhattan, Diagonal and Euclidean 
139
          Heuristics)
140
          
141
          successor.f = successor.g + successor.h
142
143
        ii) if a node with the same position as 
144
            successor is in the OPEN list which has a 
145
           lower f than successor, skip this successor
146
147
        iii) if a node with the same position as 
148
            successor  is in the CLOSED list which has
149
            a lower f than successor, skip this successor
150
            otherwise, add  the node to the open list
151
     end (for loop)
152
  
153
    e) push q on the closed list
154
    end (while loop) 
155
156
```
157 2 Antonio de Souza Gomes Pereira
158
## Referências