奥赛搜索算法讲稿

搜索算法讲一、预备知识——树（图）的深度优先遍历（DFS）和广度优先遍历（DFS）树的广度优先遍历（BFS）的方法实质是按层来遍历这棵树：从根结点出发，了根结点之后根结点（BFSDFS递归BFSDFSBFS二、搜索算法概索过程际上是据初始件和展规则构一“解答树并寻找合目标的节点（：（DFS；（BFS（例1、分溶剂问题：有2个，容量分别为x毫升、y毫升，在一个实验瓶中装有x+y毫升的化学‘NO!（3，5，0（5，0，3三、深度优先搜索算（ConstMaxd=100;Type Varf:Array[1..Maxd]ofnode;已纵深方向上已经扩展出的结点（栈Proceduredfs(dep:Integer);Varc:Integer;If(f[dep].a=(x+y)div2)and(f[dep].x=(x+y)div2)thenBeginoutans(dep);exitEnd;Forc:=1to6Ifexpandok(f[dep].a,f[dep].x,f[dep].y,dep,c)then扩展结点6depc1、某个容器里溶剂量为0，则不能向其他容器倾倒液体2、某个容器已经装满，则不能向这个容器倾倒液3、前面已经存在的结点不能继续扩展Vari,tmp:Integer;casecof1:If(sa=0)or(sx=x)thenBeginexpandok:=false;exitEnd;A->XA0X2:If(sa=0)or(sy=y)thenBeginexpandok:=false;exitEnd;A->yA0y3:If(sx=0)thenBeginexpandok:=false;exitEnd;X->AX0，则不能扩展4:If(sx=0)or(sy=ythenBeginexpandok:=false;exitEnd;X->YX0Y5:If(sy=0thenBeginexpandok:=false;exitEnd;Y->AY0，6:If(sy=0)or(sx=xthenBeginexpandok:=false;exitEnd;Y->XY0Xcasec1:BeginIftmp>xthensx:=xelse AXAXsa:=tmp-sxEnd;2:Begintmp:=sa+sy;Iftmp>ythensy:=yelse AYAYsa:=tmp-sy3:Beginsa:=sa+sx;sx:=0 XAXA4:BeginIftmp>ythensy:=yelse XYXYsx:=tmp-sy5:Beginsa:=sa+sy;sy:=0 YAYA6:BeginIftmp>xthensx:=xelse YXYXsy:=tmp-sxEnd;Fori:=1todIf(sa=f[i].a)and(sx=f[i].x)and(sy=f[i].y) Beginexpandok:=False;exitf[d+1].a:=sa;f[d+1].x:=sx; outans(dep);输出一个解：Vari:Integer;Fori:=1tod-1do路径长为 procedureprocedureiifthenbeginexitEnd;nforj:=todoif剪枝thenDFS(dep+1);2、分析搜索的“上界”和“下界使分枝尽量减少3、搜索前预处理一些数据，达到简化搜索的目的4、加强剪枝（着就是能力和水平的问题了下面来看几个简单例子编程列举出1、2、…、n全排列。具体到本题，我们假设n=3时，如下图：位置1可以放置数字1、2、3；位置2可以放置数字1、2、3；位3可以放置数字12、3，但是当位置1放了1后位置2位置3不能在放1，因此画树的约束条件是：23，用“╳”标示的分支表示该结点不满足约束条件，不能被扩展出来：我们用递归过程来描述“解答树”PascalprocedureDFS(i:integer);Varc:integer;Ifi>3thenBeginexitEnd;Forc:=1to3doIfused(c)=falseThenused[c]:=true;a[i]:=c;3ic请同学自己将这个程序完善，并在机器上调试通：素数环：1n步骤1、画解答树（n=3步骤2、确定约束条件和剪枝函ok(i-ok(i-这里我们用数组used[i]来表示数字i是否已经使用过Ifused[i]=falsetheniIfused[i]=Truetheni函数Ok(i,j)是判断a[i-1]+a[i]是否是素数(其中j是待填入a[I]的数FunctionFunctionok(i,j:Integer):boolean;Varc,s:integer;Ifi=0thenbeginok:=true;exitEnd;P:=true;s:=a[i]+j;Forc:=2totruncc(sqrt(s))Ifsmodc=0thenBeginp:=false;breakIfi=n-1then 由于是环，因此当jna[1]的和也是素数Forc:=2totruncc(sqrt(s))Ifsmodc=0thenBeginp:=false;break步骤3、写搜索程序（与上例一样ProcedureProceduretry(i:integer)a[i]填数}Varc:integer;Ifi>nthenBeginoutans;exitEnd;{如果找到一种填法，则输出}Forc:=1tondo {a[i]中可以填入数字1、2、3、…、n} 自己将该程序完例4、数的划nk1，1，5;1，5，1;输入：n，k(6<n<=200，2<=k<=6)输入：7输出：41n=3，m=2。2②假设n已经分解成了a[1]+a[2]+…+a[i]，则a[I+1]的最大值为：k=a[1]+a[2]+…+a[i]；a[I+1]<=(n-k)div(m-i)所以扩展结点时的“上界”是(n-k)div(m-请画出n=7m=3时，加上约束条件的解答树3、搜索过程ProcedureProcedure VarIf(dep=m)and(k>=a[dep-1])ThenInc(ans);exit;Forc:=a[dep-1]tokdiv(m-dep)doa[dep]:=c;solve(k-c,dep+1)eat和aoneaonat和aenn<=20)n行每行有一个单词，输入的最后一行为一个 5a23（连成的“龙”为atouche 龙长度= Function Function VarL1,L2,L:Integer;L1:=Length(s[i]);L2:=Length(s[j]);len:=-1;L:=1;While(L<l1)and(L<l2)doIfs1=s2thenBeginlen:=length(s[j])-l;exitEnd;Procedurelinktable;Vari,j:Integer;Fori:=1ton Forj:=1tondo2used[1..Maxn]of0..2，来记录每个单词的使用Proceduresolove(i,ans:Integer);IProceduresolove(i,ans:Integer);I，ansVarIfbest<ansthenForc:=1ton Forb:=1to2do If(used[c]>0)and(link[i,c]>0)Thenused[c]:=used[c]-1;ans:=ans+link[i,c]; Fori:=1tonIfc=s[i][1]then6、虫食 其中#53，第二行的5。首先，我们只考虑加法的虫食算。这里的加法是NN0。NN个大写字母来表示这个0N-1N个不同的数字（N0N-1N个字 NN个不同的字母分别代表的数字，使得该加法算式成立。输入26字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从到低位，并且恰好有N位。A，B，C……所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。5103430%的数据，保证有N10；50%的数据，保证有N15；N26。ConstVarused:Array[0..Maxn-1]ofinteger;ans:Array['A'..'Z']ofInteger;ProcedureVarProcedureVark:Integer;Ifdep>n-1ThenIfcheckThenBeginoutans;haltFork:=0ton-1doIfused[k]=0thenFunctionFunctionVarg,m,k:Integer;cc:Array[1..Maxn]OfInteger;g:=0;check:=True;Fork:=ndownto1docc[k]:=mmodn;g:=mdivIfg>0thenBegincheck:=False;exitEnd;如果和的位数超过了n，Fork:=1tonIfans[c[k]]<>cc[k]ThenBegincheck:=False;exitEnd;a、b、cc=(a+b)modnor(c=(a+b+1)moda、bc：(c=(a+b)modnor(c=(a+b+1)modb、ca：(a=(c-b+n)modn)or(a=(c-b+n+1)moda、cb（b=(c-a+n)modn）or(b=(c-a+n+1)modFunctionFunctionVarFork:=ndownto1if(ans[a[k]]>=0)and(ans[b[k]]>=0)and(ans[c[k]]>=0)thenpp1:=(ans[a[k]]+ans[b[k]])modn;pp2:=(pp1+1)modn;Ifnot((ans[c[k]]=pp1)or(ans[c[k]]=pp2))thenBegincheck1:=False;exitEnd;Fork:=ndownto1if(ans[a[k]]>=0)and(ans[b[k]]>=0)and(ans[c[k]]=-1)thenpp1:=(ans[a[k]]+ans[b[k]])modn;pp2:=(pp1+1)modn;If(used[pp1]=1)and(used[pp2]=1)thenBegincheck1:=False;exitEnd;Fork:=ndownto1if(ans[a[k]]>=0)and(ans[b[k]]=-1)and(ans[c[k]]>=0)thenpp1:=(ans[c[k]]-ans[a[k]]+n)modIfpp2<0thenpp2:=pp2+n;If(used[pp1]=1)and(used[pp2]=1)thenBegincheck1:=False;exitEnd;Fork:=ndownto1if(ans[a[k]]=-1)and(ans[b[k]]>=0)and(ans[c[k]]>=0)thenpp1:=(ans[c[k]]-ans[b[k]]+n)modIfpp2<0thenpp2:=pp2+n;If(used[pp1]=1)and(used[pp2]=1)thenBegincheck1:=False;exitEnd; 完善上面的程序，并在机器上通过Const Type Varf:Array[1..Maxd]ofnode;按层已经扩展出的结点（队列ProcedureVarh:=1;While(r<Maxn-6)and(h<=r)doForc:=1to6doIfexpandok(f[h].a,f[h].x,f[h].y,r,c)ThenBeginr:=r+1;f[r].parent:=hEnd;If(f[r].a=(x+y)div2)and(f[r].x=(x+y)div2)ThenBeginoutans(r);haltEnd;If(h>Maxn-6)or(h>r)Thenwri n('Noanswer!');expandok(f[h].a,f[h].x,f[h].y,r,c)与前面深度优先搜索一样；outans(r)用递归；书写如下：ProcedureProcedureoutans(r:Integer);Iff[r].parent>0Thenoutans(f[r].parent);Const mov:Array[1..4,1..2ofinteger=((-2,1),(-1,2),(1,2),(2,1Type Varq:Array[1..Maxnof 算法 ProcedureProcedureVarh,r,c,x,y:Integer;h:队首、rh:=1;r:=1;Whilenot(find)andh<=r Forc:=1to