信息学竞赛搜索专题汇总课件

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.432系统栈实例在调用过程或函数之前，系统需完成三件事：将所有的实在参数、返回地址等信息传递给被调用过程保存；为被

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,A,B,C)系统栈例线性读写操作都在栈顶先进后出栈的特点静态数组Ty

3、pe 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;栈的定义操作静态数组(A,top)动态链表(H,top)建立栈测试栈是否为空读栈顶元素进栈(push) 出栈(pop)Top:=0top:=nil;Top=0top=nil;AtopTTop:=top

4、+1; 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（0（入栈时不作优先级比较）+ -1* /2）单独处理入栈标准：优先级大于栈顶元素优先级后缀表示法栈的使用# -16 - 19* 2( 04+ 13+*-+ 15+ 16943+*-5+6-9*(4+3)+5#6-9*(4+3)+53496+1(0*2-1#-1763-57+ 15-52中缀栈求解Procedure try(I); 选择第

6、I个皇后的位置； if 安全 then (1) 放置第I个皇后； (2) if I=8 then 输出 else try(I+1); 尝试下一个位置；栈的应用八皇后（递归）13455248724648246462758245724885824762425253873837636382537335773625825523828352326374837463472486388247373663724For 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 I0 do j:=j+1; if j8

7、then 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 I0 do j:=j+1; if j 8 then top:=top-1; j:=atop; bj ctop+j dtop-j:=t; else if (top 8 then print;mm全排列非递归方式递归 回溯基本框架深度优先搜索素数环：将120这20个数摆成一个环，要求相

8、邻的两个数的和是一个素数走迷宫训练方向：上下左右方向：右下左上研究背景背包问题简单枚举有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*wIIf stmax then 记录状态；有n个背包，问题如何解决？回溯穷举A: 123450000000001000100001111111逢1进位分析问题找出实质初值：0 0 0 0 0找到需要进位的下标如何查找？N1 结束标记？实质For I:=0 to

9、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+1 to n do aI:= 0 ; 计算;-1逢1进位有n种背包，每种背包有若干个(bi)，While a0=0 do j:=n; while aj= 1 do j:=j-

10、1; aj:=aj+1; for I:=j+1 to n do aI:= 0 ; 计算;Bj相等进位从1m中任意取出n个，打印所有取法123124125134135145234235245345保证不重复选择 升序第n 位进位标志：m第n-1位进位标志：m-1第 j 位进位标志?相等进位组合问题深度优先搜索深入应用跳马周游棋盘问题一棵八叉树八个方向：目前位置(i,j)，下一个位置：可能为：(i+1,j+2),(i-1,j+2),(i-2,j+1),(i-2,j-1),(i-1,j-2),(i+1,j-2),(i+2,j-1),(i+2,j+1)用二维数组表示棋盘，未走过的地方设置为0bi1,j

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

12、0012000010101310100011140011000005000010010找出一个从入口到出口的最短路径（八个方向）迷宫问题总行数：0m+1, 总列数： 0n+1 11111111111101000100111000010101111010001111100110000011000010010111111111111在深搜过程中，记录搜索步数并与最小值进行比较，记录当前最佳方案，最后打印输出能否改进？方案1从步数的角度考虑问题，分别列举出一步能到达的结点、两步能到达的结点、发现的终点肯定是最优方案如何记录方案？记录每个结点的来由方案28个方向表示可以用数组说明：1012113104

13、1-150-16-1-17-108-11如何记录探索的踪迹？队列序号123456X123332Y123144pre012233基本如何防止重复探索：将迷宫中的0替换为-1队列中入队、出队情况如下表：迷宫问题程序迷宫（用不同的颜色表示步数）与深搜区别之一：搜索的方向不影响搜索规模主要影响因素是什么？迷宫变形：起点在迷宫中心、几乎没有障碍结论迷宫变形在宽搜过程中，队列以几何数量级扩展，扩展层数越大，对存储的威胁越大如何对存储进行压缩？双向搜索结论现要找出一条从A到B经过城市最少的一条路线。广度优先遍历: A 应用F,r,队列初始化；While f=r do 取队首； 宽搜基本框架sq1.x:=1

14、;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 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

15、，3，5，7，13，运算符号：+,*, 且运算无优先级之分，如2+3*5=25，3*5+2=17，编写一个程序，给出任意一个整数n，要求用以上的数和运算符，以最少的运算次数产生出n。 例如：n=7,7=7,（0次运算）n=93，93=13*7+2 （2次运算 ）。 例 数值计算（1）数据的结构：参加运算的数据、参加运算的符号可以用常量数组 data12，data23，参与运算数据、符号顺序 （2）每步参加运算的数据及运算符号 x, y , t：被加数、加数，结果（x ），t ：从哪一步计算到此。 分析算法模式给出一个整数n(n1030)和k个变换规则（k=R and 反面个数=5-R num=

16、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+ 在队列中只需记录正面个数翻了i个正面，(5-i)个反面的硬币后正向硬币的个数打印方向：从前往后：递归 从后望前：非递归/递归交界处重复打印翻币次数如何计算易错点最少拐弯问题作业骑士问题过河问题登山问题1345524872464824646