搜索算法初步

搜索算法初步江苏省常州市第一中学 林厚从一、概述搜索是程序设计中的一项重要技术。许多编程问题不能用公式推导、数学计算或者模拟等方法来寻找答案，这样的问题往往有一个庞大的问题状态空间，并且给出了一些约束条件，要求寻找“解空间”中的一个或多个解。对于这样的问题，我们需要在“状态空间树”中摸索，以某种方式或顺序来试探不同的“状态结点”，使得尽可能快的寻找到“目标结点”，或者是从“初始结点”到“目标结点”的一个路径。这也正好利用了计算机运算速度快的优点。1、状态和状态空间状态一般是指客观现场信息的描述，通常用T表示，而用T0表示初始状态、Tn表示目标状态。状态空间是指所有合理状态的集合，可以表示成=T。例1、分油问题问题描述有3个油瓶，容量分别为10斤、7斤、3斤。开始时，10斤的瓶子中装满了油，其余为空，现在通过在这3个瓶子中倒来倒去，将10斤油分成2个5斤的。请编程输出一种倒油的方案。概念解释用一个三元组T（x10,x7,x3）来表示一种状态，其中x10，x7，x3分别表示10斤瓶、7斤瓶、3斤瓶中的油量。初始状态：T0=（10，0，0）目标状态：Tn=（5，5，0）约束条件：x10+x7+x3=10, 0x1010，0x77，0x33状态空间：所有满足上述约束条件的状态 T（x10,x7,x3），如T（3,7,0），T（4,4,2）状态总数：35种。2、产生式系统产生式系统由一个综合数据库、一组产生式规则和一个控制系统三个基本要素组成。其中，综合数据库是产生式系统所用的主要数据结构（常见的如：集合、数组、树、队列等）。它主要用来表示问题的状态（初始状态、目标状态、中间状态）及状态之间的关系，它不是固定不变的，在求解过程中，它的内容会越来越多，关系也会越来越复杂。产生式规则是对数据库进行操作的一系列规则。规则的一般形式就是：IF 条件 THEN 操作。它实现了状态之间的转移和关联，一般也称为状态变化规则。控制策略规定了操作的顺序，即在什么条件下用什么规则进行操作，什么条件下停止运行，它规定了问题求解的搜索策略和路线。控制策略一般分为不可撤回方式和可撤回方式（试探法、回溯法）两类。对于分油问题，有6种倒油的可能性（6条产生式规则），分别如下： 10斤的瓶子往7斤的瓶子里倒：条件是x10>0 and x7<7 操作是x10:=x10+x7-7;x7:=7;x3不变10斤的瓶子往3斤的瓶子里倒：条件是x10>0 and x3<3 操作是x10:=x10+x3-3;x3:=3;x7不变7斤的瓶子往3斤的瓶子里倒：略7斤的瓶子往10斤的瓶子里倒：略3斤的瓶子往7斤的瓶子里倒：略3斤的瓶子往10斤的瓶子里倒：略3、搜索中的一些问题搜索的问题一般有两种情况：一种是给出初始结点，要求寻找到符合约束条件的目标结点；另一种是给出初始结点和目标结点，要求找到从初始结点到目标结点的一条路径。对于解的要求也不尽相同，有的问题要求出问题的最优解，有的则要求出较优解，而有的问题要找出问题的全部解。搜索问题中的数据结构一般要求表达要合理，要有助于计算机的处理；信息要完整，要能反应出状态的本质和状态之间的关系；还要节省存储空间，尽可能地提高搜索的速度。比如分油问题本来用一个三元组（x10,x7,x3）即可，但是为了输出方便，我们增加一个d,用来表示该结点的父结点（由谁扩展来的），即变成一个四元组（x10,x7,x3,d）。另外还用到队列来实现控制策略，当然，不能忘记状态变化过程中的重复性检查，因为大多数情况下，出现重复状态是毫无意义的，会造成死循环和空间的浪费。二、广度优先搜索算法广度优先搜索是从初始结点开始，应用产生式规则和控制策略生成第一层结点，同时检查目标结点是否在这些生成的结点中。若没有，再用产生式规则将所有第一层结点逐一扩展，得到第二层结点，并逐一检查第二层结点是否包含目标结点。若没有，再用产生式规则扩展第二层结点，如此依次扩展，检查下去，直至发现目标结点为止。如果扩展完所有结点，都没有发现目标结点，则问题无解。在搜索的过程中，广度优先搜索对于结点是沿着深度的断层扩展的。如果要扩展第n+1层结点，必须先全部扩展完第n层结点。对于同一层结点来说，他们对于问题的解的价值是相同的。所以，这种搜索方法一定能保证找到最短的解序列。也就是说，第一个找到的目标结点，一定是应用产生式规则最少的。因此，广度优先搜索算法比较适合求最少步骤或者最短解序列的题目。在具体求解过程中，广度优先一般用到“队列”这种重要的数据结构。例2、奇怪的电梯问题描述有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1in)上有一个数字Ki(0Kin)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字Ki。当然，如果不能满足要求，相应的按钮就会失灵。例如：3、3、1、2、5代表了Ki(K1=3,K2=3,)，从1楼开始。在1楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？输入格式输入文件共有二行，第一行为三个用空格隔开的正整数，表示n,A,B(1n200, 1A,BN)，第二行为n个用空格隔开的正整数，表示Ki。输出格式输出文件仅一行，即最少按键次数,若无法到达，则输出-1。输入样例5 1 53 3 1 2 5输出样例3问题分析因为要求的是“最少按几次按扭”，所以是很明显的广度优先搜索。每次从当前结点最多只可以扩展两个结点。参考程序program lift;var n,a,b,i,x:longint;n总层数，a起始层，b终止层，x是记录上层到达层数的个数 r,r1:set of 1.200;r记录上一次到达层的集合 k,s:array1.200of longint;s记录到达该层所需的次数begin readln(n,a,b); for i:=1 to n do read(ki); for i:=1 to n do si:=maxlongint; 初始化为都不可到达 sa:=0; r:=a; x:=1; while (sb=maxlongint)and(x<>0) do begin x:=0;r1:=; for i:=1 to n do if i in r then求出上一层的顶点，进行枚举 begin if (i+ki<=n)and(si+1<si+ki)then如果可以向上乘电梯 begin x:=x+1; si+ki:=si+1; 解更优，即到达i+ki层花的步数更少 r1:=r1+i+ki end; if (i-ki>=0)and(si+1<si-ki)then如果能向下乘电梯 begin x:=x+1; si-ki:=si+1; r1:=r1+i-ki end; end; r:=r1 为下一次作准备 end; if sb<>maxlongint then writeln(sb) else writeln(-1);end.例3、图的广（宽）度优先搜索问题描述读入一个用邻接矩阵存储的无向图，输出它的广度优先遍历序列。输入样例 80 1 1 0 0 0 0 01 0 0 1 1 0 0 01 0 0 0 0 0 1 10 1 0 0 0 1 0 00 1 0 0 0 1 0 00 0 0 1 1 0 0 00 0 1 0 0 0 0 10 0 1 0 0 0 1 0输出样例1-2-3-4-5-7-8-6参考程序program bfs;var i,j,n,front,rear,x:integer; g:array1.20,1.20 of integer; q,flag:array0.20 of integer;begin readln(n); for i:=1 to n do begin for j:=1 to n do read(gi,j); readln; end; for i:=1 to n do flagi:=0; flag1:=1;q1:=1; front:=1;rear:=1; while front<=rear do begin x:=qfront; front:=front+1; for i:=1 to n do if (flagi=0) and (gx,i=1) then begin rear:=rear+1;qrear:=i;flagi:=1;end; end; for i:=1 to n-1 do write(qi,-); writeln(qn);end.例4、分油问题参考程序 program oil;var i,j,x,y,z,y10,y7,y3,front,rear:integer; q:array1.100,1.4 of integer; out:array1.100,1.3 of integer; p:boolean;function f:boolean; 状态判重var i:integer; yes:boolean;begin yes:=true; for i:=1 to rear do if (qi,1=y10) and (qi,2=y7) and (qi,3=y3) then yes:=false; f:=yes;end;procedure insert; 插入新状态begin rear:=rear+1; qrear,1:=y10; qrear,2:=y7; qrear,3:=y3; qrear,4:=front;end;beginmain q1,1:=10;q1,2:=0;q1,3:=0;q1,4:=0; front:=1;rear:=1;p:=true; while p do begin x:=qfront,1;y:=qfront,2;z:=qfront,3; 取队头元素扩展 if (x=5) and (y=5) then p:=false else begin if (x>0) and (y<7) then 10->7 begin y10:=x+y-7;y7:=7;y3:=z; if f then insert; end; if (x>0) and (z<3) then 10->3 begin y10:=x+z-3;y7:=y;y3:=3; if f then insert; end; if (y>0) then 7->10 begin y10:=x+y;y7:=0;y3:=z; if f then insert; end; if (y>0) and (z<3) then 7->3 if (y+z>3) then begin y10:=x;y7:=y+z-3;y3:=3; if f then insert; end else begin y10:=x;y7:=0;y3:=y+z; if f then insert; end; if (z>0) then 3->10 begin y10:=x+z;y7:=y;y3:=0; if f then insert; end; if (y<7) and (z>0) then 3->7 if (y+z>7) then begin y10:=x;y7:=7;y3:=y+z-7; if f then insert; end else begin y10:=x;y7:=y+z;z:=0; if f then insert; end; front:=front+1; end; end; i:=0; while front<>0 do 根据结点之间的关系，依次输出 begin i:=i+1; outi,1:=qfront,1; outi,2:=qfront,2; outi,3:=qfront,3; front:=qfront,4; end; for j:=i downto 1 do writeln(outj,1:3,outj,2:3,outj,3:3); readln;end.运行结果10 0 03 7 03 4 36 4 06 1 39 1 09 0 12 7 12 5 35 5 0三、深度优先搜索算法深度优先搜索与广度优先搜索的大体思想相同，也是从初始结点开始扩展，但扩展的顺序却不同，深度优先搜索总是先扩展最新产生的结点。这就使得搜索沿着状态空间的某条单一的路径进行下去，直到最后的结点不能产生新结点或者找到目标结点为止。当搜索到不能产生新结点的时候，就沿着该结点产生顺序的反方向寻找可以产生新结点的结点，并扩展它，形成另外一条搜索路径。广度优先搜索中的结点扩展原则是先产生的先扩展（队列），而深度优先搜索中扩展结点的原则是先产生的后扩展（用堆栈来实现），这是两种搜索方式的本质不同。因此，深度优先搜索找到的第一个解，并不一定是问题的最优解，要搜索完整个状态空间，才能确定哪个解是最优解。例5、图的深度优先搜索问题描述读入一个用邻接矩阵存储的无向图，输出它的深度优先遍历序列。输入样例80 1 1 0 0 0 0 01 0 0 1 1 0 0 01 0 0 0 0 0 1 10 1 0 0 0 1 0 00 1 0 0 0 1 0 00 0 0 1 1 0 0 00 0 1 0 0 0 0 10 0 1 0 0 0 1 0输出样例1-2-4-6-5-3-7-8参考程序program dfs;var i,j,k,n,top:integer; g:array1.20,1.20 of integer; stack,flag:array0.20 of integer;begin readln(n); for i:=1 to n do begin for j:=1 to n do read(gi,j); readln; end; for i:=1 to n do flagi:=0; write(1); flag1:=1; stack0:=1; top:=0; while top>=0 do begin k:=k+1; if k>n then begin k:=stacktop;top:=top-1;end else if (flagk=0) and (gstacktop,k=1) then begin write('-',k); flagk:=1; top:=top+1;stacktop:=k; k:=0; end; end; readln;end.例6、马的走法问题描述在一个4*5的棋盘上，输入马的起始位置坐标（纵、横），求马遍历所有格子且返回起始位置的所有不同走法的总数。注意：马只能走“日”字，且走过的位置不能重复走。样例输入：2 2样例输出：4596问题分析从问题描述可以看出，数据的规模很小，用回溯算法即可搜索出问题的解，但是看到样例，我们发现结果可能很大。定义一个递归过程find（p1,p2），表示当前马的位置在（p1,p2），之前经过的路径用一个二维数组chess标记即可，chessi,j=1表示马已经走过该位置了，初始化为全0。显然从（p1,p2）出发，最多有8个可能的走法（如下左图），8种走法的纵、横坐标的变化值只要用一个常量数组表示即可。例如，从右图1号点出发，马先到2号点，再到3号，直到某一步不能继续走，这时要么找到了一条路径，要么进入了“死胡同”，这个find过程就不能递归调用自己了，就会后退一步（回溯）继续进行递归了。请自己动手模拟一下find的执行过程，就能充分体会其中的奥妙了，也可以跟踪参考程序，观察find的调用情况和chess数组的变化。同时，适当改变8个方向的常量数组顺序，也能够得到同样的结果，但是过程可能有所不同。本题的数据范围是4*5，如果范围稍微改大一点，如7*7，就会出现超时很严重的情况，请大家分析一下其中的搜索量。参考程序program horse;type tp=array0.4,0.5 of integer;const d:array1.2,1.8 of integer =(-1,-1,-2,-2,2, 2,1, 1),(-2, 2, 1,-1,1,-1,2,-2);var chess:tp; sx,sy,first:integer; tot:longint;procedure find(p1,p2:integer);var pi,pj,i:integer;begin for i:=1 to 8 do begin pi:=p1+d1,i; pj:=p2+d2,i;if (pi>=1) and (pj>=1) and (pi<5) and (pj<6) and (chesspi,pj=0) then begin chesspi,pj:=1; find(pi,pj); chesspi,pj:=0; 恢复现场 end else if (pi=sx) and (pj=sy) then inc(tot); end;end;beginmain readln(sx,sy); fillchar(chess,sizeof(tp),0); chesssx,sy:=1; tot:=0; find(sx,sy); writeln(tot);end.