同学们大家好,下面由我来为大家介绍算法思想 那么在上一讲中呢我们介绍了贪心法和围聚法,接下来我将要为大家介绍递归法和回溯法 首先我们来看递归法。递归就是编写这样一个特殊的过程,在这个过程体中呢有一个语句用于 调用这个过程本身,也成为递归调用,递归过程由于实现 了自我嵌套执行,使复杂的算法可以实现的非常简单 首先我们来看使用递归法来实现N! 我们可以定义N!为N*(N-1)! 这样我们就将求N!转换为求(N-1)!,这样就是一个递归的描述了 我们可以看这一段代码,当n==0的时候我们返回1,否则我们返回n*(n-1)! 那么这一段呢就是一个递归调用,下面我们来看汉诺塔问题,有N个圆盘,那么这一段呢就是- 一个递归调用 它以半径大小自下而上嵌套在a柱上,每次只允许 移动最上面的一个圆盘到另外的柱子上去,那么除了a柱以外还有b柱和c柱 而b柱和c柱在开始的时候都没有圆盘,这个问题呢 不允许发生在柱子上出现大盘在上小盘在下的情况 现要求设计一个方法将a柱上的n各圆盘都搬运到c柱的方法 下面我们来看n=3的时候的 解答,首先第一步将小盘子从 a移到c,第二步将a上的中盘子移到b 第三步呢将这个c上的小盘子移回到b 第四部将大盘子移到c,第五步将 b上小盘子移到a,第六步将中 盘子移到c,第七步将最后这个小盘子移到c柱 那么这个过程看上去比较复杂,但是我 如果我们把上面的两片捆绑在一起看成是一整片的话 也就是我们把这两片看成整片的话 我们可以将1-3步变成一步,那么这三步做的事情呢就是把 这一大片移到了b 那么就变成了这样的一个状态 第二步呢我们将这个大盘子移到了c就跟我们 之前做的一样,是普通的一步移动操作,那么第三步呢我们再将我们 捆绑在一起的这一大片b移动到c,换句话说 我们这个过程将这两片移到c那么就变成了最后这个过程 那么这个问题是否变得简单一些了呢? 我们可以将原问题看做将a柱上的n片移动到 c柱,b柱位过渡柱,我们记为a,b,c 那么第一步呢就是将a柱上的n-1片移到b柱上,c为过渡柱可以记为a,c,b 第二步呢是普通的一个移动操作不需要调用过程 第三步呢我们n-1柱从b移到c上,a为过渡柱,可以记为b,a,c 汉诺塔问题这个移动过程虽然很复杂和繁琐,但是 规律性却很强,我们可以使用递归调用技术来解决这个问题。那么我们先要找到一个递归- 调用模型 那么这个方法,这个解法的着眼点应该是如何移动A杆底部的这个大盘,而不是最顶部的- 这个小盘 那么要将A杆上的N各盘移至C杆 根据刚刚的分析我们可以这样想,一步是以C为临时杆,从A移到B 第二步将A杆剩下的N号盘移到C,第三步以A为临时杆 将N-1号盘从B移到C,那么我们可以看到步骤2这个操作 只需要一次移动即可以完成,而步骤1和3的操作和原来 这N个盘的移动问题是完全相同的问题,唯一的区别呢就在于各杆的作用有所不同 那么这样我们就把原问题转换为与原问题相同性质但是规模性质小一些的新的问题 那么根据我们刚刚分析的三步呢 我们把它写成数学的表达式,那么这个问题呢可以分两个 情况,当N=1的时候呢,这就只需要一步,否则的话呢我们就先 需要做这个子问题,然后呢移动一步,然后再需要做这个子问题 那么我们有了这个数学公式之后呢我们就可以简单的把它转变成这个代码 当N==1的时候呢我们进行简单的移动操作,否则的话呢我们先解决这个子问题 进行一次移动操作,再解决下一个子问题,那么这两步呢就是 进行递归调用,因为它们是与原问题完全相同的子问题 接下来我们来看迷宫问题 迷宫问题呢可由如图所示的网格来表示,每个方格呢或者是通道,或者是墙 那么入口和出口是事先指定的两个方格,我们需要找出从入口到 出口的一个简单路径,也就是说呢在求的路径上不能有重复的通道 那么首先我们得到一个迷宫,有入口和 出口,然后呢我们在迷宫的外面扩充一圈,加上监视哨 这个并不是为了改进我们的算法,而是为了我们在 代码实现的时候能够更加方便,不需要做一些边界的判断 然后我们进行这个遍历。我们按照上右下左的方向来遍历 换句话说呢我们在一个点上我们先尝试它能否向上走,然后向右走,然后向下走 然后向左走,那么在第一个位置上呢,上右都不行,所以我们向下走 然后在这个位置呢我们选择向右走,那这样一路走到了这个地方,但是 这是一个死路,所以呢我们进行了第一次回溯,回到了刚才这个位置 然后呢再接着往上走,走到了这个地方,这也是一个死路,所以我们进行第二次回溯 然后回到了这个地方,然后呢按照同样道理我们还需要进行第三次回溯 然后以此类推可以最后走到这个出口 那么这是一个经典的搜索问题,我们从入口出发,沿着一个方向 进行搜索,如果能走通那就继续向前走,否则呢就按原路返回换一个方向再走 直到遇到出口或者所有可能走过的路都走过了 那我们方向呢一共有4个 分别是上右下左,那我们可以用这个 一个数组来表示4个方向 下面我们来看迷宫问题的代码,这个函数解决的是输入一个迷宫 4个方向,然后我们需要从入口x1,y2走到出口y1,y2 我们来枚举4个可能的不同的方向 然后我们可以求得这个新走出一步之后新的这个坐标g和h 那么如果呢这个新的坐标是墙或者是已经搜索过了那么我们枚举下一个k 但是呢如果新的坐标就是我们要的出口,那么我们表示找到一个路径,那么进行输出 那做完这两步之后呢那我们将这个新走的这个一步标记为已经搜索过了 然后接下来呢我们要从新迈出的一步开始进行递归调用,调用这个函数本身 那么如果它返回的是1表示这个搜索成功了我们进行输出 刚刚我们看呢是迷宫问题,接下来我们看四皇后问题 在国际象棋的4*4格的棋盘上放置4个皇后,使 任意两个皇后不在同一行上,同一列上以及同一个对角线上 假设第一个皇后放在第一行x1的位置,第i个皇后放在第i行 xi的位置,那么四皇后问题的一个解可以表示为一个向量(x1,x2,x3,x4) 那么显然这个向量是1,2,3,4的一个排列,那么所有可能的向量有4个阶乘个那么多 这是经典的八皇后问题的简化版本。下面我们来四皇后问题及其解空间树 那么我们用一个这个树来表示四皇后问题的状态空间 它一共有24个结点,就是这个问题所有的可能的解 那么树内部结点代表问题的部分解,树的结点编号 是按照深度优先方式来排列的,其实就是按回溯方式便利搜索的次序来排列的 我们来看第一行,表示我们枚举x1,那么x1可以等于 1,2,3,4,所以呢我们就有了这四个子树 那么第二行表示我们枚举x2,那么对于这个状态 来说呢1已经被用过了所以我们有3个子树,2,3,4 那么接下来x3可能为3或4,x4 相应的可能有对应的值。所以呢叶节点呢就是表示对应的一个可能的解 下面我们来看搜索过程,如果我们进行递归回溯搜索的话呢 大概就是按照这样的一个过程,首先我们在第一行第一列上放置一个皇后 那么我们走到了这样一个点 然后呢我们再在第二行第二列放置一个皇后,那么我们走到了这个点 然后我们发现呢这两个皇后之间是会相互攻击的,所以这一个解呢 不成立,所以我们不用再继续向下搜索了 然后呢我们在第二行第三列又尝试放置一个皇后 我们走到了这样一个点,然后呢我们再在第三行第二列放置一个皇后 所以我们走到了这个点,然后我们发现呢这两个皇后互相之间呢是会攻击的,所以这条路- 也行不通 那么按照这样的过程做呢我们最终可以走到一个叶节点,找到一个解 我们来直观的分析这个问题的搜索代价,时间代价呢 在空间树一共有65个结点,24个叶节点,但是在搜索过程中,只遍历了16个结点,其中- 有2个叶节点 如果要找到所有解的话,我们还不能停下,要继续搜索下去 那么空间代价呢与树的高度有关而不是与树的 总结点有关,在回溯算法中我们并不需要真正的创建一个解空间树 那么 这个生成问题状态的这个基本原理呢就是我们将 正在产生儿子的结点称为扩展结点 一个自身已经生成但是儿子还没有被生成完的结点称为活结点 一个所有儿子都已经生成的结点称为死结点,那么问题 状态生成法呢可以有深度优先和宽度优先这两种方法 那么具体呢这边就不详细说了 我们来回顾一下回溯法的基本思想。第一针对所给 的问题,定义问题的解空间,第二,确定易于搜索的解空间结构 第三以深度优先的方式搜索解空间,并且在搜索结果解空间尽可能使用剪枝函数来避免无- 效的搜索 这就是我们这一讲的内容。同学们再见,谢谢