Senhores(as), espero que estejam bem!

Notei algo interessante no código: no início criamos grafos todos interconectados, ou seja, todo nó se conecta a todos os nós vizinhos, correto? Porém, na resposta do exercício que o professor passou — que no caso seria de A até C — o algoritmo escolheu o melhor caminho sendo A → B → C.

A cada nó visitado, ele adiciona 1 no G e faz a soma com o número negativo de H para obter o f. Até aqui tudo bem. Entretanto, o melhor caminho não seria esse, já que A se liga diretamente a C. Analisando o código, descobri a causa: é a má configuração da heurística. Como a heurística é negativa, as contas na fórmula não assumem o caminho mais rápido. Vou demonstrar como isso acontece no exemplo.

Situação inicial

Início: Produto A (0.9)

Objetivo: Produto C (0.7)

Heurística = -conversao_probabilidade

Ou seja:

h(A) = -0.9

h(B) = -0.8

h(C) = -0.7

h(D) = -0.6

Primeira expansão (partindo de A)

Fila inicial: [( -0.9, g=0, A )]

Expande A → vizinhos = B, C, D.

Cálculo de f = g + 1 + h:

Para B: f = 0 + 1 + (-0.8) = 0.2

Para C: f = 0 + 1 + (-0.7) = 0.3

Para D: f = 0 + 1 + (-0.6) = 0.4

Fila: [(0.2, g=1, B), (0.3, g=1, C), (0.4, g=1, D)]

Observação: Como podem ver, B vai para o começo da fila como nó a ser expandido. Porém, A já havia encontrado C. Então, por que não parou aí? Isso acontece porque o A* escolhe sempre o nó com o menor f. Por apenas 0.1, C não foi escolhido.

Segunda expansão (a partir de B)

Expande B → vizinhos = A, C, D (mas A já foi visitado).

Para C via B: f = g(=1) + 1 + h(C)(-0.7) = 1.3

Para D via B: f = 1 + 1 + (-0.6) = 1.4

Fila: [(0.3, g=1, C), (0.4, g=1, D), (1.3, g=2, C), (1.4, g=2, D)]

Terceira expansão

Agora o próximo menor f é o Produto C (0.3).
Esse é o objetivo, então o algoritmo para.

Recuperando o caminho

O dicionário de caminhos guarda:

B veio de A

C veio de B

Então o caminho reconstruído é: A → B → C

Analogia com o carrinho de sorvete

Imagine o seguinte:

Você tem duas opções de ponte para chegar até o carrinho de sorvete (C).

Ponte B: mais curta (200m), mas que leva a um desvio de 1000m depois.

Ponte C: mais longa no início (300m), mas vai direto ao objetivo.

O algoritmo, por causa da heurística incorreta, escolhe expandir primeiro a Ponte B e acaba chegando ao caminho mais longo.

Por que isso acontece?

Isso ocorre por um fator principal: a definição incorreta da heurística. Assim, o algoritmo encontra um caminho válido, mas não o ótimo.

No A*, para garantir que o primeiro caminho encontrado seja o ótimo, a heurística precisa ser:

Admissível: nunca superestimar o custo real até o objetivo.

Consistente: obedecer à desigualdade triangular dos custos.

No caso, como usamos:

return -produto.conversao_probabilidade

isso não representa um custo até o objetivo, mas apenas uma ordenação de preferência.

Resultado: a heurística não é admissível nem consistente, então o A* pode encontrar caminhos não ótimos (como A → B → C em vez de A → C).

Como resolver?

Se a ideia é encontrar o caminho mais curto em número de passos (arestas do grafo):

def heuristica(produto):
return 0

Isso transforma o A* em um Dijkstra, garantindo sempre o caminho mais curto.

Se quiser usar algo parecido com “distância real”:
Por exemplo, se fossem produtos em categorias, a heurística poderia ser baseada na distância entre categorias.

def heuristica(produto, objetivo):
# Heurística baseada na categoria
if produto.categoria == objetivo.categoria:
return 0
else:
return 1

E se fosse para continuar com o exemplo do professor porém de maneira corrigida seria alterando essa parte:

caminho = []
produto = objetivo
while produto in caminhos:
caminho.insert(0, produto)
produto = caminhos[produto]
return caminho

Não deu para colocar a solução completa, coloco no comentário abaixo.

Código com solução compelta para terceira solução:
import heapq

class Produto:
def init(self, nome, categoria, conversao_probabilidade):
self.nome = nome
self.categoria = categoria
self.conversao_probabilidade = conversao_probabilidade

def __lt__(self, other):
    # Necessário para que o heapq possa comparar Produtos em caso de empate de prioridade
    return self.nome < other.nome

def __repr__(self):
    return f"{self.nome} (Categoria: {self.categoria}, Prob: {self.conversao_probabilidade})"

class AStarRecommendation:
def init(self, produtos, heuristica):
self.produtos = produtos
self.heuristica = heuristica # Função heurística: probabilidade de conversão
self.grafo = self.criar_grafo()

def criar_grafo(self):
    # Criando um grafo simplificado de produtos, onde cada produto se conecta a todos os outros
    grafo = {}
    for produto in self.produtos:
        grafo[produto] = [p for p in self.produtos if p != produto]
    return grafo

def a_star(self, inicio, objetivo):
    fila_prioridade = []
    # A tupla na heap agora é (f_score, g_score, produto)
    heapq.heappush(fila_prioridade, (0 + self.heuristica(inicio), 0, inicio))  # f = g + h
    
    # Dicionário para reconstruir o caminho
    caminhos = {inicio: None}
    
    # Dicionário para armazenar o custo (g_score) do início até cada nó
    g_score = {produto: float('inf') for produto in self.produtos}
    g_score[inicio] = 0

    while fila_prioridade:
        _, g, atual = heapq.heappop(fila_prioridade)

        # Se chegamos ao objetivo, podemos parar e reconstruir o caminho
        if atual == objetivo:
            # --- INÍCIO DA CORREÇÃO ---
            caminho_final = []
            produto_atual = objetivo
            while produto_atual is not None:
                caminho_final.insert(0, produto_atual)
                produto_atual = caminhos[produto_atual]
            return caminho_final
            # --- FIM DA CORREÇÃO ---

        for vizinho in self.grafo[atual]:
            # O custo para ir de um produto a outro é sempre 1
            tentativa_g_score = g + 1

            # Se encontrarmos um caminho melhor para o vizinho
            if tentativa_g_score < g_score[vizinho]:
                caminhos[vizinho] = atual
                g_score[vizinho] = tentativa_g_score
                h = self.heuristica(vizinho)
                f_score = tentativa_g_score + h
                heapq.heappush(fila_prioridade, (f_score, tentativa_g_score, vizinho))

    # Retorna uma lista vazia se não houver caminho
    return []

def heuristica(produto):
# Quanto maior a probabilidade de conversão, mais atraente é o produto
# Retornamos o negativo porque a fila de prioridade é uma min-heap (busca o menor valor)
return -produto.conversao_probabilidade

Exemplo de produtos

produtos = [
Produto("Produto A", "Categoria 1", 0.9),
Produto("Produto B", "Categoria 1", 0.8),
Produto("Produto C", "Categoria 2", 0.7),
Produto("Produto D", "Categoria 2", 0.6),
]

Criando o sistema de recomendação

recomendador = AStarRecommendation(produtos, heuristica)

Buscar o melhor caminho entre dois produtos

inicio = produtos[0] # Produto A
objetivo = produtos[2] # Produto C

caminho_recomendado = recomendador.a_star(inicio, objetivo)

Exibindo a recomendação

if caminho_recomendado:
print("Caminho recomendado:")
for p in caminho_recomendado:
print(f" -> {p}")
else:
print(f"Não foi possível encontrar um caminho de {inicio.nome} para {objetivo.nome}")