解决方案

A*搜索在开放集合中存储棋面状态,所以能够高效地删除评价值最小的棋面状态。在深度优先搜索和广度优先搜索中,A*搜索查看是否已经达到目标状态的方式只是有些许不同。我们回忆一下,深度优先搜索和广度优先搜索会检查棋面状态是什么时候生成的。尤其,A*搜索在从开放集合中删除元素时,会检查是否已经达到目标状态,这样做的目的是确保得到的解是最短路径。例7-5是A*搜索的Java实现。

例7-5:A*搜索实现

阅读 ‧ 电子书库
阅读 ‧ 电子书库

在深度优先搜索和广度优先搜索中,棋面状态都会在处理之后放入闭合集中。由于A*搜索的启发式信息需要计算g*(n),所以可能存在一种情况,这种情况下,A*搜索需要重新评价已经做出的决定。比如,如果存在一个将要被放入开放集合的棋面状态,其评估分数要比已经访问过的相同棋面状态评估函数低。这样,A*搜索会将这个状态从闭合集中删除,因为我们可能能够得到一个最小耗费的解。

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

每个棋面状态都存储了一个后链,叫做DepthTransition,记录的是(a)生成此棋面状态的走法,(b)之前的状态以及(c)初始位置开始的深度。在A*搜索中,g*(n)通常当作深度。算法多次复制一个棋面状态,用来尝试各种走法。