搜索入门
-
深度优先搜索。
所谓深度优先搜索，其实就是一种顺序枚举。对于某一个问题，找出所有可能的可行解，最朴素的方式，就是枚举每一种可能的解，判断该解是否可行，或者与之前的解相比较，找出一个最优解。这就是深搜该做的事情。
当然在解决实际问题的过程中，我们有时并不需要尝试所有可能的状态，所以可以通过一些条件，去除某一类对解决问题没有帮助的状态，而提高程序运行的效率，这种方法称为剪枝，不过现在各位记住这个名词就行了，我们稍后在讨论这个问题。
让我们首先看一下《啊哈，算法》里面的例题：求1-9的全排列。
123456789
由于篇幅问题，我们简化一下，求3的全排列。
接下来我来模拟一下，深度优先搜索，将会用怎样的策略，求出三的全排列，也就是说，找出123这三个数字进行排列，所有可能的方式。
首先我们知道，这个问题之中，一共有三个数位，每一个数位上的数字，可能有1，2，3这三种可能。让我们先确定一下枚举的顺序。对于整个问题，我们从百位尝试到各位，对于每一位，我们从1枚举到3.
第一步，显然，是在第一位上，填上数字1：
-
1
X
X
对于这种状态，百位上的数已经暂时确定了，为了得到结果，我们现在向十位进行枚举。
-
1
1
X
确定好十位之后，我们再去个位。
-
1
1
1
这样的话，我们就得到了一个解，然而这个解是不可行的，因为全排列中，一个数不可以出现多次，数字1出现3次，不是一个可行解，于是我们继续枚举个位。
-
1
1
2
1还是出现了两次，不可行。继续
-
1
1
3
1还是出现了两次，不可行。继续
至此，在百位为1，十位为1的状态，已经被我们枚举完了，于是我们退一步，回到十位。
-
1
2
X
接下我们继续枚举各位：
-
1
2
1
-
1
2
2
-
1
2
3
我们终于发现了一个可行解，于是我们将其记录下来，然后继续向下搜索。
现在我直接给出深度优先搜索过程中的部分状态。
-
X
X
X
1
X
X
1
1
X
1
1
1
1
1
2
1
1
3
1
2
X
1
2
1
1
2
2
1
2
3
1
3
X
1
3
1
1
3
2
1
3
3
2
X
X
2
1
1
2
1
2
2
1
3
.
.
.
.
.
.
.
.
.
3
3
3
带你理解这个过程之后，我们对它的逻辑进行一下变形。
图片不见了...
//未完待续