深度优先搜索在栈中存储一系列开放(例如还未被访问)棋面状态,处理时每次从中取出一个。在例7-3的实现中,闭合集的结构是一个散列表,可以高效地查询是否一个棋面状态已经访问,根据INode对象来计算散列函数的键值、每个棋面状态有一个叫做DepthTransition引用,记录(a)到达这个状态的走法,(b)之前状态,以及(c)从最初位置开始到此的深度。算法会多次复制一个棋面状态,用来尝试各种走法。
例7-3:深度优先搜索实现
例7-3的实现必须关注于闭合集所使用的数据结构,以便高效地得知一个棋面状态是否已经访问。例如,如果闭合集使用的是一个简单的链表,那么在闭合集中搜索一个元素所花费的时间将会占用整个算法花费时间的大部分。注意,当后继状态是目标状态时,搜索算法终止(在广度优先搜索中同样如此)。