基本概念

概念

搜索，也就是对状态空间进行枚举，通过穷尽所有的可能来找到最优解，或者统计合法解的个数。Complete search，我们在学习递归的时候，就了解到了。递归枚举子集，递归枚举组合，递归枚举排列，是三个入门的问题。

在讲到搜索的时候，会有几个概念，<深度优先搜索、深度优先遍历>，<宽度优先搜索、宽度优先遍历>（也叫广度优先搜索）。遍历呢，一般是指图上的搜索。我们在学习搜索的时候，主要是指学习深度优先搜索。

下面这段话，用来理解和区分这几个常用的概念问题。

• depth first search(dfs)， 按照深度优先的顺序对“问题状态空间”进行搜索的算法（理解理解搜索树，是不是深度优先?）。
• “深搜”，是一种包括遍历形式、状态记录与检索、剪枝优化等算法整体设计的统称。提前学习建图方法后，掌握在图上进行遍历，进一步把“问题空间”类比为一张图。
• 研究dfs算法之前，要定义该过程产生的 “搜索树” 结构，整个深搜算法就是基于该搜索树完成的（用递归实现的指数型枚举、排列性枚举、组合型枚举，其实就是深搜的三种最简单的形式）。
• dfs，常常指利用递归函数实现暴力枚举的算法。
• 递归搜索，该类搜索算法的特点在于，将要搜索的目标分成若干“层”，每层基于前几层的状态进行决策，直到达到目标状态。

不要过多纠结于名词概念，能够inplementation才是王道。