信息学竞赛搜索专题汇总.ppt

1、搜索算法,搜索,给出初始节点，要求寻找到符合约束条件的目标节点 给出初始节点和目标节点，要求找到从初始节点到目标节点的一条路径。 最优解？较优解？全部解？,搜索算法,枚举 广度优先搜索 深度优先搜索、回溯 A*,深度优先,栈Why State? 搜索深度优先搜索 递归（系统栈） 回溯（人工栈的维护） 什么是栈？,Function jc(n:integer):integer; begin if n=1 then jc:=1 else jc:=n*jc(n-1); end; Begin write(jc(4); End.,4,3,2,系统栈实例,在调用过程或函数之前，系统需完成三件事： 将所有的实

2、在参数、返回地址等信息传递给被调用过程保存； 为被调用过程的局部变量分配存储区； 将控制转移到被调过程的入口。 从被调用过程返回调用过程之前，系统也应完成三件工作： 保存被调过程的计算结果； 释放被调过程的数据区； 依照被调过程保存的返回地址将控制转移到调用过程。当有多个过程构成嵌套调用时，按照“后调用先返回”的原则,系统栈,汉诺塔（tower of Hanoi）问题。 Procedure move(n:integer; A,B,C:char); if n=1 then AC else move(n-1，A，C，B) AC move(n-1，B，A，C) 请写出系统栈的变化过程 move(3,

3、A,B,C),系统栈例,线性 读写操作都在栈顶 先进后出,栈的特点,静态数组 Type arr=array1.n of integer; stack=record vec:arr; top:integer; end; Var s:stack;,Var stack:arr; top:integer;,动态链表 Type link=node; node=record info:integer; next:link; end; Var stack:link; top:link;,栈的定义,Top:=0,top:=nil;,Top=0,top=nil;,Atop,T,Top:=top+1

4、; atop:=;,？,Top:=top-1;,？,栈的基本操作,入栈顺序为1,2,3,n，出栈序列为p1,p2,p3,pn，已知p1=n，则pi=? 入栈顺序为1,2,3,n，出栈序列为p1,p2,p3,pn，已知pn=1，则pi=? 栈s初始为空，有元素1,2,3,4,5，现进行进、进、进、初、进、出、进，问：出栈序列，栈顶指针，栈顶元素,应用举例,元素e1,e2,e3,e4,e5,e6依次通过栈s，若出栈顺序为2,4,3,6,5,1，则栈s的容量至少为？ 车厢重组：1,2,3,4,5进站，第一个到达出口的是3号车厢，问：可能的排列总数？,应用举例,中缀表示法 运算优先级问题、括号的出现改

5、变运算顺序 后缀表示法（逆波兰式）-一次扫描,栈的简单应用表达式,3/5+6 3 5 / 6 + 6-9*(4+3)+5 6 9 4 3 + * - 5 + 转换方法 2*(x+y)/(1-x) (25+x)*(a*(a+b)+b),后缀表示法,6-9*(4+3)+5 优先级,后缀表示法栈的使用,# -1,6,- 1,9,* 2,( 0,4,+ 1,3,+,*,-,+ 1,5,+,+ 1,6943+*-5+,6-9*(4+3)+5#,6-9*(4+3)+5,7,63,-57,+ 1,5,-52,中缀栈求解,Procedure try(I); 选择第I个皇后的位置； if 安全 then (1)

6、 放置第I个皇后； (2) if I=8 then 输出 else try(I+1); 尝试下一个位置；,栈的应用八皇后（递归）,For j:=1 to 8 do if bj and cI+j and dI-j then ai:=j; bj:=f; cI+j:=f; dI-j:=f; if I8 then try(I+1) else print; bj:=t; cI+j:=t; dI-j:=t; 栈：I、 j 系统维护 b 、c、 d 手动维护 递归调用返回即回溯,Procedure try(I);,Top:=1; j:=0; While top0 do j:=j+1; if j8 then

7、top:=top-1; j:=atop; bj ctop+j dtop-j:=t; else if (top8 then print;,八皇后非递归,For j:=1 to 8 do if bj and cI+j and dI-j then ai:=j; bj:=f; cI+j:=f; dI-j:=f; if I 8 then try(I+1) else print; bj:=t; cI+j:=t; dI-j:=t;,m,m,全排列递归,Top:=1; j:=0; While top0 do j:=j+1; if j 8 then top:=top-1; j:=atop; bj ctop+j

8、dtop-j:=t; else if (top 8 then print;,m,m,全排列非递归,方式 递归 回溯 基本框架,深度优先搜索,素数环：将120这20个数摆成一个环，要求相邻的两个数的和是一个素数 走迷宫,训练,方向：上下左右,方向：右下左上,研究背景,背包问题简单枚举 有5个背包（不可拆分），背包的价值(w)、体积(t)各不相等，在容量(tj)范围内，如何选取，使价值最大？,For a1:=0 to 1 do for a2:=0 to 1 do for a5:=0 to 1 do P;,St:=aI*tI; Sw:=aI*wI If stmax then 记录状态；,有n个背包，

9、问题如何解决？,回溯穷举,A:,逢1进位,分析问题找出实质,初值：0 0 0 0 0 找到需要进位的下标 如何查找？ N1 结束标记？,实质,For I:=0 to n do aI:=0; While a0=0 do j:=n; while aj=1 do j:=j-1; aj:=aj+1; for I:=j+1 to n do aI:=0; 计算P; 打印；,程序框架逢1进位,N个砝码（1，3，9，3n-1）可以放在重物一侧，也可以放在砝码一侧，给出一个重量，问：如何称？,While a0=0 do j:=n; while aj=1 do j:=j-1; aj:=aj+1; for I:=j

10、+1 to n do aI:= 0 ; 计算;,-1,逢1进位,有n种背包，每种背包有若干个(bi)，,While a0=0 do j:=n; while aj= 1 do j:=j-1; aj:=aj+1; for I:=j+1 to n do aI:= 0 ; 计算;,Bj,相等进位,从1m中任意取出n个， 打印所有取法,保证不重复选择 升序,第n 位进位标志：m 第n-1位进位标志：m-1 第 j 位进位标志?,相等进位组合问题,深度优先搜索深入应用,跳马周游棋盘问题,一棵八叉树 八个方向：目前位置(i,j)，下一个位置：可能为： (i+1,j+2),(i-1,j+2),(i-2,j+1

11、),(i-2,j-1),(i-1,j-2),(i+1,j-2),(i+2,j-1),(i+2,j+1) 用二维数组表示棋盘，未走过的地方设置为0 bi1,j1 0 当棋格 ( i1, j 1) 未被占据 i 当棋格 ( i1, j1) 在第 i 次移动中被占据 范围：未走过的和不越出棋盘边界的那些位置 为了防止马跳出棋盘，将棋盘扩大二圈，这些位置的表示设置为-1,分析,缩小搜索范围避免无效搜索 改变搜索次序在几个可能到达的位置中根据优劣条件选择一个最优点来跳马 剪枝,深度优先搜索的优化方法,编一个程序，找出一条通过迷宫的路径。这里显示为1的单元表示走不通，将一只老鼠从入口处经过迷宫到出口处的通

12、路一一打印出来。,入口 出口,迷宫问题,基本题,16,找出一个从入口到出口的最短路径（八个方向）,迷宫问题,总行数：0m+1, 总列数： 0n+1,在深搜过程中，记录搜索步数并与最小值进行比较，记录当前最佳方案，最后打印输出 能否改进？,方案1,从步数的角度考虑问题，分别列举出一步能到达的结点、两步能到达的结点、发现的终点肯定是最优方案 如何记录方案？ 记录每个结点的来由,方案2,8个方向表示可以用数组说明：,如何记录探索的踪迹？ 队列,基本,如何防止重复探索：将迷宫中的0替换为-1 队列中入队、出队情况如下表：,迷宫问题,程序,迷宫（用不同的颜色表示步数）,与深搜区别之一：搜索的方向不影响搜

13、索规模 主要影响因素是什么？ 迷宫变形：起点在迷宫中心、几乎没有障碍,结论,迷宫变形,在宽搜过程中，队列以几何数量级扩展，扩展层数越大，对存储的威胁越大 如何对存储进行压缩？双向搜索,结论,现要找出一条从A到B经过城市最少的一条路线。,广度优先遍历: A ,应用,F,r,队列初始化； While f=r do 取队首；,宽搜基本框架,sq1.x:=1 ;sq1.y:=1 ;sq1.pre:=0 ; front :=1; rear :=1 ; mg1,1:=-1 ; while front=rear do x:=sqfront.x ; y:= sqfront.y ; for v:=1 to 8

14、do I:=x+zv.x ; j:= y+zv.y ; if mgI,j =0 then rear :=rear+1 ; sqrear.pre:=front ; sqrear.x:=I ; sqrear.y:=j ; mgI,j:= -1 ; if ( i=m ) and (j=n) then print; front := front+1 ;,设有数字2，3，5，7，13，运算符号：+,*, 且运算无优先级之分，如2+3*5=25，3*5+2=17，编写一个程序，给出任意一个整数n，要求用以上的数和运算符，以最少的运算次数产生出n。 例如：n=7,7=7,（0次运算）n=93，93=13*7

15、+2 （2次运算 ）。,例 数值计算,（1）数据的结构：参加运算的数据、参加运算的符号可以用常量数组 data12，data23，参与运算数据、符号顺序 （2）每步参加运算的数据及运算符号 x, y , t：被加数、加数，结果（x ），t ：从哪一步计算到此。,分析算法模式,给出一个整数n(n1030)和k个变换规则（k=15）。 规则： 1个数字可以变换成另一个数字 规则的右部不能为零。 例如：n=234，有规则（k=2）： 2 5 3 6,例 产生数,例题4 有10升油在10升的容器中，另有两个7升和3升的空容器，现要求用这三个容器倒油，使得最后在10升和7升的容器中各有5升油。 题解 三

16、个容器可以看作三个变量 C10，C7，C3，每次倒油的可能性只有如下六种情况： C10 向 C7 倒油 C10 向 C3 倒油 C7 向 C10 倒油 C7 向 C3 倒油 C3 向 C10 倒油 C3 向 C7 倒油,例 倒油,一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。 如:阵列 0 2 3 4 5 0 0 0 6 7 1 0 3 4 5 6 0 5 0 0 2 0 4 5 6 0 0 6 7 1 0 0 0 0 0 0 0 0 8 9 有4个细胞。,细胞问题,有N个硬币（N6）正面朝上排成一排，每次将5

17、个硬币翻过来放在原位置，直到最后全部硬币翻成反面朝上为止。编程让计算机找出步数最少的方法并把翻币过程及次数打印出来。（用O表示正面，用*表示反面）。,翻币问题,分析： 每次翻R个正面，可行性判断 正面个数=R and 反面个数=5-R num=R and (10-num)=5-R num=R and num-R=5 0=num-R=5 R=05,翻币问题,问题求解模式：状态A-状态B且AB同质 正向队列Q1（队列首为起始状态A） 反向队列Q2（队列首为目标状态B）,双向搜索,while (f1=r1) and (f2=r2) do data1=q1f1 for i=1 to 方案总数 计算得新状态temp1 if 为新状态 (在q1内比对判重) 入队q1 if 与q2有相同状态(在q2内比对判重) then 终止搜索，得到解决方案 data2=q2f2 for i=1 to 方案总数 计算得新状态temp2 if 为新状态(在q2内比对判重) 入队q2 if 与q1有相同状态(在q1内比对判重 ) then 终止搜索，得到解决方案 f1+; f2+,在队列中只需记录正面个