Uma implkementação de A* para exercício
import heapq
class Produto:
def __init__(self, nome, categoria, probabilidade):
self.nome = nome
self.categoria = categoria
self.probabilidade = probabilidade
def __repr__(self):
return self.nome
class AStarRecommendation:
def __init__(self, grafo):
self.grafo = grafo
def buscar(self, inicio, objetivo):
fila = []
heapq.heappush(
fila,
(
heuristica(inicio), # f(n)
0, # g(n)
[inicio]
)
)
melhor_custo = {
inicio: 0
}
while fila:
_, custo_atual, caminho = heapq.heappop(fila)
no_atual = caminho[-1]
if no_atual == objetivo:
return caminho, custo_atual
for vizinho, custo_aresta in self.grafo.get(no_atual, []):
novo_custo = custo_atual + custo_aresta
if ( vizinho not in melhor_custo or novo_custo < melhor_custo[vizinho] ):
melhor_custo[vizinho] = novo_custo
f = novo_custo + heuristica(vizinho)
novo_caminho = caminho + [vizinho]
heapq.heappush(
fila,
(
f,
novo_custo,
novo_caminho
)
)
return None, None
def heuristica(produto):
return 1 - produto.probabilidade
produto1 = Produto(
"Produto 1",
"Categoria A",
0.50
)
produto2 = Produto(
"Produto 2",
"Categoria B",
0.40
)
produto3 = Produto(
"Produto 3",
"Categoria C",
0.70
)
produto4 = Produto(
"Produto 4",
"Categoria D",
0.85
)
grafo = {
produto1: [
(produto2, 3),
(produto3, 2)
],
produto2: [
(produto4, 4),
(produto3, 2)
],
produto3: [
(produto1, 1),
(produto2, 2)
],
produto4: []
}
recomendador = AStarRecommendation(grafo)
caminho, custo = recomendador.buscar( produto1, produto4 )
print("Caminho:", caminho)
print("Custo:", custo)
Conte com o apoio da comunidade Alura na sua jornada. Abraços e bons estudos!