A*算法学习笔记

2010-03-07 黄毅

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

算法描述

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


blog comments powered by Disqus

转载请注明出处,收藏或分享这篇文章到: