A*搜索在开放集合中存储棋面状态，所以能够高效地删除评价值最小的棋面状态。在深度优先搜索和广度优先搜索中，A*搜索查看是否已经达到目标状态的方式只是有些许不同。我们回忆一下，深度优先搜索和广度优先搜索会检查棋面状态是什么时候生成的。尤其，A*搜索在从开放集合中删除元素时，会检查是否已经达到目标状态，这样做的目的是确保得到的解是最短路径。例7-5是A*搜索的Java实现。
例7-5：A*搜索实现
在深度优先搜索和广度优先搜索中，棋面状态都会在处理之后放入闭合集中。由于A*搜索的启发式信息需要计算g*(n)，所以可能存在一种情况，这种情况下，A*搜索需要重新评价已经做出的决定。比如，如果存在一个将要被放入开放集合的棋面状态，其评估分数要比已经访问过的相同棋面状态评估函数低。这样，A*搜索会将这个状态从闭合集中删除，因为我们可能能够得到一个最小耗费的解。
每个棋面状态都存储了一个后链，叫做DepthTransition，记录的是（a）生成此棋面状态的走法，（b）之前的状态以及（c）初始位置开始的深度。在A*搜索中，g*(n)通常当作深度。算法多次复制一个棋面状态，用来尝试各种走法。