我在学习人工智能课程时，遇到了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}) = SII -> {N,O,L,E}argmin(f{SIN,SIO,SIL,SIE}) = SIN...path = SINRQGcost = 36按照上述程序，我尝试了加权A*算法（权重W = 3），其中f = g + 3*h，结果如下：
path = SKHFJGcost = 48在这种情况下，官方答案是路径SINRQG！现在，在原始问题中（w = 1），当我使用Dijkstra算法并将f作为决定性启发式函数而不是仅使用g时，成本为26，检查顺序为S,I,N,K,H,C,D,F,J,G。那么，我该如何手动使用A*算法呢？经过一些工作，我从课程中得到了代码版本的解决方案：
from collections import dequeclass Graph: def __init__(self, adjacency_list): self.adjacency_list = adjacency_list def get_neighbors(self, v): return self.adjacency_list[v] # 启发式函数，对于所有节点的值相等，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 #权重 while len(open_list) > 0: n = None # 打印开放和关闭列表 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# 测试你的修改后的A*算法adjacency_list = {.......然而，我发现手动理解和实现这个算法太过繁琐，尽管它给出了正确的答案。
回答：
A*星算法从不丢弃它已经扩展的路径。任何这些路径——无论长短——都会通过它们的f值与新路径竞争。
显然，你在书面分析中没有这样做：
S -> {C,H,I,K}argmin(f{SC,SH,SI,SK}) = SII -> {N,O,L,E}argmin(f{SIN,SIO,SIL,SIE}) = SIN...path = SINRQGcost = 36
是的，S扩展到C,H,I,K，这些节点的g、h和f值如下：
| 节点 | g | h | f=g+h |
|---|---|---|---|
| SI | 6 | 11 | 17 |
| SC | 6 | 13 | 19 |
| SK | 16 | 5 | 21 |
| SH | 16 | 9 | 25 |
你是对的，现在节点I扩展到SIN,SIO,SIL,SIE，但你不应该丢弃SC,SK和SH：它们仍然在“竞争”中！所以我们得到以下结果：
| 节点 | g | h | f=g+h |
|---|---|---|---|
| SC | 6 | 13 | 19 |
| SK | 16 | 5 | 21 |
| SIN | 16 | 6 | 22 |
| SH | 16 | 9 | 25 |
| SIO | 30 | 11 | 41 |
| SIL | 30 | 14 | 44 |
| SIE | 30 | 17 | 47 |
因此，下一个要扩展的节点不是N（通过SIN），而是C（通过SC），这与预期的节点检查顺序（S,I,C,…）一致。
如果你继续这样做，从不丢弃路径，除了被其扩展替代的路径，那么你将得到预期的结果。
