浅谈dfs

DFS, 全称为深度优先搜索，是一种基于图论的漫游和搜索算法，它是经典的暴力算法之一， 搜索所有最优解解的有效算法之一，尤其是在树或图的搜索中非常实用。当然，正因为它是暴力算法，针对特定的问题它的时间和空间复杂度可能会比较高。

DFS的基本思路是从某个状态开始，不断按照可选方案生成新状态，重复这个过程，直到生成一个“解”，也就是在满足限制条件的情况下得到了需要的结果。由于这种搜索方法是基于深度的，所以叫做深度优先搜索。

实现DFS的标准方法是用递归，从根节点开始，一直沿着一条路径去到最深节点，将结果返回上一级节点，继续往下进行。

下面是几个相关的概念，稍加解释一下：

状态：搜索的问题中每种情况称作一种状态。

树：搜索树是一棵根节点为初始状态，边为某个状态到相邻状态的转化, 子节点连接到子状态的一个树。

剪枝：在进行搜索的过程中, 可以剪枝, 当搜索到某个节点时，如果这个节点无法找到符合条件的“解”，则可以剪去这个节点以及所有以这个节点为根的子树。这种方法可以提高搜索效率，避免无谓的搜索。一些常见的剪枝技巧包括：可行性剪枝，限界剪枝等。

回溯：当搜索到某个节点时，发现这个节点不能到达解，则回退到上一个节点，重新选择其它分支继续搜索, 这种操作称为回溯。

DFS的算法框架：

1. 确定初始状态

2. 逐个扩展各种情况的状态

3. 判断是否符合预定的目标

4. 递归到上一层状态继续进行 2 - 3 步

5. 如果找到最优解则返回，否则回溯到上一个状态，继续2-4步，直到所有情况遍历完毕

下面我来通过实例来进一步理解DFS的过程。

假设我们有一些玩具，包括：魔方、跳棋和拼图，想选一部分送给小朋友，现在有两个限制条件：一是需要选四个玩具，二是不能出现两个同种玩具。请使用DFS算法解决该问题。

首先，我们确定初始状态是选择0个玩具，此时状态为[]。

1. 我们从魔方、跳棋、拼图三个玩具中任选一个，比如说选择了拼图，此时状态变为[拼图]。

2. 我们继续从魔方、跳棋、拼图三个玩具中任选一个，选择跳棋，此时状态变为[拼图, 跳棋]。

3. 我们再继续任选一个，假设选择了魔方，状态变为[拼图, 跳棋, 魔方]。

4. 现在我们已经选择了三个玩具，接下来需要再选择一个。我们从魔方、跳棋、拼图三个玩具中任选一个，比如说选择了魔方。此时状态变为[拼图, 跳棋, 魔方, 魔方]，但是由于出现了两个同种玩具，所以这条路径无法继续往下走，需要回溯到上一个状态[拼图, 跳棋, 魔方]。

5. 回溯到上一个状态后，我们继续做两种选择，即选择跳棋或选择拼图，假设我们选择了跳棋，那么状态变为[拼图, 跳棋, 魔方, 跳棋]，输出结果[拼图, 跳棋, 魔方, 跳棋]。

6. 继续回溯到[拼图, 跳棋, 魔方]，此时只有一个选择，即选择拼图，状态变为[拼图, 跳棋, 魔方, 拼图]，但是由于出现了两个同种玩具，需要回溯到上一个状态。回溯到[拼图, 跳棋]，继续做两种选择，即选择魔方或选择拼图。

7. 假设我们选择了魔方，状态变为[拼图, 跳棋, 魔方, 魔方]，但是由于出现了两个同种玩具，需要回溯到上一个状态。回溯到[拼图, 跳棋]，继续做两种选择，即选择魔方或选择拼图。

8. 假设我们选择了拼图，状态变为[拼图, 跳棋, 拼图, 拼图]，但是由于出现了两个同种玩具，需要回溯到上一个状态。回溯到[拼图, 跳棋]，我们还有最后一种选择，即选择魔方，状态变为[拼图, 跳棋, 魔方]。

9. 从[拼图, 跳棋, 魔方]状态开始，我们可以选择魔方、跳棋和拼图中的任一个作为最后一个玩具，于是搜索结束。

在以上的过程中，DFS在搜索过程中采用递归的方式，逐渐深入下一层的状态，并每次累计处理答案，这样就能够逐层对状态进行扩展，从而不断更新搜索结果，从而得到较高的搜索效率。

DFS 算法的优缺点:

优点：

1.具有较高的搜索效率

2.DFS假定计算机的处理速度非常快，内存容量大，因此只需少量的空间就可以完成对给定问题的搜索。

缺点：

1.可能会随机漫游到过深或过浅的状态空间，导致过多的无意义搜索，导致算法时间复杂度过高。

2.可能导致状态空间的重复搜索，原因是同一个状态可能从多个父状态派生出来。

3.在不同机器上执行的时间和空间复杂度可能会有所不同。

综上所述，DFS是一种高效的搜索算法，它的核心思想是从当前状态开始，通过递归不断扩展状态空间，直到发现符合条件的解，或者搜索完所有状态并回溯到初始状态。但是，由于 DFS 算法的时间和空间复杂度可能较高，因此我们在实践中需要结合具体问题来综合考虑各种因素，以得到更优秀的解决方案。