from dataclasses import dataclass, field
import heapq
@dataclass
class Produto:
nome: str
categoria: str
taxa_conversao: float # entre 0 e 1
def __hash__(self):
return hash(self.nome)
def __repr__(self):
return f"{self.nome} [{self.categoria}] ({self.taxa_conversao:.0%})"
class SistemaRecomendacaoAStar:
"""Encontra a sequência de produtos mais 'promissora' entre um
produto de partida e um produto-alvo, usando o algoritmo A*."""
def __init__(self, catalogo):
self.catalogo = catalogo
self.conexoes = self._montar_conexoes()
def _montar_conexoes(self):
# Cada produto se conecta a todos os demais do catálogo.
# O custo da aresta é a diferença absoluta entre as taxas
# de conversão: quanto mais parecidas, mais barato o passo.
conexoes = {}
for origem in self.catalogo:
vizinhos = []
for destino in self.catalogo:
if origem is destino:
continue
custo = abs(origem.taxa_conversao - destino.taxa_conversao)
vizinhos.append((destino, custo))
conexoes[origem] = vizinhos
return conexoes
@staticmethod
def _heuristica(produto_atual, produto_alvo):
# Estimativa de quão longe ainda estamos do alvo: quanto mais
# próximas as taxas de conversão, menor a heurística.
return abs(produto_atual.taxa_conversao - produto_alvo.taxa_conversao)
def buscar_melhor_rota(self, origem, destino):
contador = 0 # desempate estável na fila de prioridade
fronteira = [(self._heuristica(origem, destino), contador, origem, 0)]
veio_de = {}
custo_ate_aqui = {origem: 0}
explorados = set()
while fronteira:
_, _, atual, g_atual = heapq.heappop(fronteira)
if atual in explorados:
continue
explorados.add(atual)
if atual == destino:
return self._reconstruir_rota(veio_de, destino)
for vizinho, custo_aresta in self.conexoes[atual]:
novo_g = g_atual + custo_aresta
if vizinho not in custo_ate_aqui or novo_g < custo_ate_aqui[vizinho]:
custo_ate_aqui[vizinho] = novo_g
f = novo_g + self._heuristica(vizinho, destino)
contador += 1
heapq.heappush(fronteira, (f, contador, vizinho, novo_g))
veio_de[vizinho] = atual
return None # não encontrou caminho (não deveria acontecer em grafo completo)
@staticmethod
def _reconstruir_rota(veio_de, destino):
rota = [destino]
while rota[-1] in veio_de:
rota.append(veio_de[rota[-1]])
rota.reverse()
return rota
if __name__ == "__main__":
catalogo = [
Produto("Fone Bluetooth", "Eletrônicos", 0.92),
Produto("Carregador Portátil", "Eletrônicos", 0.81),
Produto("Mochila Notebook", "Acessórios", 0.68),
Produto("Garrafa Térmica", "Casa", 0.55),
]
sistema = SistemaRecomendacaoAStar(catalogo)
origem = catalogo[0] # Fone Bluetooth
destino = catalogo[2] # Mochila Notebook
rota = sistema.buscar_melhor_rota(origem, destino)
print(f"Melhor rota de recomendação entre '{origem.nome}' e '{destino.nome}':")
for produto in rota:
print(" ->", produto)
Para saber mais:
Conte com o apoio da comunidade Alura na sua jornada. Abraços e bons estudos!