广度和深度优先搜索.doc

3深度优先搜索和广度优先搜索产生式系统深度优先搜索和广度优先搜索一、产生式系统首先通过一个具体事例说明什么是产生式系统。例题4-1八数码难题在3X3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是：找到一种移动方法，实现从初始布局到目标布局的转变。例如输入：（代表从前一布局到后一布局）2 8 31 6 47 0 51 2 38 0 47 6 5 分析状态表示：用二维数组来表示布局。(si,sj)表示第i行、第j列上放的棋子数字。空格用0表示。产生规则：原规则规定空格周围的棋子可以向空格移动。但如果换一种角度观察，也可看做空格向四周移动。这样处理更便于编程。如果空格位置在(si,sj)，则有四条规则：(1)空格向上移动: If si-1=1 then ch(si,sj):=ch(si-1,sj);ch(si-1,sj):=0(2)空格向下移动: If si+1=1 then ch(si,sj):=ch(si,sj-1);ch(si,sj-1):=0(4)空格向右移动: If sj+1=3 then ch(si,sj):=ch(si,sj+1);ch(si,sj+1):=0搜索策略：(1)把初始状态作为当前状态；(2)从当前状态出发，运用四条移动规则，产生新的状态；(3)判断新的状态是否达到目的状态，如果是，转(5)；(4)把新的状态记录下来，取出下一个中间状态作为当前状态，返回(2)；(5)输出从初始状态到目标状态的路径，结束。这个例子就是产生式系统。产生式系统的组成：产生式系统是由三个基本要素组成的：一个综合数据库（GOLBLE DATABASE），一组产生式规则（Set of rules），和一个控制系统（Control System）。1、综合数据库:它是产生式系统所有的主要数据结构。它主要表示问题的状态，即初始状态，目标状态，和中间状态等，以及状态之间的关系。它不是固定不变的，在求解过程中，它的内容将越来越多，状态之间的关系也越来越复杂。经常用来表示数据库的数据结构有串，集合，数组，树，表，记录，队列等。例题4-1八数码难题使用数组这种数据结构表示状态，若压缩数据存储，把二维数组压缩为串，则数据库采用的数据结构就是串。2、产生式规则：是对数据库进行操作的一系列规则。规则的一般形式是：if 条件 then 操作即满足应用的先决条件后，就对数据库实行后面的操作。3、控制策略：它规定了操作的顺序既在什么条件下用什么规则进行操作，什么条件下停止操作，即它规定了问题的搜索策略和路线。一般的，控制策略分为两大类：3.1不可撤回方式(IRREVOCABLE)3.2试探法(TENTATIVE)：3.2.1回溯法(BACKTRACKING)3.2.2图搜索法(GRAPH-SEARCH)4、搜索策略：搜索策略有两种基本方式：一种是不考虑给定问题的特有性质，按事先规定好的顺序依次运用规则，这是一种盲目搜索的方法，或称为无信息引导的搜索。另一种是考虑问题的特有性质，优先选用较合适的数据和规则，这称为启发式搜索，或有信息引导的搜索。目前，从这两种基本方式出发，已创造出多种具体的搜索方法。归纳起来有以下几种：(一)求任一路径的搜索策略：回朔法(Backtracking)、爬山法(Hill climbing)、深度优先搜索法(Depth-first)、广度优先搜索法(Breadth-first)、限定范围搜索法(Beam search)、最优策略(Best first)(二)求最优路径的搜索策略：大英博物馆法(British Museum)、分支定界法(Branch and Bound)、动态规划法(Dynamic Programming)、最佳图搜索法(A*)(三)与或图搜索法：一般与或图搜索法(AO*)、极大极小法(Minimax)、a-b剪枝法(Alpha-beta Pruning)、启发式剪枝法(Heuristic Purning)产生式系统的应用例题42有N枚硬币(N为偶数)正面朝上排成一排，每次将N1枚硬币翻过来放在原位置上，不断地重复上述过程，直到最后全部硬币翻成反面朝上为止。编程让计算机把翻币的最简过程及翻币次数打印出来(用x代表正面，O代表反面)。分析状态表示：显然可以用一个数组a描述当前的状态，当元素ai=“*”时，第i枚硬币朝上，ai=“o” 时，第i枚硬币朝下。移动规则：根据题意每次翻动N1枚硬币，相当于固定一枚硬币，把其他各枚硬币翻个。所以每次有n种操作方案：固定第ii1n枚硬币，使其他硬币翻面。搜索策略：把初始状态(即每一枚硬币正面朝上)作为当前状态；(1)从当前状态出发，运用移动规则，产生新的状态；(2)判断新的状态是否达到目标状态(即每一枚硬币反面朝上)，如果是，转(4)；(3)把新的状态记录下来，取出下一个中间状态作为当前状态，返回(2)；(4)输出从初始状态到目标状态的路径，结束。上面的方法只是一种盲目的枚举，而没有考虑到题目的特殊性。题目只要求一组最优解，而一枚硬币不是正面朝上就是反面朝上，所以一组硬币的状态只取决于它有几枚硬币正面朝上、有几枚硬币反面朝上，而与硬币的排列无关，故很容易推出求解此题的简易算法。请大家自己思考。例题43从一整版正方形的邮票上可以撕成各种形状的四联票。下图是几种不同形状的四联票。编程由计算机寻找并画出可撕成所有形状的四联票。 分析该题的一种解法是，先从一张邮票出发，在它的上、下、左、右分别联接上一张邮票，删去其中重复的。然后在剩下的二联票的基础上，在它们的上下左右再分别联上一张邮票，删去重复的，依此类推就可以得到问题的19个解。 (1)综合数据库：可以用二位数组来表示各种N联票，如果数组元素为1，表示该处有邮票，0表示该处没有邮票。比如图中的5种三联票，可以表示为： 111000000010110000110100000110010000100110000开始时，数据库中仅有一个元素，即1张一联票。 (2)产生规则：4条左联：if (ai,j=1) and (ai,j-1=0) then ai,j-1:=1又联：if (ai,j=1) and (ai,j+1=0) then ai,j+1:=1上联：if (ai,j=1) and (ai-1,j=0) then ai-1,j:=1下联：if (ai,j=1) and (ai+1,j=0) then ai+1,j:=1(3)控制策略可分为6步骤：S1：设I=1；S2：对所有I联票运用规则产生I+1联票；S3：对新产生的I+1联票判断是否重复，删去重复的，然后存入数据库；S4：检查所有I联票扩展完否？如果还有返回S2；S5：I增1，如果I0) then Begin if 第j本书没有分下去 and 第i个同学也喜欢这本书 then Flag:=flag+j;booki:=j; 把第j本书分出去，把书给第i个同学 if i=5 then print if 第五个同学已经有书了 then 打印结果 Else calc(i+1); 否则给第i个同学分书 Flag:=flag-j;booki:=0; End End;Begin主程序Flag:= ;c:=0;calc(1);Readlnend.状态搜索图(搜索过程)：C(1)CA(2)CAB(3)CABD(4)CABDE(5)CB(6)CE(7)CEB(8)CEBD(9)D(10)DA(11)DAB(12)DAC(13)DB(14)DBC(15)DE(16)DEB(17)DEC(18)注：（N）中的N代表结点产生的顺序。从产生的顺序可以看出，深度越大的结点越先进行扩展，即先产生它的子结点。例如，有了结点(C)和(CA)后，并不是继续产生(C)的子结点，而是先产生(CA)的子结点(CAB)。这是由于(CA)的深度是2，(C)的深度是1，(CA)的深度大，所以先扩展。这种在搜索过程中，深度大的结点先进行扩展的算法，我们就称它为深度优先搜索法。英语称之为DepthFirstSearch，简称为DFS法。上述算法实际是一个产生式系统。综合数据库就是一维数组book；产生规则是：在1至5中选择与前面已选定的数不相同的数；控制策略就是深度大的结点先扩展，深度达到5即是目标结点。深度优先搜索基本算法(一)从例题44可以看出，深度优先搜索法有两个显著特点：(1)对已产生的结点按深度排序，深度大的先得到扩展，即先产生它的子结点；(2)深度大的结点是后产生的，但先得到扩展，即“后产生先扩展”。因此用堆栈作为该算法的主要数据结构，存储产生的结点。深度优先搜索的基本算法如下：对于递归算法，递归过程为：Procedure DFSTRY(i)； For i=1 to maxr do if子结点mr符合条件then产生的子结点mr压人栈； if子结点mr是目标结点then输出 Else DFSTRY(i+1)； 栈顶元素出栈(删去Mr) Endif Enddo；主程序为：ProgramDFS 初始状态入栈； DFSTRY(1)；对于非递归算法为：ProgramDFS(dcp)； dep:=0; Repeat Dep: = dep+ 1; J: =0; p: =false; Repeat J: =j+l; If mr 符合条件then 产生子结点 mr 并将其记录; If 子结点是目标结点 then 印输出并出栈; Else p: = true; Else If j =maxi then 回溯 else p: =false; Endif; Until p= true; Until dep = 0;其中回溯过程如下：Procedure backtracking; Dep: = dep-1; If dep0 then 取回栈顶元素 EIse p: =true;不同问题的深度优先搜索基本算法是一样的，但在具体处理方法上和编程的技巧上，不尽相同，甚至会有很大的差别。例如对于例题44的解法还可以这样来设计：从表中看出，孙同学只喜爱D一本书，无其他选择余地，因此可以在搜索前确定下来，这样程序就只需对剩下的四位同学进行搜索。另外，发现“喜爱书”的数组有多个0，为减少不必要的试探，该用链表来表示。例如第三位同学的链表是：Link(3，0)=2，表示他喜爱的第一本书的编号是2；Link(3，2)=3，即表示喜爱的书2后面是3，最后Link(3，3)=0，表示3是最后一本喜爱的书。根据上面的改进，基本算法不变，程序改进如下，读者可以比较两个程序的运行时间。源程序Program ex4_4_1;Const Like:array 1.5,0.5 of byte=(3,0,0,4,0,0),(1,2,5,0,0,0),(2,0,3,0,0,0), (4,0,0,0,0,0),(2,0,5,0,0,0); name: array 1.5 of string 6 = (zhang,wang,liu,sun,li);Var Book: array 1.5 of 0.5; Flag: set of 1.5; C:integer; Procedure print; Var I: integer; Begin Inc(c);writeln(Answer,c,:); For i:=1 to 5 do Writeln(namei:10,:,chr(64+booki); End; Procedure calc(i: integer); Var j:integer; Begin if booki0 then if i=5 then print Else calc(i+1) else begin j:=likei,0; while j0 do begin if not (j in flag) then Begin Flag:=Flag+j;bookI:=j; If i=5 then print Else calc(i+1); Flag:=Flag-j;booki:=0; End; j:=likei, j end end End;BEGIN Flag:=4;book4:=4;c:=0; calc(1);ReadlnEND.深度优先搜索的应用例题45设有一个4X4的棋盘(即每行每列有四个正方形格的棋盘)，用四个棋子布到格子中，要求满足以下条件：任意两个棋子不在同一行或同一列或同一对角线上。试问有多少种棋局?编程把它们找到并打印出来。分析问题要求输出所有解，所以只能采用穷举的算法。因为每一行只有一颗棋子，所以只要枚举每一行的棋子所在的列数即可。状态表示：用一个一维数组来描述这个4X4的棋盘，Ai(i1.4)表示第i行的棋子摆在第Ai列。题目要求任意两个棋子不在同一行、列、对角线，所以还需要几个数组记录某一行或列或是对角线是否已有棋子。行：因为枚举是按行的，一行只有一颗棋子，所以不必判断。列：可以用一个b 1.4的布尔数组记录，当bi=true时表示第i列还没有棋子，否则已有棋子。对角线：每个格子所在的对角线有两条，4 X 4的棋盘分别有7条斜向上和斜向下的对角线，可用两个布尔数组c，d 1.7判断。算法分析：首先我们枚举第一行的棋子的列坐标i，选定一个后，把ai赋值为i,把它所在的列(i)、所在的两条对角线(i,i+3)的数组元素赋值为false，再搜索第二行，如此递归搜索直到第四行棋子的列坐标确定，输出。源程序program ex4_5;var t:integer; a:array 1.4 of 1.4; b:array 1.4 of boolean; c,d:array 1.7 of boolean; procedure print; var i,j:integer; begin inc(t);writeln(Answer (, t,):); for i:=1 to 4 do for j:=1 to 4 do begin if j=ai then write(*) else write(o); if j=4 then writeln end 打印一组解 end; procedure calc(i:integer); var j:integer; begin for j:=1 to 4 do if bj and ci+j-1 and dj-i+4 then begin ai:=j; if i=4 then print else begin bj:=false; ci+j-1:=false; dj-i+4:=false; calc(i+1); bj:=true; ci+j-1:=true; dj-i+4:=true end end end;begin fillchar(b,sizeof(b),true); fillchar(c,sizeof(c),true); fillchar(d,sizeof(d),true); t:=0;calc(1);readlnend.例题46覆盖问题右边长为N(偶数)的正方形，用NXN/2个长为2宽为1的长方形将它全部覆盖。编程打印所有覆盖方法。当N=4时几种覆盖方法及打印格式举例如下：124122413345668577835687分析状态表示：把这个编长为N的正方形划分为一个NXN的网格，用一个NXN的数组A来描述这个正方形，当Ai，j0时，表示这个小方格已被编号为Ai,j 1X2的长方形覆盖，当Ai，j=0时，表示这个小方格未被覆盖。搜索策略为：S1：按行优先，列优先的原则找到一个Ai，j=0的格子(i，j)；S2：如果(in) AND (ai+1，j=0)那么格子(i,j)与(i+1，j)用一个1x2的长方形覆盖，转S3；如果(j(1，2)-(2，4)-(4，3)-(5，1)-(6，3)-(8，4)分析状态表示：题目要求输出路径，而从棋盘的左下角走到右上角的步数不能确定，但每一步都只能往右走，所以最多不会超过9。因此可以用一个一维数组A19记录每一步跳到的位置(X，Y)。移动规则：马最多有4个方向，若原来的横坐标为i、纵坐标为j，则四个方向的移动可表示为：1：(i，j)-(i+1，j+2)(i4，j(i+2，j+1)(i3，j(i-1，j+2)(i0，j(i-2，j+1)(i1，j); writeln (8,4),t:5);readln end; procedure calc(i:integer); var j:integer; begin for j:=1 to 4 do if (ai-1,1+xj,1=0) and (ai-1,1+xj,1=0) and (ai-1,2+xj,2=8) then begin ai,1:=ai-1,1+xj,1;ai,2:=ai-1,2+xj,2; if(ai,1=4) and (ai,2=8) then print(i) else calc(i+1); ai,1:=0;ai,2:=0 end end;begin calc(2) gram ex4_6;var n:integer; t:longint; a:array 1.10,1.10 of integer; procedure print; var i, j: integer; begin inc(t);writeln(Answer (,t,):); for i:=1 to n do begin for j:=1 to n do write(ai,j:5); writeln end end; procedure calc(i: integer); var j,k:integer; begin j:=0; repeat j:=j+1;k:=1; while (k0) do inc(k);until k=n;找到第一个aj,k=0的格子(j,k) aj,k:=i; if (in) and (a j+1,k=0) then begin aj+1,k:=i;if i*2n*n then calc(i+1)搜索下一个长方形 else print; aj+1,k:=0 end; if (kn) and (aj,k+1=0) then begin aj,k+1:=i;if i*2n*n then calc(i+1)搜索下一个长方形 else print; aj,k+1:=0 end; aJ,k:=0 end;begin write( Input n:);readln(n); if odd(n) or (n0且CR没有到过THEN增加一个NODE元素，把新增元素赋值为：K+R；增加一个OPEN元素，记录下NODE元素的位置。源程序program ex4_8;const max=maxint; link:array 1.5, 1.6 of integer=(0,4,8,0,0,0),(4,0,3,4,6,0),(8,3,0,2,2,0),(0,4,2,0,4,9),(0,6,2,4,0,4);邻接表最后一行可以省略，因为到达c6后不能在到其他城市去type path=string6;字符串记录路径var open:array 1.6 of integer;索引表 node: array 1.100 of path;记录所有路径 count, i, n: integer; procedure calc(k,dep:integer); var r,len:byte; temp:path; begin temp:=nodeopendep;取出 node表中最后一个元素 len:=length(temp);不能再到其他城市 if pos(6,temp)0 then exit else for r:=2 to 6 do if (linkk, r0) and (pos(chr(48+r),temp)=0) then begin到达下一个城市 inc(n);noden:=temp+chr(48+r); opendep+1:=n;calc(r,dep+1) 搜索下一个城市 end end; procedure print; var f,i,j,k,l:integer;bool:array 1.100 of boolean;记录路径是否打印long:array 1.100 of integer;记录路径总长 begin count:=0; for i:=1 to n do if nodei,length(nodei)6 then booli:=false else begin booli:=true;inc(count);longi:=0; for j:=2 to length(nodei) do longi:=longi+linkord(nodei, j-1)-48,ord(nodei,j)-48; end; for i:=1 to count do begin k:=maxint; for j:=1 to n do if (boolj) and (longj,nodel, j);输出路径 writeln ( cost=, k)输出总长度 end; readln end;begin n:=1;node1:=1;open1:=1赋初值;calc(1,1);printend.11-2-3-5-6cost=1321-2-5-6cost=1431-3-5-6cost=1441-2-4-3-5-6cost=1651-2-4-5-6cost=1661-2-3-4-5-6cost=17712-4-6ccst=1781-2-3-4-6oost=1891-3-4-5-6cost=18101-3-4-6cost=19111-3-2-5-6cost=21121-2-3-5-4-6cost=22131-2-5-3-4-6cost=23141-2-5-4-6cost=23151-3-2-4-5-6cost=23161-3-5-4-6cost=23171-3-2-4-6cost=24181-3-4-2-5-6cost=24191-3-5-2-4-6cost=29201-3-2-5-4-6cost=3022深度优先搜索和广度优先搜索广度优先搜索三、广度优先搜索在深度优先搜索算法中，深度越大的结点越先得到扩展。若把它改为深度越小的结点越先得到扩展，就是广度优先搜索法，下面通过一个具体实例来讨论广度优先算法的一般规律。例题4-1八数码难题在3X3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是：找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。例如输入：（代表从前一布局到后一布局）2 8 31 6 47 0 51 2 38 0 47 6 5分析由于题目要找到的解是达到目标最少步骤，因此解题的方法为：从初始状态出发，先把移动一步后的布局全部找到，检查是否达到目标布局；如果没有，再从这些移动一步的布局出发，找到移动两步后的所有布局，再判断是否有达到目标的；如此继续，一直达到目标状态为止，输出结果。由于是按移动步数从少到多产生新布局的，所以找到的第一个目标一定是移动步数最少的一个，也就是最优解。建立产生式系统。其中：综合数据库显然用3X3的二维数组来表示布局比较直观。用ch(i,j)表示第i行第j列格子上放的棋子数字，空格则用0表示。为了方便编程，还需存储该布局的空格位置：(si,sj)；初始布局到该布局的步数，即深度dep；该布局的上一布局，即父结点的位置。这样数据库每一个元素应该是由上述几个数据组成的记录。因为新产生的结点深度(也即从初始布局到该结点的步数)一般要比数据库原有结点大(或相等)，按步数大的后扩展的要求，应该放在数据库的后面。而当前扩展的结点从数据库前面选取，即符合先产生的先扩展，后产生的后扩展规律。所以数据库的结构用队列的结构形式较合适。用上述记录为元素的数组data来表示数据库，并设置两个指针：closed为队列的首指针，open为队列的尾指针。产生规则：原规则规定空格周围的棋子可以向空格移动。但如果换一种角度观察，也可看做空格向四周移动。这样处理更便于编程。如果空格位置在(si,sj)，则有四条规则：(1)空格向上移动: If si-1=1 then ch(si,sj):=ch(si-1,sj);ch(si-1,sj):=0(2)空格向下移动: If si+1=1 then ch(si,sj):=ch(si,sj-1);ch(si,sj-1):=0(4)空格向右移动: If sj+1=closed队列空 源程序$M 65521,0,655360program ex4_1_1;const fn1=ex4_1.in; fn2=ex4_1.out;type xtype=array 1.3,1.3 of 0.8; ctype=array 1.10000 of xtype; dtype=array 1.10000 of integer;var a,b:xtype; c:ctype; dep,father:dtype; x0:array1.10000,1.2 of byte; procedure init; var f:text; i,j:integer; begin new(dep);new(father); for i:=1 to 10000 do new(ci); assign(f,fn1);reset(f); for i:=1 to 3 do begin for j:=1 to 3 do read(f,ai,j); readln(f); end; readln(f); for i:=1 to 3 do begin fo