递归与搜索部分知识点小结

递归与搜索部分知识点小结

递归算法

程序直接或间接调用自身的编程技巧称为递归算法。
直接或间接调用自身的函数称为递归函数。
递归函数通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。（一步步缩小，缩到最小问题可以直接解决）

递归的关键：
问题转化与递归终止：
问题转化：找出问题转化的规则是一个重点（这有点像动态规划中状态转移方程的寻找，难点很多时候就在这一步）（递归很多时候与状态转移方程类似，状态转移方程是递推的概念，而递归就是递归，二者思路上十分相近）
递归终止：就是所描述问题的最简单情况，它本身不再使用递归的定义。（递归到最后的小问题可以直接解决）

递归与递推的关系：
递归是大问题转化为小问题，不断调用自身或不断间接调用的一类算法。
递归算法的关键是要找出大问题和小问题的联系----即递归定义。进而使大问题的规模不断减少，从而达到能解决的规模，最后解决这个问题。
有时，递归算法的效率会很低，这时候就可以用记忆化搜索，即建立一个标志数组为全局变量，用来记录每次递归得到的答案，这样如果后面要继续使用这个值的时候，就不用在计算了，避免了重复计算。

递推和递归非常相似：
递推是把问题划分为若干个步骤，每个步骤之间，或者是这个步骤于之前的几个步骤之间有一定的数量关系，就可以用前几项的值表示出这一项的值，这样就可以把一个复杂的问题变成很多小的问题。
递推问题的关键是要设出状态变量，并且表示出递推公式，找出这两点，这个问题就可以说解决了。
递推算法注意的是设置什么样的递推状态，因为一个好的递推状态可以让问题很简单。
而一般最难的是想出递推公式，一般递推公式是从后面向前想，倒推回去，当然也有很多是从中间想或者是前面，一项一项的推到最后。
有时候递推也会用预处理的方法，在处理的数据比较大时，想把所有的数据算出来，然后再开始不断调出。

递归的步骤：
递归算法解题通常有三个步骤：
1）分析问题、寻找递归：找出大规模问题与小规模问题的关系，这样通过递归使问题的规模逐渐变小。
2）设置边界、控制递归：找出停止条件，即算法可解的最小规模问题。
3）设计函数、确定参数：设计函数体中的操作及相关参数。

搜索

搜索算法就是穷举出一个问题的部分或所有可能情况，从中找出求解方法。但是搜索相比于单纯的枚举算法有了一定的方向性和目标性。搜索从解的所有可能中从一个状态转移到其他状态（按照要求向解的方向拓展），这样一直进行下去，直到找到答案（目标状态）为止。

搜索分为广度优先搜索（BFS）与深度优先搜索（DFS）

广度优先搜索：
基本思想：从初始状态S 开始，利用规则，生成所有可能的状态。构成的下一层节点，检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别顺序利用规则。
生成再下一层的所有状态节点，对这一层的所有状态节点检查是否出现G，若未出现，继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。——在路径的寻找问题上用得比较多

这种思路可以用队列来模拟该过程：
具体实现过程：
1 每次取出队列首元素（初始状态），进行拓展
2 然后把拓展所得到的可行状态都放到队列里面
3 将初始状态删除
4 一直进行以上三步直到求出可行解或队列为空。

深度优先搜索：（回溯法）
基本思想：从初始状态，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态，若未出现，以此状态利用规则生成再下一层任一个结点，再检查，重复过程一直到叶节点（即不能再生成新状态节点），当它仍不是目标状态时，回溯到上一层结果，取另一可能扩展搜索的分支。采用相同办法一直进行下去，直到找到目标状态为止。

这种思路可以用栈来模拟该过程：
具体实现过程：
1 每次取出栈顶元素，对其进行拓展。
2 若栈顶元素无法继续拓展，则将其从栈中弹出。继续1过程。
3 不断重复直到获得目标状态（取得可行解）或栈为空（无解）。