这个特定版本的 A-star 算法是如何工作的（手工操作，而不是在 PC 上使用代码）？

当我在 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 = {
.......

然而，我发现这太笨拙了，无法手动理解和实现，尽管它给出了正确的答案。