高中信息技术 全国青少年奥林匹克联赛教案 搜索法二VIP免费

算法在信息学奥赛中的应用（搜索法二）在深度优先搜索算法中，深度越大的结点越先得到扩展，若把它改为深度越小的结点越先得到扩展，就是广度优先搜索法。广度优先搜索基本算法：programbfs;初始化；建立队列data;设队列首指针closed:=0;队列尾指针open:=1;repeatclosed增1，取出closed所指结点进行扩展；fori:=1tordobeginif子结点符合条件thenbeginopen增1，并把新结点存入数据库队尾；if新结点与原有结点有重复then删于该结点(open减1)elseif新结点即目标then输出并退出;end{if};end{for};untilclosed>=open;{队列为空}使用广度优先搜索时，离根结点最近的结点先扩展，所以广度优先搜索法比较适合求步数最少的解，由于深度优先使用了标志法，使得存储空间大大减少，而广度优先要保留所有搜索过的节点，随着搜索程度的加深，所需的存储空间成指数增加。因此在必要时我们采用双向搜索来减少搜索空间和存储空间，如下面的例子。广度优先算法应用例字串变换（NOIP2002tg）[问题描述]:已知有两个字串A$,B$及一组字串变换的规则（至多6个规则）:A1$->B1$A2$->B2$规则的含义为：在A$中的子串A1$可以变换为B1$、A2$可以变换为B2$…。例如：A$＝'abcd'B$＝'xyz'变换规则为：‘abc’->‘xu’‘ud’->‘y’‘y’->‘yz’则此时，A$可以经过一系列的变换变为B$，其变换的过程为：‘abcd’->‘xud’->‘xy’->‘xyz’共进行了三次变换，使得A$变换为B$。[输入]:键盘输人文件名。文件格式如下：A$B$A1$B1$\A2$B2$|->变换规则....../所有字符串长度的上限为20。[输出]:输出至屏幕。格式如下：若在10步（包含10步）以内能将A$变换为B$，则输出最少的变换步数；否则输出"NOANSWER!"[输入输出样例]b.in:abcdxyzabcxuudyyyz屏幕显示：3算法分析：此题是求变换的最少步数，很显然可以使用广度优先搜索法，如果直接从初状态搜到目标状态，最坏情况下存储的结点数超过6的10次方幂，搜索空间过大，因此我们考虑使双向搜索，同时从初始状态和目标状态向中间状态搜索，当相遇时搜索结束。采用双向搜索，存储的结点数还有可能超限，我们在前向搜索队列中存储5步内变换的结点，在后向搜索队列中，由于第5步产生的结点只是用来与前向队列中的结点比较，所以可以不存储在队列中，后向搜索队列只需存储4步内的结点，这样就解决了存储空间问题。为了使用方便，在程序设计中用一个数组a[1..max]存储两个队列，前向搜索队列为a[1..mid]，后向搜索队列为a[mid..max]，用st存储搜索方向，st=0表示前向搜索，st=1表示后向搜索，用op[st]和cl[st]分别表示队列尾指针和首指针，用be表示队列起始位置，循环产生每一个结点，若在10内无解退出循环，若在10内找到解则输出解并退出程序。源程序：constmid=12000;max=16000;typenode=records:string;x:byte;end;vari,mark:integer;a:array[1..max]of^node;x:array[0..6,0..1]ofstring[20];d,fil:string;op,cl:array[0..1]ofinteger;procedureInit;{读取数据，初始化}varf:text;t:string;beginreadln(fil);assign(f,fil);reset(f);i:=0;whilenoteof(f)dobeginreadln(f,t);x[i,0]:=copy(t,1,pos('',t)-1);x[i,1]:=copy(t,pos('',t)+1,length(t));inc(i);end;{while}mark:=i-1;close(f);end;{判断是否到达目标状态}procedurebool(be,st:integer);beginfori:=mid-be+1tocl[1-st]doifa[cl[st]]^.s=a[i]^.sthenbeginwriteln(a[cl[st]]^.x+a[i]^.x);halt;end;{if}end;{判断节点是否与前面的结点重复}procedurecheck(be,st:integer);beginfori:=be+1tocl[st]-1doifa[i]^.s=a[cl[st]]^.sthenbegindec(cl[st]);exit;end;bool(be,st);end;{扩展产生新节点}procedureexpand(be,st:integer);vari,j,k,lx,ld:integer;begininc(op[st]);d:=a[op[st]]^.s;k:=a[op[st]]^.x;ld:=length(d);fori:=1tomarkdobeginlx:=length(x[i,st]);forj:=1tolddobeginif(copy(d,j,lx)=x[i,st])thenbeginif(st<>1)or(k<>4)thenbegininc(cl[st]);new(a[cl[st]]);end;{if}a[cl[st]]^.s:=copy(d,1,j-1)+x[i,1-st]+copy(d,j+lx,ld);a[cl[st]]^.x:=k+1;check(be,st);{检查是否重复}end;{if}end;{for}end;{for}end;pro...