算法与数据结构讲义三（搜索算法）.doc

第十三课搜索算法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-1113223122113314424114244112332232343233234123243213244可以建立搜索树如下：图中表示：由(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）每个结点数据的下一级子结点是由该结点的产生式规则生成。（3）目标结点（答案数据）一定在搜索树中能够出现。（4）对于数据规模较大的问题，搜索树的结点将是海量的。（5）搜索树可能是无穷无尽的（因为很多结点回重复出现）。12.1搜索算法的基本原理：从搜索树中可以看出，一个问题从起始状态，通过穷举的方式建立起搜索树后，目标状态一定能在搜索树中出现。因此，只要建立起搜索树，就可以在其中搜索到目标状态（数据、路径、位置等）。搜索算法要解决的问题：产生式规则：由当前状态按照问题的需求和限制，生成新的状态的方法集合。搜索树的生成和存储：一般采用一边生成，一边搜索；存储方法有：集合、栈。搜索的方法：按行搜索：即从上到下，逐层搜索双向按行搜索：一边从上往下（起始状态到中间状态），一边从下往上逐层搜索（从目标状态到中间状态），找到相同的中间状态即可。回朔法搜索：优先向更深层结点查找，走不通则换一条路，无法换则退回到上一层。搜索状态的减少：在生成搜索树时，对于已搜过的中间状态的再次出现，是否需要再次加入到树中重新搜索。12.2广度优先搜索（bfs）又称宽度优先搜索，是一种从搜索树的根结点开始，沿着树的宽度遍历树的结点。如果所有节点均被访问，则算法中止。一般用于求从起始状态到目标状态所需的最少步骤数。算法过程：1、首先将根结点放入队列中。2、从队首取出一个结点，按照产生式规则逐个生成新的结点数据，对新数据：如果如果是目标结点，则结束算法并返回结果。如果不是目标结点，则检查它是否已在搜索树中出现过，未出现就将它作为尚未检查过的子结点加入到队列的队尾（特殊情况下，也有已出现过的结点重新入队的）。3、重复步骤2。4、若队列为空，表示整张图都检查过了，即目标无法达到，结束算法并返回“找不到目标”的信息。算法细化：用哈希数组判断新生成的结点数据是否已出现过。队列经常要多开一行，记录新结点的父亲（即该结点由上一层的哪个结点扩展而来），用于最后输出过程。如数据规模过大，需要使用循环队列（后果是无法记录父亲）。算法框架：functioncreat(i)begincaseiof1:creat:=按照第一产生式规则生成新状态数据；2:creat:=按照第二产生式规则生成新状态数据；...end;end;////////////////////////////////////////////////////////////////procedurebfs;beginjoin(起始状态);whilenot(队空)dobegin当前处理状态:=deq;fori:=第一产生式规则to最大产生式规则dobegin新状态:=creat(i);if新状态=目标状态thenbeginprint;exit;endelseifnot(haxi[新状态])thenbeginjoin(新状态);haxi[新状态]:=true;end;end;end;end;空间复杂度：线性队列：O(最大可能状态数)循环队列：O(最大可能状态数/2)时间复杂度：最差情形下，BFS必须寻找所有到可能结点的所有路径。O(最大可能状态数)完全性：广度优先搜索算法具有完全性。只要目标存在，则BFS一定会找到。但是，若目标不存在，且问题规模为无限大，则BFS将不收敛（不会结束）。适用范围：广度优先搜索是找到第一个解的算法，即距离根结点的边数最少的解。如果所有边的权值都相等（即所有产生新状态的代价相同），则这个解也是最优解。例一：将一个马从M*N