下载后可任意编辑第十三课 搜索算法12.0 搜索树12.1 搜索算法的基本原理12.2 广度优先搜索12.3 深度优先搜索12.4 练习12.0 搜索树引例：在一个 4*4 的棋盘上的左下角有一个马，根据国际象棋的规则，将这个马跳到右上角。分析：首先建立棋盘的坐标，我们以左下角为(1,1)，以右上角、为(4,4)。根据马的移动规则，假定当前马的位置坐标为(x,y)，则移动方法有：（1）x’=x+1; y’=y+2（2）x’=x+1; y’=y-2;（3）x’=x+2; y’=y+1;（4）x’=x+2; y’=y-1;（5）x’=x-1; y’=y+2;（6）x’=x-1; y’=y-2;（7）x’=x-2; y’=y+1;（8）x’=x-2; y’=y-1可以建立搜索树如下：图中表示：由(1,1)可以跳到(2,3)和(3,2)两个点(其它移动规则由于边界限制无法到达)；(2,3)又可以跳到(1,1)、(4,4)、(4,2)、(3,1)四个点，(3,2)可以跳达(1,1)、(1,3)、(2,4)、(4,4)四个点，……。搜索树：根据数据元素的产生式规则建立起来的数据元素逻辑关系。特点：（1）数据之间的逻辑关系为一对多。 （2）每个结点数据的下一级子结点是由该结点的产生式规则生成。*113223122113314424114244112332232343233234123243213244下载后可任意编辑 （3）目标结点（答案数据）一定在搜索树中能够出现。 （4）对于数据规模较大的问题，搜索树的结点将是海量的。 （5）搜索树可能是无穷无尽的（因为很多结点回重复出现）。12.1 搜索算法的基本原理：从搜索树中可以看出，一个问题从起始状态，通过穷举的方式建立起搜索树后，目标状态一定能在搜索树中出现。因此，只要建立起搜索树，就可以在其中搜索到目标状态（数据、路径、位置等）。搜索算法要解决的问题：产生式规则：由当前状态根据问题的需求和限制，生成新的状态的方法集合。搜索树的生成和存储：一般采纳一边生成，一边搜索；存储方法有：集合、栈。搜索的方法：按行搜索：即从上到下，逐层搜索双向按行搜索：一边从上往下（起始状态到中间状态），一边从下往上逐层搜索（从目标状态到中间状态），找到相同的中间状态即可。回朔法搜索：优先向更深层结点查找，走不通则换一条路，无法换则退回到上一层。搜索状态的减少：在生成搜索树时，对于已搜过的中间状态的再次出现，是否需要再次加入到树中重新搜索。12.2 广度优先搜索（bfs）又称宽度优先搜索，是一种从搜索树的根结点开始，沿着树的宽度遍历树的结点。假如所有节点均被访问，则算法中止。一般用于求从起始状态到目标状态所需的最少步骤数。算法过程...
