==============
A*算法学习笔记
==============

给 A* 算法是最佳的提供了一个简单证明，介绍了在棋类游戏中应用 A* 的一个简单想法。

.. 目录::

算法描述
========

.. code-block:: python

    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* 算法最佳优先的搜索策略时，可以使得效果好的路径得到更深度的搜索。最大搜索深度定义为离起始节点最大路径长度。