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