Introdução ao Algoritmo A*

O algoritmo A* é uma técnica de busca heurística desenvolvida para encontrar o caminho de custo mínimo em um espaço de estados. Ele combina a completude da busca em largura com a eficiência de heurísticas, sendo amplamente utilizado em planejamento de rotas e inteligência artificial para jogos.

Princípios Fundamentais

O A* direciona a busca usando uma função de avaliação que pondera o custo acumulado e uma estimativa do custo restante:

• Função de avaliação: f(n) = g(n) + h(n)
• Custo real (g): g(n) é o custo do caminho do nó inicial até n.
• Custo heurístico (h): h(n) é o custo estimado de n ao nó objetivo.
• Prioridade: Nós com menor f(n) são expandidos primeiro.

Procedimento Passo a Passo

1. Inicialização:
   • Coloque o nó inicial na lista aberta (open list).
   • Defina g(inicial) = 0 e calcule h(inicial) com uma heurística.
   • Crie uma lista fechada (closed list) para nós visitados.
2. Loop principle:
   • Remova o nó com menor f(n) da lista aberta.
   • Se for o nó objetivo, reconstrua o caminho e termine.
   • Adicione o nó à lista fechada.
   • Expanda seus vizinhos.
3. Expansão de vizinhos:
   • Para cada vizinho:
     • Ignore se já na lista fechada.
     • Calcule novo_g = g(atual) + custo(atual, vizinho).
     • Se o vizinho não está na lista aberta ou novo_g é menor que seu g atual, atualize seus valores e defina o pai.

Formalização Matemática

Dado um grafo ponderado G = (V, E), onde V são vértices, E são arestas, e w(u, v) é o peso da aresta, o A* mantém:

• g(n): custo real do caminho até n.
• h(n): custo heurístico de n ao objetivo.
• f(n) = g(n) + h(n): valor de avaliação.

A busca é ótima se a heurística for admissível, garantindo f(n) ≤ g*(n) + h*(n), onde g* e h* são custos ótimos.

Complexidade

• Pior caso temporal: O(b^d), com fator de ramificação b e profundidade d.
• Caso médio: Depende da qualidade da heurística.
• Espaço: O(b^d) devido à manutenção de listas.

Características

Vantagens

• Encontra soluções ótimas sob heurísticas admissíveis.
• Eficiente ao reduzir espaço de busca.
• Flexível via ajuste de heurísticas.

Desvantagens

• Requer design cuidadoso da heurística.
• Pode consumir muita memória em grandes grafos.
• Susceptível a mínimos locais em alguns casos.

Aplicações Práticas

• IA em jogos para movimentação de personagens.
• Sistemas de navegação GPS.
• Planejamento de trajetórias em robótica.
• Roteamento em redes de computadores.

Código Pseudocódigo

função AlgoritmoAEstrela(início, objetivo, heurística):
    lista_aberta ← nova FilaPrioridade()
    lista_fechada ← novo Conjunto()
    
    início.g ← 0
    início.h ← heurística(início, objetivo)
    início.f ← início.g + início.h
    início.pai ← nulo
    
    lista_aberta.adicionar(início)
    
    enquanto lista_aberta não está vazia:
        atual ← lista_aberta.remover()
        
        se atual == objetivo:
            return reconstruir_caminho(atual)
        
        lista_fechada.adicionar(atual)
        
        para cada vizinho de atual:
            se vizinho em lista_fechada:
                continue
            
            g_tentativa ← atual.g + custo(atual, vizinho)
            
            se vizinho não em lista_aberta ou g_tentativa < vizinho.g:
                vizinho.pai ← atual
                vizinho.g ← g_tentativa
                vizinho.h ← heurística(vizinho, objetivo)
                vizinho.f ← vizinho.g + vizinho.h
                
                se vizinho não em lista_aberta:
                    lista_aberta.adicionar(vizinho)
    
    return falha

Exemplo de Implementação em Python

import heapq

class NoCaminho:
    def __init__(self, coordenada, progenitor=None):
        self.coordenada = coordenada
        self.progenitor = progenitor
        self.custo_acumulado = 0
        self.custo_estimado = 0
        self.avaliacao_total = 0
    
    def __lt__(self, outro):
        return self.avaliacao_total < outro.avaliacao_total

def calcular_rota_a_estrela(matriz, início, fim, heurística):
    nó_início = NoCaminho(início)
    nó_fim = NoCaminho(fim)
    
    lista_aberta = []
    lista_fechada = set()
    
    heapq.heappush(lista_aberta, nó_início)
    
    while lista_aberta:
        nó_atual = heapq.heappop(lista_aberta)
        lista_fechada.add(nó_atual.coordenada)
        
        if nó_atual.coordenada == nó_fim.coordenada:
            caminho = []
            nó_temp = nó_atual
            while nó_temp:
                caminho.append(nó_temp.coordenada)
                nó_temp = nó_temp.progenitor
            return caminho[::-1]
        
        vizinhos = []
        for delta in [(0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]:
            coord_vizinho = (nó_atual.coordenada[0] + delta[0], nó_atual.coordenada[1] + delta[1])
            
            if (0 <= coord_vizinho[0] < len(matriz) and
                0 <= coord_vizinho[1] < len(matriz[0]) and
                matriz[coord_vizinho[0]][coord_vizinho[1]] == 0):
                
                vizinhos.append(NoCaminho(coord_vizinho, nó_atual))
        
        for vizinho in vizinhos:
            if vizinho.coordenada in lista_fechada:
                continue
            
            # Calcular custo de movimento
            if abs(vizinho.coordenada[0] - nó_atual.coordenada[0]) + abs(vizinho.coordenada[1] - nó_atual.coordenada[1]) == 2:
                custo_mov = 1.414
            else:
                custo_mov = 1
            
            vizinho.custo_acumulado = nó_atual.custo_acumulado + custo_mov
            vizinho.custo_estimado = heurística(vizinho.coordenada, nó_fim.coordenada)
            vizinho.avaliacao_total = vizinho.custo_acumulado + vizinho.custo_estimado
            
            # Verificar se já na lista aberta com custo menor
            adicionar = True
            for nó_aberto in lista_aberta:
                if nó_aberto.coordenada == vizinho.coordenada and nó_aberto.custo_acumulado <= vizinho.custo_acumulado:
                    adicionar = False
                    break
            
            if adicionar:
                heapq.heappush(lista_aberta, vizinho)
    
    return []

Funções Heurísticas Comuns

def distância_manhattan(pos1, pos2):
    """Distância Manhattan para movimentos em quatro direções."""
    return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])

def distância_euclidiana(pos1, pos2):
    """Distância Euclidiana para movimentos em oito direções."""
    return ((pos1[0] - pos2[0]) ** 2 + (pos1[1] - pos2[1]) ** 2) ** 0.5

def distância_chebyshev(pos1, pos2):
    """Distância Chebyshev para movimentos de cavalo ou rei."""
    return max(abs(pos1[0] - pos2[0]), abs(pos1[1] - pos2[1]))

def distância_diagonal(pos1, pos2):
    """Distância diagonal para movimentos em oito direções com custos variados."""
    dx = abs(pos1[0] - pos2[0])
    dy = abs(pos1[1] - pos2[1])
    return max(dx, dy) + (1.414 - 1) * min(dx, dy)

Análise do Algoritmo

Propriedades da Heurística

Para garantir otimalidade, a heurística h(n) deve ser:

• Admissível: h(n) ≤ h*(n), onde h* é o custo real ótimo.
• Consistente: h(n) ≤ w(u,v) + h(v) para todos os nós u, v.

Heurísticas comuns incluem Manhattan, Euclidiana e Chebyshev, dependendo do tipo de movimento permitido.

Comparação com Outros Algoritmos

Estratégias de Otimização

• A* bidirecional: Busca simultânea do início e fim.
• Jump Point Search: Otimização para grid maps.
• A* com limite de memória: Restrição de memória para grafos grandes.

Exemplo simplificado de A* bidirecional:

def rota_bidirecional(matriz, início, fim, heurística):
    lista_aberta_direta = []
    lista_aberta_inversa = []
    lista_fechada_direta = set()
    lista_fechada_inversa = set()
    
    nó_início = NoCaminho(início)
    nó_fim = NoCaminho(fim)
    
    heapq.heappush(lista_aberta_direta, nó_início)
    heapq.heappush(lista_aberta_inversa, nó_fim)
    
    while lista_aberta_direta and lista_aberta_inversa:
        # Expandir direção direta
        nó_dir = heapq.heappop(lista_aberta_direta)
        lista_fechada_direta.add(nó_dir.coordenada)
        
        if nó_dir.coordenada in lista_fechada_inversa:
            # Reconstruir caminho combinando as duas buscas
            caminho = []
            # Código para reconstruir caminho omitido por brevidade
            return caminho
        
        # Expandir vizinhos para direção direta (similar ao A* padrão)
        
        # Expandir direção inversa de forma similar
        nó_inv = heapq.heappop(lista_aberta_inversa)
        lista_fechada_inversa.add(nó_inv.coordenada)
        
        if nó_inv.coordenada in lista_fechada_direta:
            # Reconstruir caminho
            return []
    
    return []

Considerações de Implementação

Ao implementar o A*, assegure que a heurística seja admissível para otimalidade. Para problemas de grande escala, considere técnicas de limitação de memória. Trate cuidadosamente a reconstrução do caminho e a atualização de nós na lista aberta para evitar redundâncias.