搜索算法
搜索算法
搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。
【一】搜索过程搜索算法实际上是根据初始条件和扩展规则构造一颗“解答树”并寻找符合目标状态的节点的过程。所有的搜索算法从最终的算法实现上来看，都可以划分成两个部分——控制结构（扩展节点的方式）和产生系统（扩展节点），而所有的算法优化和改进主要都是通过修改其控制结构来完成的。其实，在这样的思考过程中，我们已经不知不
觉地将一个具体的问题抽象成了一个图论的模型——树，即搜索算法的使用第一步在于搜索树的建立。
由图一可以知道，这样形成的一棵树叫搜索树。初始状态对应着根结点，目标状态对应着目标结点。排在前的结点叫父结点，其后的结点叫子结点，同一层中的结点是兄弟结点，由父结点产生子结点叫扩展。完成搜索的过程就是找到一条从根结点到目标结点的路径，找出一个最优的解。这种搜索算法的实现类似于图或树的遍历，通常可以有两种不同的实现方法，即深度优先搜索（DFS——Depth First search）和广度优先搜索（BFS——Breadth First Search）。
【二】深度优先搜索一、算法思想如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前（子结点）探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。深度优先搜索的实现方式可以采用递归或者栈来实现。
由此可见，把通常问题转化为树的问题是至关重要的一步，完成了树的转换基本完成了问题求解。二、深度优先搜索的优化1、优化思想
减少所遍历的状态总数
2、三种方法
(1)减少节点数
思想：尽可能减少生成的节点数
(2)定制回溯边界
思想：定制回溯边界条件，剪掉不可能得到最优解的子树
在很多情况下，我们已经找到了一组比较好的解。但是计算机仍然会义无返顾地去搜索比它更“劣”的其他解，搜索到后也只能回溯。为了避免出现这种情况，我们需要灵活地去定制回溯搜索的边界。
在深度优先搜索的过程当中，往往有很多走不通的“死路”。假如我们把这些“死路”排除在外，不是可以节省很多的时间吗？打一个比方，前面有一个路径，别人已经提示：“这是死路，肯定不通”，而你的程序仍然很“执着”地要继续朝这个方向走，走到头来才发现，别人的提示是正确的。这样，浪费了很多的时间。针对这种情况，我们可以把“死路”给标记一下不走，就可以得到更高的搜索效率。
(3)记忆化
思想：运用记忆化的方法，使得一些遍历过的子树不要重复遍历
3、三个原则
(1)正确性：剪去的“枝条”不包含最优答案；
(2)准确性：在保证第一条原则的情况下，尽可能的剪去更多不包含最优答案的枝条；
(3)高效性：通过剪枝要能够更快的接近到达最优解。
【三】广度优先搜索一、广度优先搜索遍历类似树的按层遍历，其过程为：首先访问初始点Vi，并将其标记为已访问过，接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2……Vit，并均标记为已访问过，然后再按照Vi1、Vi2……Vit的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。二、处理和优化对于状态数很多时，广度优先搜索可以采用循环队列或动态链表来处理。
举例分析一下：
(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表优化和双向广搜优化。一般的广度优先搜索用这两个优化就足以解决。
【四】深度优先搜索和广度优先搜索的比较遍历方式
深度优先搜索遍历
广度优先搜索遍历
所用数据结构
栈
队列
一般优化
最优性剪枝
可行性剪枝
Hash判重
双向搜索