深度优先搜索算法（回溯法）入门

搜索算法

搜索是人工智能中的一种基本方法，是一项非常普遍使用的算法策略，能够解决许许多多的常见问题，在某些情况下我们很难想到高效的解法时，搜索往往是可选的唯一选择。按照标准的话来讲：搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。

搜索虽然简单易学易于理解，但要掌握好并写出速度快效率高优化好的程序却又相当困难，总而言之，搜索算法灵活多变，一般的框架很容易写出，但合适的优化却要根据实际情况来确定。在搜索算法中，深度优先搜索（也可以称为回溯法）是搜索算法里最简单也最常见的，今天我们就从这里讲起，下面的内容假设读者已经知道最基本的程序设计和简单的递归算法。

产生式系统和搜索树

所有的搜索算法从其最终的算法实现上来看，都可以划分成两个部分──控制结构和产生系统。正如前面所说的，搜索算法简而言之就是穷举所有可能情况并找到合适的答案，所以最基本的问题就是罗列出所有可能的情况，这其实就是一种产生式系统。

我们将所要解答的问题划分成若干个阶段或者步骤，当一个阶段计算完毕，下面往往有多种可选选择，所有的选择共同组成了问题的解空间，对搜索算法而言，将所有的阶段或步骤画出来就类似是树的结构（如图）。

从根开始计算，到找到位于某个节点的解，回溯法（深度优先搜索）作为最基本的搜索算法，其采用了一种“一只向下走，走不通就掉头”的思想（体会“回溯”二字），相当于采用了先根遍历的方法来构造搜索树。

上面的话可能难于理解，没关系，我们通过基本框架和例子来阐述这个算法，你会发现其中的原理非常简单自然。

 

回溯（深度优先搜索）基本框架

函数DFS（节点）

{

如果（节点=目标节点） {找到目标，跳出}

遍历所有下一层节点

{

DFS（下一层的节点）

}

}

例：跳马

如图，在7*5的棋盘上，左下角有一个马，现在要该马条至右上角位置，请求出所有可行路径，图中绘出了一条可行路径。规定：马只能跳“日”字格，且只能向右跳。

分析：

我们把马跳的每一部划分为一个阶段，可以看出，每个阶段接下来都（至多）有两种可行选择，即向右上跳或右下跳，对每种情况的遍历又再会产生两种选择，直到遍历到目标点。然后“回溯”，即从上一阶段的另一选择继续，直至遍历完所有可能情况。当判断到目标点时，需要记录该条可行路径。

具体程序思路如下：

函数DFS（位置）

{

如果（位置不合法，出边界） {跳出}

如果（位置=目标位置） {记录路径，跳出}

DFS（右上）

DFS（右下）

}

可以看出，这个问题我们完全按照框架结构来套用即可。读者请自行完成。

基本练习

寻找路径

如图，在9*4的矩形方格阵中，左下角有一个红色方块，现在要把它移动到右上角，每次可向上或向右移动一步，请求出所有可行路径的总数。

问题

1．马的遍历

对于例子中的跳马问题，我们要求把马跳到右上角即可。现在我们要求将该马走遍棋盘的每个位置，并且每个位置只能走一次，这样的路径是否存在？如果存在，求出所有可行的路径数。

2．排列组合

给定N，M（N，M<7），求出A（N，M）和C（N，M），并打印所有数字。注意每个数的保存方法以及组合数中重复情况的判断。

3．八皇后问题

[经典问题]

在8*8的棋盘上，放置8个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。

4．迷宫最短路径

[经典问题]

[最短路径的应用非常广泛。]

给定迷宫地图，求出最短的一条通路。搜索不是唯一的解法，注意用搜索解决时不要走着走着又倒回来了……-_-

5．简单的0-1背包

[经典问题]

[0-1背包问题的应用也非常广泛，这里只是一种最简单情况。]

有一个背包容量为v（v<100），同时有n个物品(n<10)，每个物品有一个体积 。要求从 n个物品中，任取若干个装入包内，使背包的剩余空间为最小。注意，物品只有装（1）或者不装（0）两种状态。

思考

递归改写

我们知道，所有的递归算法都可以改写成非递归算法，方法就是自己来保存递归时需要的某些信息。请读者思考标准的回溯法改写成非递归算法该是什么样，体会回溯时具体该记录些什么信息。

动态规划

诸如跳马、寻找路径、0-1背包等问题高效的解法是使用动态规划。想一想，这些问题怎样用动态规划来解决？为什么搜索也可解决？为什么使用动态规划要比普通的搜索高效？回溯法有什么弊端？

 

总结

 

搜索算法是我们解决问题中很容易想到的算法，虽然可能不是最优算法，但合理的运用和优化依然能提供一种可行的解决方案。

回溯算法可用于找可行解或所有解以及最优解，是一种常见的通用解法。回溯算法采用不断深入的思想，直至无法前进或找到结果。但在解空间很大的情况下，回溯法会耗费大量时间，很多时候我们要限制深度并提前判断不可能情况及时跳出，借此来提高回溯效率。这属于搜索优化的内容，在此不再赘述。值得一提的是回溯法消耗空间非常有限，相对于广度优先来说，回溯的空间占用要少得多，时间和空间的矛盾是算法设计中常见的矛盾，怎样选择取决于实际情况。

 

延伸阅读

 

广度优先搜索（BFS）

双向广度优先搜索

记忆化搜索

启发式搜索(A*)

剪枝的有关技术

任何一本算法设计或分析的书