Futebol de Robos F180 » Inteligência

1. Algoritmo A*

1. 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*.

1. 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 o elemento de menor distância sempre ficará no topo da lista.

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

---

(7 , 2)

(9 , 3)

(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 v2, após isso devemos colocar na aberta o v4, que ainda não foi inicializado, e manter o valor de v3, pois a distância relativa ao v2 é de 17, sendo maior que 9, caso a distância calculada fosse menor que 9, o valor deveria ser substituído por esse.


LISTA ABERTA

---

(9 , 3)

(14 , 6)

(15 , 4)

LISTA FECHADA

---

1

2

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.

1. Derivando o A*

1. Referências