当我在 A* 算法中遇到这个问题时，我正在上人工智能课程：
启发式如下：
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
起始节点是“S”，目标节点是“G”。节点间成本在图像中以红色指定。官方答案是路径“SCDFJG”，成本= 26。节点检查的顺序为：S，I，C，D，F，H，K，J。
根据我的理解，在每一步中，我们根据启发式 f = g + h 的值选择和扩展一个节点，其中 g 是沿着到达那里的路径从节点“S”移动到给定节点的成本。对于相等 g 值的情况，平局决胜者应该是原始问题中节点的字母顺序。
失败的尝试
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
按照上述过程，我尝试了加权 A*（权重 W = 3），其中 f = g + 3*h，得到：
path = SKHFJG
cost = 48
在这种情况下，官方答案是路径 SINRQG！现在，在原始问题（w = 1）中，当我应用 Dijkstra 算法并仅用 f 作为决策启发式来代替 g 时，成本为 26，检查顺序为 S,I,N,K,H,C ，D，F，J，G。那么，如何手动使用 A* 呢？经过一番工作后，我可以从课程中获得解决方案的代码版本：
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 = {
.......
然而，我发现这太笨拙了，无法手动理解和实现，尽管它给出了正确的答案。
