domingo, 1 de março de 2015

[Python] - Algoritmo de busca A*

Olá pessoal, dando continuidade aos posts sobre Inteligência Artificial, iremos falar sobre o algoritmo de busca A* (A star).

A* é uma combinação do Uniform Cost Search (UCS) e algoritmos gulosos (greedy). O UCS ordena pelo custo do caminho ou backward cost. Já o Greedy pela proximidade do objetivo ou forward cost.

Veja bem, se o custo do UCS é dado por g(n) e o custo do Greedy é dado por h(n), então podemos dizer o custo de A* é dado por:

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

Uma imagem vale mais que mil palavras:


Para você compreender melhor o código que irei colocar, é essencial que você assista a vídeo-aula seguinte, pois a implementação foi baseada nessa vídeo-aula, é em inglês, mas possui legendas em inglês para um melhor entendimento por parte de quem não tem fluência no idioma.


A implementação foi feita em Python. Trata-se de um único arquivo chamado "a_star.py" que contém três classes: uma classe que representa uma fila de prioridades (PriorityQueue), uma classe que representa um nó/vértice (Node) e uma classe que representa um grafo (Graph).

Veja o seguinte grafo que foi utilizado na vídeo-aula que você acabou de assistir:


No grafo acima, o vértice de onde se inicia é o "S" e o objetivo é o "G". Veja o passo a passo da execução do A*:

g(S) = 0, h(S) = 3 e f(S) = g(S) + h(S) = 3

O "S" é colocado na fila de prioridades. Essa fila de prioridades é pelo menor "f".

O "S" é retirado da fila juntamente com o seu "g" e "h".

Para cada sucessor de "S" é calculado um "g" e um "f", em seguida o sucessor é colocado na fila de prioridades com o seu respectivo "g", "h" e o "f".

Para o sucessor "A" temos que:

g(A) = g(S) + (peso da aresta)
g(A) = 0 + 2 = 2
h(A) = 2
f(A) = g(A) + h(A) = 2 + 2 = 4

Para o sucessor "B" temos que:

g(B) = g(S) + (peso da aresta) = 0 + 2 = 2
h(B) = 1
f(B) = g(B) + h(B) = 2 + 1 = 3

Como a fila de prioridades é pelo menor "f", então eu removo um elemento da fila que é o "B", pois o "B" tem um "f" menor que o "A".

Para cada sucessor de "B", calculo novamente o "g" e "f". O "B" só tem um sucessor que é o "G", então temos:

g(G) = g(B) + (peso da aresta) = 2 + 3 = 5
f(G) = g(G) + h(G) = 5 + 0 = 5

Veja só, chegou ao objetivo, mas como bem explica a vídeo-aula, não devemos parar, devemos continuar porque pode ser que exista um caminho melhor. O próximo elemento a ser removido é o "A" porque o f(A) é 4 e o f(G) é 5, o menor é 4, então ele tem prioridade.

O único sucessor do "A" é o "G", então fazemos:

g(G) = g(A) + (peso da aresta) = 2 + 2 = 4
f(G) = g(G) + h(G) = 4 + 0 = 4

Perceba que conseguimos um f(G) menor indo por "A", então o caminho fica sendo: 


S -> A -> G com custo 4.

Veja esse outro grafo:


Tente executar o passo a passo você mesmo, inicia de "S" e o objetivo é o "G". O menor caminho tem custo 6 e passa por S -> A -> D -> G.

Esses dois grafos descritos acima foram utilizados como exemplos para testar a implementação, veja só a saída para cada um:


O código está bem comentado, segue o link do repositório:



Nenhum comentário: