如何手动执行该特定版本的A*算法以得到正确路径？

问题背景 #

在AI课程学习中遇到如下A*算法问题：

启发式函数值 #

起始节点为S，目标节点为G，节点间代价标注在图中的红色数字内。官方给出的正确路径为SCDFJG，总代价为26，节点检查顺序为：S, I, C, D, F, H, K, J。

按规则，每一步需依据启发式函数 f = g + h 选择并扩展节点：

• g 表示从起始节点S到当前节点的路径代价
• 若g值相同，按节点字母顺序作为平局决胜规则

手动执行的问题 #

普通A*（W=1）的失败尝试 #

手动执行步骤如下：

S -> {C, H, I, K}
argmin(f{SC, SH, SI, SK}) = SI
I -> {N, O, L, E}
argmin(f{SIN, SIO, SIL, SIE}) = SIN
...
最终路径：SINRQG，总代价：36

但该结果与官方给出的正确路径不符。

加权A*（W=3）的尝试 #

使用加权A*（f = g + 3*h）手动执行后，得到结果：

路径：SKHFJG，总代价：48

但此时官方给出的正确路径为SINRQG。

另外，在原问题（W=1）中用Dijkstra算法，以f替代g作为决策启发式，得到的代价为26，节点检查顺序为S, I, N, K, H, C, D, F, J, G。

课程提供的解决方案代码 #

从课程中获取的解决方案代码如下：

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]

    # 启发式函数，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*算法？

内容的提问来源于stack exchange，提问作者Awe Kumar Jha