Aprenda sobre o algoritmo A Estrela no Python, um algoritmo de otimização, e veja como criá-lo linha a linha de código.
Caso prefira esse conteúdo no formato de vídeo-aula, assista ao vídeo abaixo ou acesse o nosso canal do YouTube!
Para receber por e-mail o(s) arquivo(s) utilizados na aula, preencha:
Na aula de hoje, vou te apresentar o algoritmo A Estrela no Python. Esse algoritmo, também conhecido como A* ou A Star, é uma ferramenta de otimização que utilizaremos para encontrar os melhores caminhos dentro de um labirinto!
A ideia é empregar o labirinto que aprendemos a construir na aula anterior para que você possa descobrir a rota mais eficiente do ponto inicial até o final.
Esse processo replica a funcionalidade dos aplicativos de mapas e GPS, que nos orientam pela rota mais rápida entre dois pontos, considerando os caminhos possíveis.
Nesta aula, vou te mostrar como funciona o algoritmo A Estrela no Python e como construí-lo passo a passo para descobrir o melhor caminho dentro dos labirintos que aprendemos a criar anteriormente.
Então, faça o download do material disponível e vamos começar!
Para compreender o funcionamento e a lógica por trás do Algoritmo A Estrela, vamos utilizar um labirinto de 4 linhas e 4 colunas gerado pela biblioteca pyamaze.
Nesse labirinto, queremos sair da célula inicial (4,4) e chegar até a célula final (1,1). Dentro dele, há diversos caminhos possíveis, alguns mais práticos, rápidos e intuitivos, outros menos intuitivos e rápidos, e outros que são inviáveis, como ir para um caminho sem saída.
Ou seja, ao pensar em um algoritmo que irá explorar as possibilidades, precisamos considerar um que ignore as opções inúteis, poupando tempo e processamento de dados irrelevantes.
Considere, por exemplo, aplicativos de mapas e GPS como o Google Maps e o Waze. Esses aplicativos não consideram todas as rotas possíveis entre o ponto A e o ponto B, mas sim as viáveis, determinando as mais rápidas e curtas.
Se eles considerassem todas as rotas existentes, demandaria um tempo e um processamento muito longos.
Para determinar os melhores caminhos possíveis e, a partir deles, a melhor rota, esses aplicativos precisam de algoritmos como o A*.
O A Estrela é um algoritmo que otimiza essas buscas pelos melhores caminhos por meio de um método que leva em consideração a quantidade percorrida somada a uma estimativa da quantidade restante.
Voltando para o exemplo do nosso labirinto, o A Estrela consideraria quantas células já percorremos e a estimativa de células restantes para chegar ao ponto final. A soma desses dois valores resulta em um custo para cada célula do labirinto.
Esse custo é chamado de f_score, e é dado pela soma de g_score (passos dados) e h_score (estimativa restante). Portanto, no labirinto 4×4, teremos na célula inicial um f_score de 6, pois demos 0 passos, e o caminho estimado até o ponto final, desconsiderando paredes, levaria 6 passos.
f_score = g_score + h_score
A cada movimento feito dentro do labirinto, o A* recalcula esses valores, atribuindo um novo custo para a célula atual e para as células adjacentes.
No entanto, se a pontuação para uma célula adjacente for maior do que a pontuação anterior que essa célula já tinha, o algoritmo não a substituirá, evitando assim andar para trás.
Como o algoritmo A Estrela já realiza esse cálculo para evitar “andar para trás”, o próximo passo de tomada de decisão é calcular qual célula adjacente tem o menor valor, ou seja, qual a célula tem o “menor custo” para se mover e, por consequência, o melhor caminho.
Quando temos células com o mesmo custo, o algoritmo A Estrela optará por aquela que tem o menor h_score, ou seja, aquela célula que tem o menor custo estimado até o resultado final.
Se o custo (f_score) e o h_score forem iguais para ambos os caminhos, ele optará por começar sua busca por um deles, tanto faz qual for escolhido.
Na imagem acima, por exemplo, tanto a célula (2,4) quanto a célula (3,3) possuem o mesmo f_score e o mesmo h_score. Então, o A* optará por um desses caminhos e continuará explorando a partir dele.
Entretanto, essa exploração durará enquanto o caminho selecionado tiver opções com um f_score menor do que o caminho que não foi escolhido.
Ou seja, o algoritmo seguirá pelo caminho da célula (2,4) e continuará explorando até encontrar uma célula em que o f_score dela seja maior do que 6. Quando o f_score de uma próxima célula for maior do que 6, o A* retornará para o caminho da célula (3,3) e começará a explorar a partir dele.
Perceba que a partir da célula (1,2), o caminho para a célula (2,2) custaria 8. Então, o algoritmo A* voltará para a célula (3,3). Quando no caminho da célula (3,3) ele encontrar um valor de custo 8, ele irá novamente comparar entre as duas possibilidades, qual a que tem o menor h_score.
Repare que a próxima célula a partir de (3,3) tem custo 8 já, e seu g_score é 5. Desse modo, o algoritmo retorna para a célula (2,2), que tem um g_score menor, e continua a buscar o melhor caminho. Chegando assim na célula final.
Perceba que, apesar de ter explorado algumas possibilidades inúteis, o A* otimizou essa busca pelo melhor caminho, tanto é que teve células que ele nem mesmo visitou.
Caso queira compreender como funciona essa lógica mais detalhada para mecanismos de buscas, confira essa aula aqui, que lá explico como funciona o Waze
Agora que compreendemos a lógica do algoritmo A*, precisaremos desenvolver, dentro do nosso código, uma função para calcular o h_score e uma função para o algoritmo A Estrela, que executará todo o processo de análise e tomada de decisões para determinar o melhor caminho.
A função aestrela, que será o nosso algoritmo A* em Python, terá que executar toda a lógica que vimos por trás do A Estrela. Podemos ordenar essa lógica na função da seguinte forma:
Para auxiliar no desenvolvimento do nosso código, utilizaremos a biblioteca padrão do Python queue com a estrutura de dados chamada PriorityQueue.
Com essa biblioteca, é possível criar uma fila utilizando o PriorityQueue(), adicionar elementos dentro dessa fila e remover o elemento de menor valor.
Para compreender melhor o funcionamento dela, vou demonstrar um exemplo.
from queue import PriorityQueue
fila = PriorityQueue()
fila.put((2, "Lira"))
fila.put((3, "Marcus"))
fila.put((1, "João"))
print(fila.queue)Nesse código, estamos iniciando uma fila com PriorityQueue() e adicionando os elementos (2, “Lira”), (3, “Marcus”) e (1, “João”).
Repare que essa fila funciona como uma lista de tuplas. Além de adicionar elementos à fila utilizando o método put, é possível remover elementos utilizando o método get.
Esse método irá remover sempre o elemento de menor valor da fila, mas manterá os outros dois lá. Então, se executarmos uma vez, a tupla (1, “João”) será removida, mas as outras duas se manterão na fila. Executando uma segunda vez, a tupla (2, “Lira”) será removida por passar a ser o menor valor.
from queue import PriorityQueue
fila = PriorityQueue()
fila.put((2, "Lira"))
fila.put((3, "Marcus"))
fila.put((1, "João"))
print(fila.queue)
print(fila.get())
print(fila.queue)
print(fila.get())
print(fila.queue)
O PriorityQueue não remove o primeiro item da lista com o método get, mas sim o item de menor valor, o que será muito útil para o desenvolvimento do nosso algoritmo. Conseguiremos pegar dentro da lista de caminhos o caminho com menor valor.
Para situações em que tivermos mais de um valor dentro da tupla, o PriorityQueue primeiro verificará o primeiro valor e, caso encontre dois valores iguais, verificará o segundo valor para determinar qual o menor item.
Utilizaremos a biblioteca pyamaze para criar o labirinto que será utilizado no desenvolvimento do nosso algoritmo A Estrela.
Atenção: Como já mencionado, esta aula é uma continuação da aula passada sobre a criação de labirintos no Python. Recomenda-se que você acesse a aula anterior antes de continuar com esta.
from pyamaze import maze, agent
def h_score():
pass
def aestrela(labirinto):
caminho = ""
return caminho
labirinto = maze()
labirinto.CreateMaze()
agente = agent(labirinto, filled=True, footprints=True)
caminho = estrela(labirinto)
labirinto.tracePath({agente: caminho}, delay=300)
labirinto.run()Por enquanto, estamos apenas criando o nosso labirinto. Observe que o caminho que o agente percorrerá dentro do labirinto será determinado pela função aestrela, que será o nosso algoritmo A*.
Como ainda não temos a função definida, podemos deixá-la retornando um caminho vazio para verificar se o labirinto está sendo gerado corretamente.
Para desenvolver a nossa função aestrela, precisamos, antes de tudo, definir a função h_score que calculará a estimativa de passos que faltam para o final do labirinto.
Para calcular quantos passos faltam para o final do labirinto, precisamos saber a célula atual e qual é o destino. Então, nossa função h_score receberá a célula atual e a célula final.
Cada uma dessas células será composta por uma tupla contendo o valor da linha e da coluna correspondente. Vamos chamar as linhas da célula atual de linhac e colunac, e da célula de destino de linhad e colunad.
Para cada uma dessas variáveis, vamos atribuir o índice referente dentro da tupla, ou seja, linhac recebe o valor de celula[0] e colunac o valor de celula[1]. As linhad e colunad receberão, respectivamente, destino[0] e destino[1].
Como por padrão o labirinto é criado tendo a célula de destino como sendo a célula (1,1), podemos definir o valor de destino antes da função.
Para calcular o h_score, temos de pegar a diferença entre a coluna da célula atual e a coluna da célula de destino e somarmos essa diferença à diferença entre a linha da célula atual e a linha da célula de destino.
É esse o valor que essa função deve nos retornar. Para evitar valores negativos, podemos utilizar a função abs para garantir valores absolutos.
destino = (1,1)
def h_score(celula, destino):
linhac = celula[0]
colunac = celula[1]
linhad = destino[0]
colunad = destino[1]
return abs(colunac - colunad) + abs(linhac - linhad)Com a função h_score pronta, precisamos desenvolver a função aestrela. O primeiro passo dentro dessa função será criar o tabuleiro do labirinto atribuindo a todas as células o valor de f_score infinito.
Relembrando da aula de criação do labirinto, uma das informações que temos disponíveis para acessar é o grid do labirinto, que é uma lista de tuplas, onde cada tupla indica as coordenadas das células do labirinto no formato (linha, coluna).
Para criarmos o tabuleiro com o f_score infinito para todas as células do labirinto, podemos criar um dicionário e utilizar dentro dele um list comprehension que irá percorrer cada célula presente dentro do nosso labirinto.grid e atribuir a elas o valor de infinito (float(“inf”)).
def aestrela(labirinto):
#Criar tabuleiro com valores infinitos:
f_score = {celula: float("inf") for celula in labirinto.grid}Se visualizarmos esse f_score com um print, teremos um dicionário em que cada célula do nosso labirinto será a chave, e o valor para todas estará definido como infinito.
Feito isso, podemos criar um dicionário, inicialmente vazio, para calcular o g_score de cada célula.
def aestrela(labirinto):
#Criar tabuleiro com valores infinitos:
f_score = {celula: float("inf") for celula in labirinto.grid}
#Criar Dicionário g_score:
g_score = {}Agora precisamos calcular o valor da célula inicial. A célula inicial sempre será a última célula gerada no labirinto. Nesse caso, seria a célula (10,10), porém, como o valor do labirinto pode ser alterado, vamos definir a célula inicial como sendo o número de linhas (rows) e o número de colunas (cols) presentes nele.
def aestrela(labirinto):
#Criar tabuleiro com valores infinitos:
f_score = {celula: float("inf") for celula in labirinto.grid}
#Criar Dicionário g_score:
g_score = {}
#Calcular célula inicial:
celula_inicial = (labirinto.rows, labirinto.cols)Dessa forma, se criarmos um labirinto de 50 por 50, a célula inicial será a célula (50,50). Se criarmos um labirinto de 10 por 12, a célula inicial será a (10,12).
Para calcular o valor dessa célula, precisamos fazer o g_score dela + o h_score. O g_score será 0, porque nenhuma distância ainda foi percorrida, e o h_score será calculado pela função que criamos anteriormente.
def aestrela(labirinto):
#Criar tabuleiro com valores infinitos:
f_score = {celula: float("inf") for celula in labirinto.grid}
#Criar Dicionário g_score:
g_score = {}
#Calcular célula inicial:
celula_inicial = (labirinto.rows, labirinto.cols)
g_score[celula_inicial] = 0
f_score[celula_inicial] = g_score[celula_inicial] + h_score(celula_inicial, destino)Se printarmos novamente o f_score, veremos que todas as células estão com valores infinitos, exceto a célula (10, 10), que é o ponto de partida do labirinto. Ela terá o valor de 18.
Até agora, já conseguimos criar nosso tabuleiro com os valores das células definidos como infinito e calcular o valor da célula inicial.
O próximo passo será utilizar o PriorityQueue para conseguirmos caminhar para cada célula. Vamos importar o Priority Queue a partir da biblioteca queue para o nosso código.
from pyamaze import maze, agent
from queue import PriorityQueueE inicializar uma fila dentro da nossa função aestrela.
def aestrela(labirinto):
#Criar tabuleiro com valores infinitos:
f_score = {celula: float("inf") for celula in labirinto.grid}
#Criar Dicionário g_score:
g_score = {}
#Calcular célula inicial:
celula_inicial = (labirinto.rows, labirinto.cols)
g_score[celula_inicial] = 0
f_score[celula_inicial] = g_score[celula_inicial] + h_score(celula_inicial, destino)
fila = PriorityQueue()Com a fila criada, é necessário adicionar as células do nosso labirinto a ela. No entanto, devemos fazer isso de maneira que a PriorityQueue consiga priorizar as células de acordo com o f_score e, em seguida, com o h_score, pois é essa a lógica do A Estrela.
Para realizar essa tarefa, vamos criar uma variável chamada item que será uma tupla contendo o f_score, seguido pelo h_score e, por fim, a célula correspondente. Isso garantirá que a PriorityQueue avalie primeiro o f_score e, em caso de empate, o h_score será considerado para determinar a célula de menor custo.
Dessa forma, ao retirarmos um item dessa fila para ser o próximo passo dentro do labirinto, estaremos sempre selecionando o item de menor custo. Isso ocorre porque primeiro será verificado o f_score e, em caso de empate, o h_score será considerado para determinar o menor custo.
def aestrela(labirinto):
#Criar tabuleiro com valores infinitos:
f_score = {celula: float("inf") for celula in labirinto.grid}
#Criar Dicionário g_score:
g_score = {}
#Calcular célula inicial:
celula_inicial = (labirinto.rows, labirinto.cols)
g_score[celula_inicial] = 0
f_score[celula_inicial] = g_score[celula_inicial] + h_score(celula_inicial, destino)
#Criando a Fila:
fila = PriorityQueue()
#Adicionando item na Fila:
item = (f_score[celula_inicial], h_score(celula_inicial, destino), celula_inicial)
fila.put(item)Para percorrermos o labirinto através da nossa fila, vamos utilizar um loop while, com a condição de que ele se repetirá enquanto a fila não estiver vazia (empty).
Dentro desse loop, iremos selecionar a célula de menor valor da fila, calcular os caminhos possíveis a partir dela, calcular o f_score desses caminhos possíveis e adicionar a célula com o menor f_score à nossa fila.
Esse processo continuará retirando um valor e adicionando um valor até chegarmos à célula de destino, onde ele retirará um valor e não adicionará mais nenhum valor. Encerrando assim o laço de repetição.
def aestrela(labirinto):
#Criar tabuleiro com valores infinitos:
f_score = {celula: float("inf") for celula in labirinto.grid}
#Criar Dicionário g_score:
g_score = {}
#Calcular célula inicial:
celula_inicial = (labirinto.rows, labirinto.cols)
g_score[celula_inicial] = 0
f_score[celula_inicial] = g_score[celula_inicial] + h_score(celula_inicial, destino)
#Criando a Fila:
fila = PriorityQueue()
#Adicionando item na Fila:
item = (f_score[celula_inicial], h_score(celula_inicial, destino), celula_inicial)
fila.put(item)
#Caminhando utilizando a Fila:
while not fila.empty():
celula = fila.get()[2]
#Se a celula for o destino final, interrompe o loop
if celula == destino:
breakApós esse processo, serão verificadas as direções possíveis a partir da célula atual, considerando as quatro direções: norte (N), sul (S), leste (E) e oeste (W).
Para verificar se existem paredes ou não em uma dessas quatro direções, utilizaremos mais um conceito que foi abordado na aula sobre a criação de labirintos: o mapa do labirinto.
Através do atributo maze_map, é possível obter um dicionário no qual cada chave representa uma das células do labirinto, e o valor é outro dicionário contendo as direções norte (N), sul (S), leste (E) e oeste (W).
Nesse mapa, quando uma das direções possui um caminho livre, ela recebe o valor de 1; quando há uma parede, o valor é 0.
Então, para verificar esses valores para uma célula específica, só precisamos acessar o maze_map com o valor da célula desejada entre colchetes.
Por exemplo, usando a imagem acima, se imprimirmos labirinto.maze_map[(1, 1)], teremos como resposta o dicionário {‘E’: 1, ‘W’: 0, ‘N’: 0, ‘S’: 0}. E se quisermos saber apenas o valor de E, podemos fazer labirinto.maze_map[(1, 1)][‘E’].
Com isso, podemos verificar dentro do nosso loop for quando uma das direções será um caminho possível e quando ela será uma parede. Se o valor correspondente à direção for 1, ela será um caminho disponível.
def aestrela(labirinto):
#Criar tabuleiro com valores infinitos:
f_score = {celula: float("inf") for celula in labirinto.grid}
#Criar Dicionário g_score:
g_score = {}
#Calcular célula inicial:
celula_inicial = (labirinto.rows, labirinto.cols)
g_score[celula_inicial] = 0
f_score[celula_inicial] = g_score[celula_inicial] + h_score(celula_inicial, destino)
#Criando a Fila:
fila = PriorityQueue()
#Adicionando item na Fila:
item = (f_score[celula_inicial], h_score(celula_inicial, destino), celula_inicial)
fila.put(item)
#Caminhando utilizando a Fila:
while not fila.empty():
celula = fila.get()[2]
#Se a celula for o destino final, interrompe o loop:
if celula == destino:
break
#Verficando as Direções Possíveis:
for direcao in "NSEW":
if labirinto.maze_map[celula][direcao] == 1:Se o caminho for possível, vamos avançar para a próxima etapa, que é calcular o f_score de cada caminho. Caso contrário, isto é, se o caminho não for possível, não faremos nada.
Para calcular o f_score, precisamos primeiro descobrir qual é a célula referente a cada direção possível. Para isso, é necessário pensar na lógica do nosso labirinto.
Quando seguimos de uma célula para a outra na direção Norte, a próxima célula terá o valor da linha atual subtraído por 1, e o mesmo valor de coluna.
Ao seguir pela direção Sul, a próxima célula terá o valor da linha atual somado por 1 e o mesmo valor de coluna.
Se seguirmos para a direção Oeste, teremos o mesmo valor de linha, mas o valor de coluna será o valor da coluna atual subtraído por 1.
Finalmente, se caminharmos para o Leste, teremos o mesmo valor de linha; no entanto, o valor da coluna será o da coluna atual somado por 1.
É possível visualizar essa lógica observando o labirinto com as células contendo suas tuplas:
Observe que sempre que alteramos entre as direções norte e sul, o primeiro valor da tupla se altera em mais um ou menos um, pois estamos mudando de linha. Enquanto que na direção leste e oeste, o segundo valor da tupla é que é modificado, representando as colunas.
No nosso código, podemos implementar essa lógica da seguinte forma:
def aestrela(labirinto):
#Criar tabuleiro com valores infinitos:
f_score = {celula: float("inf") for celula in labirinto.grid}
#Criar Dicionário g_score:
g_score = {}
#Calcular célula inicial:
celula_inicial = (labirinto.rows, labirinto.cols)
g_score[celula_inicial] = 0
f_score[celula_inicial] = g_score[celula_inicial] + h_score(celula_inicial, destino)
#Criando a Fila:
fila = PriorityQueue()
#Adicionando item na Fila:
item = (f_score[celula_inicial], h_score(celula_inicial, destino), celula_inicial)
fila.put(item)
#Caminhando utilizando a Fila:
while not fila.empty():
celula = fila.get()[2]
#Se a celula for o destino final, interrompe o loop:
if celula == destino:
break
#Verficando as Direções Possíveis:
for direcao in "NSEW":
if labirinto.maze_map[celula][direcao] == 1:
#Posição da célula atual:
linha_celula = celula[0]
coluna_celula = celula[1]
#Calculando a Posição da Próxima Célula:
if direcao == "N":
proxima_celula = (linha_celula - 1, coluna_celula)
elif direcao == "S":
proxima_celula = (linha_celula + 1, coluna_celula)
elif direcao == "W":
proxima_celula = (linha_celula, coluna_celula - 1)
elif direcao == "E":
proxima_celula = (linha_celula, coluna_celula + 1)Após descobrirmos qual será a próxima célula analisada, precisamos calcular o g_score dessa célula, que sempre será o g_score da célula atual + 1, visto que você dará mais um passo dentro do labirinto.
Como criamos um dicionário para armazenar o g_score, o novo g_score será o g_score da célula atual que está armazenado no nosso dicionário, somado a 1.
def aestrela(labirinto):
#Criar tabuleiro com valores infinitos:
f_score = {celula: float("inf") for celula in labirinto.grid}
#Criar Dicionário g_score:
g_score = {}
#Calcular célula inicial:
celula_inicial = (labirinto.rows, labirinto.cols)
g_score[celula_inicial] = 0
f_score[celula_inicial] = g_score[celula_inicial] + h_score(celula_inicial, destino)
#Criando a Fila:
fila = PriorityQueue()
#Adicionando item na Fila:
item = (f_score[celula_inicial], h_score(celula_inicial, destino), celula_inicial)
fila.put(item)
#Caminhando utilizando a Fila:
while not fila.empty():
celula = fila.get()[2]
#Se a celula for o destino final, interrompe o loop:
if celula == destino:
break
#Verficando as Direções Possíveis:
for direcao in "NSEW":
if labirinto.maze_map[celula][direcao] == 1:
#Posição da célula atual:
linha_celula = celula[0]
coluna_celula = celula[1]
#Calculando a Posição da Próxima Célula:
if direcao == "N":
proxima_celula = (linha_celula - 1, coluna_celula)
elif direcao == "S":
proxima_celula = (linha_celula + 1, coluna_celula)
elif direcao == "W":
proxima_celula = (linha_celula, coluna_celula - 1)
elif direcao == "E":
proxima_celula = (linha_celula, coluna_celula + 1)
#Calculando o g_score da próxima célula:
novo_g_score = g_score[celula] + 1Com o g_score calculado, podemos calcular o f_score das próximas células possíveis, considerando o novo_g_score delas mais o h_score.
def aestrela(labirinto):
#Criar tabuleiro com valores infinitos:
f_score = {celula: float("inf") for celula in labirinto.grid}
#Criar Dicionário g_score:
g_score = {}
#Calcular célula inicial:
celula_inicial = (labirinto.rows, labirinto.cols)
g_score[celula_inicial] = 0
f_score[celula_inicial] = g_score[celula_inicial] + h_score(celula_inicial, destino)
#Criando a Fila:
fila = PriorityQueue()
#Adicionando item na Fila:
item = (f_score[celula_inicial], h_score(celula_inicial, destino), celula_inicial)
fila.put(item)
#Caminhando utilizando a Fila:
while not fila.empty():
celula = fila.get()[2]
#Se a celula for o destino final, interrompe o loop:
if celula == destino:
break
#Verficando as Direções Possíveis:
for direcao in "NSEW":
if labirinto.maze_map[celula][direcao] == 1:
#Posição da célula atual:
linha_celula = celula[0]
coluna_celula = celula[1]
#Calculando a Posição da Próxima Célula:
if direcao == "N":
proxima_celula = (linha_celula - 1, coluna_celula)
elif direcao == "S":
proxima_celula = (linha_celula + 1, coluna_celula)
elif direcao == "W":
proxima_celula = (linha_celula, coluna_celula - 1)
elif direcao == "E":
proxima_celula = (linha_celula, coluna_celula + 1)
#Calculando o g_score da próxima célula:
novo_g_score = g_score[celula] + 1
#Calculando o f_score para a próxima célula:
novo_f_score = novo_g_score + h_score(proxima_celula, destino)Agora podemos fazer a verificação de qual caminho terá o menor custo, ou seja, se o novo_f_score for menor do que o antigo f_score[proxima_celula], vamos atualizar o f_score da próxima célula, atualizar o g_score da próxima célula e adicionar essa célula na nossa fila.
def aestrela(labirinto):
#Criar tabuleiro com valores infinitos:
f_score = {celula: float("inf") for celula in labirinto.grid}
#Criar Dicionário g_score:
g_score = {}
#Calcular célula inicial:
celula_inicial = (labirinto.rows, labirinto.cols)
g_score[celula_inicial] = 0
f_score[celula_inicial] = g_score[celula_inicial] + h_score(celula_inicial, destino)
#Criando a Fila:
fila = PriorityQueue()
#Adicionando item na Fila:
item = (f_score[celula_inicial], h_score(celula_inicial, destino), celula_inicial)
fila.put(item)
#Caminhando utilizando a Fila:
while not fila.empty():
celula = fila.get()[2]
#Se a celula for o destino final, interrompe o loop:
if celula == destino:
break
#Verficando as Direções Possíveis:
for direcao in "NSEW":
if labirinto.maze_map[celula][direcao] == 1:
#Posição da célula atual:
linha_celula = celula[0]
coluna_celula = celula[1]
#Calculando a Posição da Próxima Célula:
if direcao == "N":
proxima_celula = (linha_celula - 1, coluna_celula)
elif direcao == "S":
proxima_celula = (linha_celula + 1, coluna_celula)
elif direcao == "W":
proxima_celula = (linha_celula, coluna_celula - 1)
elif direcao == "E":
proxima_celula = (linha_celula, coluna_celula + 1)
#Calculando o g_score da próxima célula:
novo_g_score = g_score[celula] + 1
#Calculando o f_score para a próxima célula:
novo_f_score = novo_g_score + h_score(proxima_celula, destino)
#Verificando o f_score e atualizando os valores:
if novo_f_score < f_score[proxima_celula]:
f_score[proxima_celula] = novo_f_score
g_score[proxima_celula] = novo_g_score
#atualizando a fila:
item = (novo_f_score, h_score(proxima_celula, destino), proxima_celula)
fila.put(item)Com isso, já conseguimos calcular o f_score de todas as células dentro do nosso labirinto. Nosso agente ainda não irá percorrer o melhor caminho, mas já conseguimos ver o f_score para cada célula.
Se fizermos um print(f_score), teremos como resposta os valores para cada uma das células. E veremos que algumas células ainda terão o valor de infinito; isso acontece porque essas células nem precisaram ser testadas.
Para finalizar, só precisamos armazenar qual o melhor caminho dentre todos que foram verificados. Para isso, fora do nosso while, vamos criar um dicionário chamado caminho que vai começar vazio.
E sempre que adicionarmos um item na fila, iremos adicionar ao nosso dicionário caminho a chave proxima_celula recebendo o valor da célula atual. Isso criará um caminho inverso..
Retomando novamente a aula de criação de labirintos, quando queremos passar um caminho para o nosso agente percorrer dentro do labirinto, precisamos passar para ele um dicionário em que a chave seja a célula atual e o valor seja a célula para a qual ele vai se deslocar.
Inclusive, quando utilizamos o path para descobrir o caminho perfeito, ele nos retorna um dicionário dessa forma, com cada célula e para qual célula deve ir a partir dessa. O caminho que estamos criando será um dicionário contrário; ele terá como chave a próxima célula e como valor a célula anterior.
def aestrela(labirinto):
#Criar tabuleiro com valores infinitos:
f_score = {celula: float("inf") for celula in labirinto.grid}
#Criar Dicionário g_score:
g_score = {}
#Calcular célula inicial:
celula_inicial = (labirinto.rows, labirinto.cols)
g_score[celula_inicial] = 0
f_score[celula_inicial] = g_score[celula_inicial] + h_score(celula_inicial, destino)
#Criando a Fila:
fila = PriorityQueue()
#Adicionando item na Fila:
item = (f_score[celula_inicial], h_score(celula_inicial, destino), celula_inicial)
fila.put(item)
caminho = {}
#Caminhando utilizando a Fila:
while not fila.empty():
celula = fila.get()[2]
#Se a celula for o destino final, interrompe o loop:
if celula == destino:
break
#Verficando as Direções Possíveis:
for direcao in "NSEW":
if labirinto.maze_map[celula][direcao] == 1:
#Posição da célula atual:
linha_celula = celula[0]
coluna_celula = celula[1]
#Calculando a Posição da Próxima Célula:
if direcao == "N":
proxima_celula = (linha_celula - 1, coluna_celula)
elif direcao == "S":
proxima_celula = (linha_celula + 1, coluna_celula)
elif direcao == "W":
proxima_celula = (linha_celula, coluna_celula - 1)
elif direcao == "E":
proxima_celula = (linha_celula, coluna_celula + 1)
#Calculando o g_score da próxima célula:
novo_g_score = g_score[celula] + 1
#Calculando o f_score para a próxima célula:
novo_f_score = novo_g_score + h_score(proxima_celula, destino)
#Verificando o f_score e atualizando os valores:
if novo_f_score < f_score[proxima_celula]:
f_score[proxima_celula] = novo_f_score
g_score[proxima_celula] = novo_g_score
#atualizando a fila:
item = (novo_f_score, h_score(proxima_celula, destino), proxima_celula)
fila.put(item)
caminho[proxima_celula] = celula
return caminhoCom esse dicionário caminho criado, precisamos tratá-lo, pois ele traz todos os caminhos possíveis, e só queremos o melhor caminho.
Vamos criar um dicionário chamado caminho_final, que inicialmente estará vazio. Nesse dicionário, iremos inverter a ordem de chave e valor que estamos recebendo do dicionário caminho. Além disso, excluiremos os caminhos que não são interessantes, ou seja, os caminhos que não representam a melhor rota para o destino, o ponto final do labirinto.
Vamos criar uma variável para a célula analisada que começará recebendo a célula de destino. A partir disso, criaremos um loop em que, enquanto a célula analisada for diferente da célula inicial, iremos inverter a ordem de chave e valor.
Dessa forma, partindo do destino, percorreremos o caminho contrário até o ponto de partida, invertendo o dicionário caminho, ou seja, pegando a chave e transformando em valor, e o valor em chave.
def aestrela(labirinto):
#Criar tabuleiro com valores infinitos:
f_score = {celula: float("inf") for celula in labirinto.grid}
#Criar Dicionário g_score:
g_score = {}
#Calcular célula inicial:
celula_inicial = (labirinto.rows, labirinto.cols)
g_score[celula_inicial] = 0
f_score[celula_inicial] = g_score[celula_inicial] + h_score(celula_inicial, destino)
#Criando a Fila:
fila = PriorityQueue()
#Adicionando item na Fila:
item = (f_score[celula_inicial], h_score(celula_inicial, destino), celula_inicial)
fila.put(item)
caminho = {}
#Caminhando utilizando a Fila:
while not fila.empty():
celula = fila.get()[2]
#Se a celula for o destino final, interrompe o loop:
if celula == destino:
break
#Verficando as Direções Possíveis:
for direcao in "NSEW":
if labirinto.maze_map[celula][direcao] == 1:
#Posição da célula atual:
linha_celula = celula[0]
coluna_celula = celula[1]
#Calculando a Posição da Próxima Célula:
if direcao == "N":
proxima_celula = (linha_celula - 1, coluna_celula)
elif direcao == "S":
proxima_celula = (linha_celula + 1, coluna_celula)
elif direcao == "W":
proxima_celula = (linha_celula, coluna_celula - 1)
elif direcao == "E":
proxima_celula = (linha_celula, coluna_celula + 1)
#Calculando o g_score da próxima célula:
novo_g_score = g_score[celula] + 1
#Calculando o f_score para a próxima célula:
novo_f_score = novo_g_score + h_score(proxima_celula, destino)
#Verificando o f_score e atualizando os valores:
if novo_f_score < f_score[proxima_celula]:
f_score[proxima_celula] = novo_f_score
g_score[proxima_celula] = novo_g_score
#atualizando a fila:
item = (novo_f_score, h_score(proxima_celula, destino), proxima_celula)
fila.put(item)
caminho[proxima_celula] = celula
#Criando o caminho final, a rota perfeita:
caminho_final = {}
celula_analisada = destino
while celula_analisada != celula_inicial:
caminho_final[caminho[celula_analisada]] = celula_analisada #invertendo chave e valor do dicionário caminho
celula_analisada = caminho[celula_analisada] #atualizando para a próxima célula analisada
return caminho_finalDessa forma, nossa função que implementa o algoritmo A Estrela no Python está completa. Se passarmos o caminho_final para o nosso agente, ele será capaz de percorrer o labirinto pela melhor rota possível.
Antes de testarmos nosso código, podemos calcular o total de células presentes no labirinto e quantas células foram analisadas. Assim, conseguimos ter um parâmetro de quão eficiente é utilizar o algoritmo A* para selecionar os melhores caminhos.
Para calcular quantas células foram analisadas, só precisamos, dentro da função A*, adicionar um print(“Células analisadas:”, len(caminho.keys())). Dessa forma, estamos pegando o tamanho das chaves presentes no dicionário caminho, que corresponde ao número de células avaliadas.
E para saber o número total de células do labirinto, só precisamos fazer o mesmo processo ao final do código, mas passando labirinto.maze_map.keys(), que irá calcular quantas chaves existem no dicionário referente ao mapa do labirinto.
Nosso código final ficou da seguinte forma:
from pyamaze import maze, agent
from queue import PriorityQueue
destino = (1, 1)
def h_score(celula, destino):
linhac = celula[0]
colunac = celula[1]
linhad = destino[0]
colunad = destino[1]
return abs(colunac - colunad) + abs(linhac - linhad)
def aestrela(labirinto):
#Criar tabuleiro com valores infinitos:
f_score = {celula: float("inf") for celula in labirinto.grid}
#Criar Dicionário g_score:
g_score = {}
#Calcular célula inicial:
celula_inicial = (labirinto.rows, labirinto.cols)
g_score[celula_inicial] = 0
f_score[celula_inicial] = g_score[celula_inicial] + h_score(celula_inicial, destino)
#Criando a Fila:
fila = PriorityQueue()
#Adicionando item na Fila:
item = (f_score[celula_inicial], h_score(celula_inicial, destino), celula_inicial)
fila.put(item)
caminho = {}
#Caminhando utilizando a Fila:
while not fila.empty():
celula = fila.get()[2]
#Se a celula for o destino final, interrompe o loop:
if celula == destino:
break
#Verficando as Direções Possíveis:
for direcao in "NSEW":
if labirinto.maze_map[celula][direcao] == 1:
#Posição da célula atual:
linha_celula = celula[0]
coluna_celula = celula[1]
#Calculando a Posição da Próxima Célula:
if direcao == "N":
proxima_celula = (linha_celula - 1, coluna_celula)
elif direcao == "S":
proxima_celula = (linha_celula + 1, coluna_celula)
elif direcao == "W":
proxima_celula = (linha_celula, coluna_celula - 1)
elif direcao == "E":
proxima_celula = (linha_celula, coluna_celula + 1)
#Calculando o g_score da próxima célula:
novo_g_score = g_score[celula] + 1
#Calculando o f_score para a próxima célula:
novo_f_score = novo_g_score + h_score(proxima_celula, destino)
#Verificando o f_score e atualizando os valores:
if novo_f_score < f_score[proxima_celula]:
f_score[proxima_celula] = novo_f_score
g_score[proxima_celula] = novo_g_score
#atualizando a fila:
item = (novo_f_score, h_score(proxima_celula, destino), proxima_celula)
fila.put(item)
caminho[proxima_celula] = celula
#Criando o caminho final, a rota perfeita:
caminho_final = {}
celula_analisada = destino
print("Celulas analisadas", len(caminho.keys()))
while celula_analisada != celula_inicial:
caminho_final[caminho[celula_analisada]] = celula_analisada
celula_analisada = caminho[celula_analisada]
return caminho_final
labirinto = maze()
labirinto.CreateMaze()
agente = agent(labirinto, filled=True, footprints=True)
caminho = aestrela(labirinto)
labirinto.tracePath({agente: caminho}, delay=300)
print("Total de celulas", len(labirinto.maze_map.keys()))
labirinto.run()Podemos executá-lo dessa forma, e será gerado um labirinto de 10 por 10, mas também podemos passar os valores para a função maze() e criar um labirinto de 50 por 50, definindo o labirinto como maze(50, 50).
Executando esse código, teremos nosso labirinto gerado, o caminho perfeito percorrido pelo agente preenchido, e os valores de células analisadas e totais.
Nesta aula, guiei vocês passo a passo na criação e aplicação do algoritmo A Estrela no Python para encontrar o melhor caminho em um labirinto..
A aula ficou um pouco mais longa porque exploramos tanto a teoria e lógica por trás do A Estrela quanto a implementação prática do código.
Isso permite que você entenda como os algoritmos de otimização e busca funcionam, sendo capazes de indicar a rota mais eficiente entre dois pontos, algo que aplicativos de mapas e GPS utilizam.
Esse assunto é um pouco mais complicado. Então, sugiro que você dê uma olhada novamente na parte em que criamos os labirintos e repasse toda a aula, seguindo os passos. Isso vai te ajudar a entender melhor como o algoritmo A* funciona.
Para acessar outras publicações de Python, clique aqui!
Expert em conteúdos da Hashtag Treinamentos. Auxilia na criação de conteúdos de variados temas voltados para aqueles que acompanham nossos canais.
Quer sair do zero no Python e virar uma referência na sua empresa? Inscreva-se agora mesmo no Python Impressionador