算法描述

from heapq import heappop,heappush
openset = [start]
closeset = set()
while openset:
    node = heappop(openset)
    if node==target:
        return node
    if node.pos in closeset:
        continue
    closeset.add(node.pos)
    for child in node.children():
        child.hsrc = node.hsrc + 1
        child.htarget = calc_hvalue(child, target)
        child.hvalue = child.hsrc + child.htarget
        # sort by hvalue
        heappush(openset, child)

其中 calc_hvalue 计算节点到目标最短路径长度的估计值，其结果 <= 实际的最短路径长度。

简单证明

定理：A* 算法找到的第一条路径就是最短路径

证明(反证法)：

假设通过A*算法首先找到了路径 p 来到终点，而 p 并非真正的最短路径；

那么根据算法描述， target.hvalue==len(p) ；

再假设真正最短路径A为：n1,n2,n3,...,ni,...,nm，那么A中必有节点还在 openset 中未被访问，假设离起点最远的一个节点为 ni；

首先按照算法对启发函数的要求 ni.hvalue<=len(A)<len(p)=target.hvalue ，也就是说 ni.hvalue<target.hvalue ，按照算法描述，应该先访问 ni 节点而不是 target 节点；

产生矛盾，故原算法正确。

将 A* 算法应用到棋类游戏的一个想法

一般的棋类游戏搜索树中，节点之间路径没有权重，所以通常采用深度优先算法配合 alpha-beta 剪枝，这样存在的一个问题就是所有路径都是搜索相同的深度。按照正常的思维方式，对于初期看起来好的路径完全应该加大搜索的深度。

按照局面的静态评估值对节点之间路径设置权重，局面越有利则路径越短，这样当采用 A* 算法最佳优先的搜索策略时，可以使得效果好的路径得到更深度的搜索。最大搜索深度定义为离起始节点最大路径长度。