高中信息技术 全国青少年奥林匹克联赛教案 搜索法二 (2).doc

算法在信息学奥赛中的应用（搜索法二）在深度优先搜索算法中，深度越大的结点越先得到扩展，若把它改为深度越小的结点越先得到扩展，就是广度优先搜索法。广度优先搜索基本算法：program bfs;初始化；建立队列data;设队列首指针closed:=0;队列尾指针open:=1;repeatclosed 增1，取出closed所指结点进行扩展； for i:=1 to r do begin if 子结点符合条件then begin open增1，并把新结点存入数据库队尾；if新结点与原有结点有重复 then 删于该结点(open减1)else if 新结点即目标 then 输出并退出 ; endif; endfor;until closed=open;队列为空使用广度优先搜索时，离根结点最近的结点先扩展，所以广度优先搜索法比较适合求步数最少的解，由于深度优先使用了标志法，使得存储空间大大减少，而广度优先要保留所有搜索过的节点，随着搜索程度的加深，所需的存储空间成指数增加。因此在必要时我们采用双向搜索来减少搜索空间和存储空间，如下面的例子。广度优先算法应用例 字串变换（noip2002tg）问题描述:已知有两个字串 a$, b$ 及一组字串变换的规则（至多6个规则）:a1$ - b1$a2$ - b2$ 规则的含义为：在 a$中的子串 a1$ 可以变换为 b1$、a2$ 可以变换为 b2$ 。例如：a$abcdb$xyz 变换规则为：abc-xuud-yy-yz则此时，a$ 可以经过一系列的变换变为 b$，其变换的过程为：abcd-xud-xy-xyz 共进行了三次变换，使得 a$ 变换为b$。输入:键盘输人文件名。文件格式如下：a$ b$a1$ b1$ a2$ b2$ |- 变换规则. . /所有字符串长度的上限为 20。输出:输出至屏幕。格式如下：若在 10 步（包含 10步）以内能将 a$ 变换为 b$ ，则输出最少的变换步数；否则输出no answer!输入输出样例b.in:abcd xyzabc xuud yy yz屏幕显示：3算法分析：此题是求变换的最少步数，很显然可以使用广度优先搜索法，如果直接从初状态搜到目标状态，最坏情况下存储的结点数超过6的10次方幂，搜索空间过大，因此我们考虑使双向搜索，同时从初始状态和目标状态向中间状态搜索，当相遇时搜索结束。采用双向搜索，存储的结点数还有可能超限，我们在前向搜索队列中存储5步内变换的结点，在后向搜索队列中，由于第5步产生的结点只是用来与前向队列中的结点比较，所以可以不存储在队列中，后向搜索队列只需存储4步内的结点，这样就解决了存储空间问题。为了使用方便，在程序设计中用一个数组a1.max存储两个队列，前向搜索队列为a1.mid，后向搜索队列为amid.max，用st存储搜索方向，st=0表示前向搜索，st=1表示后向搜索，用opst和clst分别表示队列尾指针和首指针，用be表示队列起始位置，循环产生每一个结点，若在10内无解退出循环，若在10内找到解则输出解并退出程序。源程序：const mid=12000;max=16000;type node=record s:string;x:byte;end;var i,mark:integer; a:array 1.maxof node; x:array0.6,0.1of string20; d,fil:string; op,cl:array 0.1 of integer;procedure init;读取数据，初始化var f:text;t:string;begin readln(fil); assign(f,fil);reset(f);i:=0; while not eof(f) do begin readln(f,t); xi,0:=copy(t,1,pos( ,t)-1); xi,1:=copy(t,pos( ,t)+1,length(t); inc(i); end;while mark:=i-1;close(f);end;判断是否到达目标状态procedure bool(be,st:integer);begin for i:=mid-be+1 to cl1-st do if aclst.s=ai.s then begin writeln(aclst.x+ai.x); halt; end;ifend;判断节点是否与前面的结点重复procedure check(be,st:integer);begin for i:=be+1 to clst-1 doif ai.s=aclst.s thenbegin dec(clst);exit; end; bool(be,st);end; 扩展产生新节点procedure expand(be,st:integer);var i,j,k,lx,ld:integer;begin inc(opst);d:=aopst.s; k:=aopst.x;ld:=length(d); for i:=1 to mark do begin lx:=length(xi,st); for j:=1 to ld do begin if (copy(d,j,lx)=xi,st) then begin if (st1)or(k4)then begin inc(clst); new(aclst); end;if aclst.s:= copy(d,1,j-1)+ xi,1-st+ copy(d,j+lx,ld); aclst.x:=k+1; check(be,st);检查是否重复 end;if end;for end;forend;procedure bfs;var be,k,st:integer;begin for st:=0 to 1 do begin if st=0 then be:=0 else be:=mid; opst:=be+0;clst:=be+1; new(aclst); aclst.s:=x0,st; aclst.x:=0; end;for repeat if (op0cl0)and(acl0.x=5)then expand(0,0); if (op1cl1)and(acl1.x=cl0)or(acl0.x5)or(op1=cl1)or (acl1.x5);end;begin init;bfs;writeln(no answer!)end.两种搜索算法的比较：搜索方式扩展方式数据结构适合求解的问题深度优先后产生先扩展栈