Eu estava fazendo um curso de IA quando me deparei com este problema no algoritmo A*:
As heurísticas são as seguintes:
N : h(N)
'A': 9,
'B': 10,
'C': 13,
'D': 9,
'E': 17,
'F': 4,
'G': 0,
'H': 9,
'I': 11,
'J': 2,
'K': 5,
'L': 14,
'M': 4,
'N': 6,
'O': 11,
'P': 4,
'Q': 4,
'R': 6,
'S': 12
O nó inicial é 'S' e o nó objetivo é 'G'. Os custos entrenós estão especificados na imagem em vermelho. A resposta oficial é o caminho 'SCDFJG' com custo = 26. A ordem de inspeção do nó é dada como: S,I,C,D,F,H,K,J.
Pelo meu entendimento, a cada etapa escolhemos e expandimos um nó de acordo com o valor da heurística f = g + h, onde g é o custo do movimento do nó 'S' até o nó determinado ao longo do caminho para chegar lá. Para os casos de valor g igual, o desempate deve estar na ordem alfabética dos nós do problema original.
Tentativas falhas
S -> {C,H,I,K}
argmin(f{SC,SH,SI,SK}) = SI
I -> {N,O,L,E}
argmin(f{SIN,SIO,SIL,SIE}) = SIN
.
.
.
path = SINRQG
cost = 36
Seguindo o procedimento acima, tentei A* ponderado (peso W = 3) em que f = g + 3*h, e obtive:
path = SKHFJG
cost = 48
Neste caso a resposta oficial é o caminho SINRQG! Agora, no problema original (w = 1), quando aplico o algoritmo de Dijkstra com f como heurística decisiva no lugar apenas de g, o custo é 26 e a ordem de inspeção é S,I,N,K,H,C ,D,F,J,G. Então, como faço para usar A* manualmente? Depois de algum trabalho consegui obter a versão do código da solução do curso:
from collections import deque
class Graph:
def __init__(self, adjacency_list):
self.adjacency_list = adjacency_list
def get_neighbors(self, v):
return self.adjacency_list[v]
# heuristic function with equal values for all nodes, H[n]
.....
def a_star_algorithm(self, start_node, stop_node):
open_list = set([start_node])
closed_list = set([])
g = {}
g[start_node] = 0
parents = {}
parents[start_node] = start_node
W = 3 #weight
while len(open_list) > 0:
n = None
# Printing open and closed lists
print(f"Open List: {open_list}")
print(f"Closed List: {closed_list}")
for v in open_list:
if n is None or (g[v] + W*self.h(v)[0], v) < (g[n] + W*self.h(n)[0], n):
n = v;
if n is None:
print('Path does not exist!')
return None
if n == stop_node:
reconst_path = []
while parents[n] != n:
reconst_path.append(n)
n = parents[n]
reconst_path.append(start_node)
reconst_path.reverse()
print('Path found:', reconst_path)
return reconst_path
for (m, weight) in self.get_neighbors(n):
if m not in open_list and m not in closed_list:
open_list.add(m)
parents[m] = n
g[m] = g[n] + weight
print(f"Inspecting node {m}")
print(g[m]+W*self.h(m)[0])
else:
if g[m] > g[n] + weight:
g[m] = g[n] + weight
parents[m] = n
if m in closed_list:
closed_list.remove(m)
open_list.add(m)
open_list.remove(n)
closed_list.add(n)
print('Path does not exist!')
return None
# Test your modified A* algorithm
adjacency_list = {
.......
No entanto, acho isso muito desajeitado para entender e implementar manualmente, embora dê a resposta correta.
