计算基础教程 12

授课内容搜索学时2教学目标知识目标理解搜索算法的核心思想与解空间树概念掌握回溯法的基本框架与剪枝优化方法掌握深度优先搜索与广度优先搜索的原理与区别了解栈和队列在搜索中的应用与迷宫问题解法能力目标提升复杂问题解空间建模与规律抽象能力强化搜索算法设计与剪枝优化的实践能力培养根据问题场景选择合适搜索策略的能力重点与难点重点回溯法的基本思想、算法框架与剪枝技巧深度优先搜索DFS的递归实现与回溯过程广度优先搜索BFS的队列实现与最短路径求解全排列、子集和、迷宫问题的搜索解法难点设计合理剪枝条件，减少无效搜索区分DFS与BFS的适用场景并正确实现教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接分治算法，学习被称为万能解题法的搜索算法搜索是解决无直接规律问题的最常用核心方法回溯、DFS、BFS是竞赛与考级中的高频考点掌握搜索能大幅提升复杂问题的求解能力本章结合典型例题，系统学习搜索与优化的实用技巧第二部分：新课讲解一、搜索基础1、搜索概述搜索算法是计算机解题中常用的算法之一，又称为“万能解题法”。搜索与暴力枚举的解题思想是一致的，搜索可以说是一种组织条理的枚举，同时它还通过及时“剪枝”来避免无意义的搜索以提高效率。2、全排列与解空间树全排列给出3个数字“123”，要求输出它们的全排列。算法：通过枚举第一位、第二位、第三位上数字可能的取值，就可以生成全排列。解空间树解空间树是解空间的一种组织形式，此形式展示了解空间的逐步生成过程。使用搜索算法时，一个重要的问题就是构造出解空间树，然后按照某种顺序遍历这棵树来寻找问题的答案。3、深搜、广搜与回溯深度优先搜索深度优先搜索(DFS)，是从根节点开始，沿某一个分支尽可能深地向下搜索，触底之后，再回退一级，然后再沿此级节点的其余分支继续向下搜索。只有某个下级节点的所有分支全部搜索完成之后，才退回到上一级节点处。广度优先搜索广度优先搜索(BFS)，是从根节点开始，沿所有可能的分支同时向前搜索。它强调在所有可能的路径上“齐头并进”地向前搜索。搜索与回溯搜索与回溯算法简称回溯法，它是深搜最常见的一种形式。回溯与深搜没有本质上的区别，只是侧重点有所不同。回溯法以穷举所有可能解为核心目标，通过系统性尝试和撤回选择来筛选满足条件的解，常用于组合优化问题。二、回溯法1、基本思想为了求得问题的解，先选择某一种可能的情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，再继续向前探索。如此反复进行，直至得到解或证明无解。2、算法框架voidSearch(intk) //第k步操作{if(到达目的地){输出解;return;}for(i=1;i<=本步可选方案总数;i++)if(第i种选法能够满足条件) //剪枝{保存结果 //保存第k步的选择Search(k+1); //进入第k+1步回溯 //退回第k步的初始状态}}3、子集和问题问题给定有n个不同正整数的集合w=（w1，w2，…,wn）和一个正整数W，要求找出w的子集s，该子集中所有元素的和为W。例如，当n=4，w=（11,24,13,7），W=31时，满足要求的子集为（11,13,7）和（24,7）。解析本题的算法非常简单，就是先考虑集合的第1个数，它有选与不选二种况；然后再考虑第2个数，它也有选与不选二种情况，依次类推。这样针对n个数的选择共有2n种组合，只需要检查这2n种组合中，哪些组合的和等于W即可。以w=（11,13,24,7）为例，其解空间树如下图所示。在本题中，剪枝问题非常重要。由于n个元素有2n种组合，将全部路径都搜索一遍时间复杂度非常高，因此，要及时进行左子树剪枝与右子树剪枝。程序详见课本。三、迷宫类问题1、概述迷宫问题是经典的程序设计问题。最简单的迷宫可以表示为一个由方块组成的矩阵，其中每个方块或者为墙，或者为通道。针对迷宫，主要有二类问题：寻找出口和寻找最短路径。寻找出口从指定的位置开始，找到任意一个出口，从而走出迷宫。这个问题使用深度优先搜索和广度优先搜索两种算法均可。寻找最短路径指定入口与出口的位置，找出二者之间的最短路径。这个问题需要使用广度优先搜索，这样搜索出的第一条路径就是最短路径。2、使用广度优先搜索求最短路径搜索过程准备一个队列，先将入口单元格放入队列中，然后进行如下循环：while(队列非空){ 取出队首元素; if（若队首元素是出口） 已找到最短路径，结束 else 将队首元素周围是“路”的单元格都添加到队尾（已搜索过的除外）}这样，通过一个循环驱动，在每轮循环中，同时向所有的路径都前进一步。当发现有一条路径已到达出口时，这条路径就是最短的。图示以课本上的样例数据为例，搜索过程如下图所示：程序详见课本。3、使用深度优先搜索寻找出口如果只需要找到出口，使用深度优先的搜索即可，搜索过程如下。准备一个栈，并将入口单元格入栈，然后进行如下循环：while（栈非空）{ if(栈顶元素是出口){输出路径;结束;}else{ 针对栈顶元素，在其四周寻找一个从未走过并且是“路”的单元格 if(能找到上述单元格) 将其入栈; //这样下次循环将会针对此单元格再向前搜索 else 将