Algoritmo A* (A Estrela)

Explicação Teórica

O Algoritmo A* (lê-se A-Estrela) é um algoritmo de busca em grafos que utiliza funções heurísticas. É amplamente utilizado em problemas de busca, devido à sua eficiência. O objetivo principal do algoritmo é encontrar o caminho mais curto entre dois pontos em um grafo.

O custo total de um nó é dado pela soma de duas funções:

g(x): O custo real do nó inicial até o nó atual.
h(x): A função heurística que estima o custo do nó atual até o nó de destino.
Portanto, a função de custo total (f(x)) é dada por: f(x) = g(x) + h(x)

O Algoritmo A* utiliza essa função de custo para escolher os próximos nós a serem explorados na busca pelo caminho mais curto.

Principais Características

Busca de Melhor-Primeiro: O A* é uma combinação entre a busca de custo uniforme e a heurística de melhor primeiro. O nó com o menor custo total estimado até o momento é expandido.

Função de Avaliação:

Utiliza uma função de avaliação que combina o custo real do caminho percorrido até o momento e uma heurística que estima o custo do caminho restante até o destino.

Eficiente:

Em muitos casos, o A* é mais eficiente que a busca cega, como a busca em largura ou em profundidade, pois utiliza informações adicionais sobre o problema para orientar a busca.

Introdução ao problema

Imagine que queremos encontrar o caminho mais curto para viajar por algumas cidades em São Paulo, com o objetivo final de chegar a uma cidade específica.
Cada cidade possui uma distância (em quilômetros) até as outras cidades, fornecendo um contexto realista para aplicar o algoritmo A*.

Grafo utilizado no desenvolvimento

Desenvolvmemos um Algoritimo em Python para resolução desse problema o repositorio do projeto se encontra aqui:
https://github.com/CristianoMafraJunior/A_Estrela

Explicação da solução:

class A_Estrela:
    def __init__(self):
        self.cidades = {
            "Araçatuba": {"Votuporanga": 127, "Novo Horizonte": 183, "Marília": 170},
            ...
        }

   self.heuristica = {
            "São Paulo": 0,
            "Santos": 50,
            ...
      }

Inicialização da Classe A_Estrela

cidades: Um dicionário que representa o grafo das cidades e as distâncias entre elas. Cada cidade tem como valor outro dicionário, onde as chaves são cidades vizinhas e os valores são as distâncias para essas cidades vizinhas.

heuristica: Um dicionário que representa a estimativa de distância (heurística) de cada cidade até o destino final (São Paulo).

Método a_estrela:

def a_estrela(self, inicio, destino):
        fila_prioridade = []
        heapq.heappush(fila_prioridade, (0, inicio))
        visitados = set()
        caminho_percorrido = {inicio: None}
        custo_total = {cidade: float("inf") for cidade in self.cidades}
        custo_total[inicio] = 0

        while fila_prioridade:
            custo_atual, cidade_atual = heapq.heappop(fila_prioridade)

            if cidade_atual == destino:
                caminho = self.reconstruir_caminho(
                    caminho_percorrido, destino, custo_total
                )
                return custo_total[destino], caminho

            if cidade_atual in visitados:
                continue

            visitados.add(cidade_atual)

            for vizinho, custo in self.cidades[cidade_atual].items():
                novo_custo = custo_total[cidade_atual] + custo
                custo_heuristica = self.heuristica[vizinho]
                if novo_custo < custo_total[vizinho]:
                    custo_total[vizinho] = novo_custo
                    heapq.heappush(
                        fila_prioridade, (novo_custo + custo_heuristica, vizinho)
                    )
                    caminho_percorrido[vizinho] = cidade_atual

        return float("inf"), []

Fila de Prioridade: fila_prioridade é uma fila de prioridade (min-heap) usada para sempre expandir o nó com o menor custo estimado (custo real + heurística). Inicialmente, ela contém o nó inicial com custo 0.

Conjuntos e Dicionários:

visitados: Um conjunto para rastrear as cidades já visitadas.
caminho_percorrido: Um dicionário para manter o caminho percorrido até cada cidade.

custo_total: Um dicionário para manter o menor custo encontrado até cada cidade. Inicialmente, todos os custos são definidos como infinito (float("inf")), exceto o custo da cidade inicial, que é 0.

Loop Principal: Enquanto houver cidades na fila de prioridade:

Remove a cidade com o menor custo estimado da fila.

Se essa cidade é o destino, reconstrói o caminho usando reconstruir_caminho e retorna o custo total e o caminho.

Se a cidade já foi visitada, pula para a próxima iteração.

Marca a cidade como visitada e avalia seus vizinhos.

Calcula o novo custo para cada vizinho e, se for menor que o custo previamente registrado, atualiza o custo total, adiciona o vizinho na fila de prioridade com o novo custo estimado e registra o caminho percorrido.

Método reconstruir_caminho:

def reconstruir_caminho(self, caminho_percorrido, destino, custo_total):
    caminho = []
    cidade = destino
    while cidade is not None:
        caminho.append((cidade, custo_total[cidade], self.heuristica[cidade], custo_total[cidade] + self.heuristica[cidade]))
        cidade = caminho_percorrido[cidade]
    return list(reversed(caminho))

Reconstrução do Caminho:

Reconstrói o caminho desde o destino até o início, usando o dicionário caminho_percorrido. Cada cidade é registrada junto com seu custo atual, heurística e custo total (custo + heurística). O caminho é invertido no final para obter a ordem correta (do início ao destino).