查找算法应用
1. c++中dfs是什么意思
C++中的DFS是指深度优先搜索算法。它是一种用于遍历或搜索树或图的算法。以下是关于DFS的详细解释：
基本概念：DFS是一种从树的顶端开始，沿着树的深度一直探索到最左边的数据，然后回溯到上一个节点，继续探索未访问的分支，直到所有节点都被访问为止的算法。
搜索策略：以深度为第一标准进行搜索。即，算法会尽可能深地探索每一个分支，直到达到叶节点或无法继续为止，然后回溯到上一个节点，继续探索其他未访问的分支。
应用场景：DFS广泛应用于各种领域，如路径查找、连通性判断、图的遍历等。在C++中，DFS通常通过递归或栈来实现。
实现方式：
- 递归实现：利用函数的递归调用，每次调用都深入一层，直到达到叶节点或无法继续，然后回溯。
- 栈实现：使用栈数据结构来模拟递归过程，通过显式地维护一个栈来记录待访问的节点，从而实现深度优先搜索。
DFS是一种重要的算法思想，在解决许多问题时都能发挥重要作用。
2. 搜索算法的应用案例
(1)题目：黑白棋游戏
黑白棋游戏的棋盘由4×4方格阵列构成。棋盘的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子。这16枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有1条公共边的2个方格称为相邻方格。一个方格最多可有4个相邻方格。在玩黑白棋游戏时，每一步可将任何2个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态，编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。
(2)分析
这题我们可以想到用深度优先搜索来做，但是如果下一步出现了以前的状态怎么办？直接判断时间复杂度的可能会有点大，这题的最优解法是用广度优先搜索来做。我们就可以有初始状态按照广度优先搜索遍历来扩展每一个点，这样到达目标状态的步数一定是最优的（步数的增加时单调的）。但问题是如果出现了重复的情况我们就必须要判重，但是朴素的判重是可以达到状态数级别的，其实我们可以考虑用hash表来判重。
Hash表：思路是根据关键码值进行直接访问。也就是说把一个关键码值映射到表中的一个位置来访问记录的过程。在Hash表中，一般插入，查找的时间复杂度可以在O（1）的时间复杂度内搞定。对于这一题我们可以用二进制值表示其hash值，最多2^16次方，所以我们开个2^16次方的表记录这个状态出现没有，这样可以在O（1）的时间复杂度内解决判重问题。
进一步考虑：从初始状态到目标状态，必定会产生很多无用的状态，那还有什么优化可以减少这时间复杂度？我们可以考虑把初始状态和目标状态一起扩展，这样如果初始状态的某个被扩展的点与目标状态所扩展的点相同时，那这两个点不用扩展下去，而两个扩展的步数和也就是答案。
上面的想法是双向广度优先搜索：
就像图二一样，多扩展了很多不必要的状态。
从上面一题可以看到我们用到了两种优化方法，即Hash表优化和双向广搜优化。一般的广度优先搜索用这两个优化就足以解决。
