深度优先搜索(图7-5)不断地向前寻找可行状态,试图一次找到通向目标状态的道路,它并不会两次访问同一个状态。因为某些搜索树包含大量的棋面状态,因此深度优先搜索只是在最大搜索深度固定的情况下才具有可行性。深度优先搜索维护一个栈,保存未访问过的棋面状态。在每次迭代时,深度优先搜索从栈中弹出一个未访问的棋面状态,然后从这个棋面状态开始扩展,根据走法计算其后继棋面状态。如果达到了目标棋面状态,搜索终止。如果没有达到的话,任何在闭合集中的后继棋面状态都会被抛弃。剩余的未访问棋面状态被压入栈中,然后继续搜索。
图 7-5 深度优先搜索详解在一个八数码问题中,从初始棋面状态开始,限定最大深度为9,我们可以得到一棵搜索树,如图7-6所示。我们从图中可以看到,虽然有些地方已经扩展到深度9,但是我们找到的解只需经过8步。在这棵树中,我们已经访问了50个棋面状态,还剩下4个未访问(浅灰色表示)。
图 7-6 八数码问题的深度优先搜索树输入/输出
输入
算法从一个初始棋面状态开始,寻找一个目标状态。算法假设在给定棋面状态下可以尝试所有的可行走法。
输出
返回一个走法的序列,表示从初始状态到目标状态的路径(或者只是输出是否存在一个解)。
假设
为了分析方便,我们假设d为深度优先搜索的最大深度,d为搜索树的分支因子。