搜索法有3种
穷举法（结出所有解，进行判断是否满足给定约束），深度优先搜索和宽度优先搜素。
深度优先搜索思想？
给定图G=(V,E)。深度优先搜索思想：初始时，所有顶点均未被访问过，任选一个顶点v作为源点。该方法先访问源点v，并将其标记标记已访问过（通常用数组visit[i]的值来标记是否访问过）；然后从v出发，选择v的下一个邻结点w，如果w已经访问过，则选择v的另一个邻结点；如果w未访问过，则标记w为以访问过，并已w为新的出发点，继续进行深度优先搜索；如果w及其子节点搜索完毕，则返回到v，在选择它的另外一个未曾访问过的邻结点继续搜索，直到图中所有和源点有路径想通的顶点均已访问过为止；若此时G中任然存在未被访问过的顶点，则另选一个尚未被访问过的顶点作为新的源点重复上述过程，直到图中所有顶点均被访问过为止。
什么是回溯法？
回溯法是在仅给出初始结点，目标结点及产生子节点的条件（一般有问题题意隐含给出）的情况下，构造一个图（隐式图），然后按照深度优先搜索的思想，在有关条件的约束下扩展到目标结点，从而找出问题的解。换言之，回溯法从初始状态出发，在隐式图中以深度优先的方式搜索问题的解。当发现不满足求解条件时，就回溯，尝试其他路径。通俗地讲，回溯法是一种能进则进，进不了则换，换不了则退。
回溯法的算法框架
回溯法是一种搜索方法。用回溯法解决问题时，首先应明确搜索范围，即问题所有可能解组成的范围。这个范围越小越好，且至少包含问题的一个（最优）解。为了定义搜索范围，需要明确以下几个方面：
（1）问题解的形式：回溯法希望问题的解能够表示成一个n元祖（x1,x2,x3,x4...xn）的形式。
（2）显约束：对分量xi(i=1,2...n)的取值范围限定
（3）隐约束：为满足问题的解而对不同分量之间施加的约束
（4）解空间：对于问题的一个实例，解向量满足显约束的所有n元祖构成了该实例的一个解空间。
本文出自 “简答生活” 博客，转载请与作者联系！
原文：http://1464490021.blog.51cto.com/4467028/1845188