相关算法

虽然A*搜索产生了最小耗费的解,但是搜索空间可能会过大以至于无法继续计算。增强A*搜索和处理这些巨大规模的问题的改进思想主要包括:

迭代加深

这个策略重复迭代有深度限制的深度优先搜索,每次迭代都会增加深度限制。这种方法能够选择出在下次迭代中优先被处理的节点,因此减少了不必要的搜索,增加了快速收敛到获胜走法的可能性。同时,由于搜索空间被切分成离散的部分,实时算法能够在尽可能多的空间限制下,在时限内寻找到一个较优解。最先应用到A*搜索算法的是Korf(1985),他发明了IDA*。

广告:个人专属 VPN,独立 IP,无限流量,多机房切换,还可以屏蔽广告和恶意软件,每月最低仅 5 美元

转移表

为了避免重复计算,程序员可以对局面状态进行散列,在一个转移表中存储路径长度。如果状态在后面的搜索中会出现,而且当前深度大于先前的深度,那么搜索将会终止。这种方法能够避免搜索一棵低效的子树。

层次化

如果局面状态能够层次化地表示,那么我们可以重新构建一下搜索空间。层次化寻路A*(HPA*)就应用了这种方法(Botea等,2004)。

内存限制

与其在计算时限制搜索空间,程序员可以执行一种“有损”搜索,在搜索的过程中舍弃一些节点,专注于搜索那些被认为和结果相关的区域。简化内存限制A*(SMA*)就是一个例子(Russel,1992)。

Reinefeld和Marsland(1994)总结了一系列的A*的有趣的扩展。更多的在AI系统中使用A*搜索的信息在教科书和大量的在线资源可以找到相关信息(Barr和Feigenbaum,1981)。