信息学竞赛搜索专题

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

2、前，系统需完成三件事：在调用过程或函数之前，系统需完成三件事：将所有的实在参数、返回地址等信息传递给被调用将所有的实在参数、返回地址等信息传递给被调用过程保存；过程保存；为被调用过程的局部变量分配存储区；为被调用过程的局部变量分配存储区；将控制转移到被调过程的入口。将控制转移到被调过程的入口。从被调用过程返回调用过程之前，系统也应完从被调用过程返回调用过程之前，系统也应完成三件工作：成三件工作：保存被调过程的计算结果；保存被调过程的计算结果；释放被调过程的数据区；释放被调过程的数据区；依照被调过程保存的返回地址将控制转移到调用过依照被调过程保存的返回地址将控制转移到调用过程。当有多个过程构成嵌

3、套调用时，按照程。当有多个过程构成嵌套调用时，按照“后调用先后调用先返回返回”的原则的原则系统栈系统栈NJOI汉诺塔（汉诺塔（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)系统栈例NJOI 线性 读写操作都在栈顶 先进后出栈的特点NJOI 静态数组Type arr=array1.n of integer; stack=record vec:a

4、rr; top:integer; end;Var s:stack;Var stack:arr; top:integer; n动态链表Type link=node; node=record info:integer; next:link; end;Var stack:link; top:link;栈的定义NJOI操作静态数组(A,top)动态链表(H,top)建立栈测试栈是否为空读栈顶元素进栈(push) 出栈(pop)Top:=0top:=nil;Top=0top=nil;AtopTTop:=top+1; atop:=;？Top:=top-1; ？头插法栈的基本操作NJOI 入栈

5、顺序为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，现进行进、进、进、初、进、出、进，问：出栈序列，栈顶指针，栈顶元素应用举例NJOI 元素e1,e2,e3,e4,e5,e6依次通过栈s，若出栈顺序为2,4,3,6,5,1，则栈s的容量至少为？ 车厢重组：1,2,3,4,5进站，第一个到达出口的是3号车厢，问：可能的排列总数？应用举例NJOI 中缀表示法 运算优先级问题、括号的出现改变运算顺序 后缀表示法（逆波兰式）-一次扫描栈的简单应用表

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

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

8、+1; if j8 then top:=top-1; j:=atop; bj ctop+j dtop-j:=t; else if (top8 then print;八皇后非递归NJOIFor 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全排列非递归NJOI 方式 递归 回溯 基本框架深度优先搜索N

9、JOI 素数环：将120这20个数摆成一个环，要求相邻的两个数的和是一个素数 走迷宫训练NJOI方向：上下左右NJOI方向：右下左上研究背景研究背景NJOI背包问题简单枚举有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个背包，问题如何解决？回溯穷举NJOIA: 123450000000001000100001111111逢1进位分析问题找出实质N

10、JOI 初值：0 0 0 0 0 找到需要进位的下标 如何查找？ N1 结束标记？实质NJOIFor 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进位NJOI 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 ; 计算;-

11、1逢1进位NJOI 有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相等进位NJOI 从1m中任意取出n个，打印所有取法123124125134135145234235245345保证不重复选择 升序第n 位进位标志：m第n-1位进位标志：m-1第 j 位进位标志?相等进位组合问题JSOI深度优先搜索深入应用NJOI跳马周游棋盘问题NJOI 一棵八叉树八个方向：目前位置(i,j)，下一个位置：可能为：(i+1,j+2),(i-1,j+

12、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,j1 0 当棋格当棋格 ( i1, j 1) 未被占据未被占据 i 当棋格当棋格 ( i1, j1) 在第在第 i 次移动中被占据次移动中被占据 范围：未走过的和不越出棋盘边界的那些位置 为了防止马跳出棋盘，将棋盘扩大二圈，这些位置的表示设置为-1分析NJOI 缩小搜索范围避免无效搜索 改变搜索次序在几个可能到达的位置中根据优劣条件选择一个最优点来跳马 剪枝深度优先搜索的优化方法NJOI 编一个程序，找出一条通过迷宫的路径

13、。这里编一个程序，找出一条通过迷宫的路径。这里显示为显示为1的单元表示走不通，将一只老鼠从入口处经过迷宫到出的单元表示走不通，将一只老鼠从入口处经过迷宫到出口处的通路一一打印出来。口处的通路一一打印出来。010000001000010001100000111001100000 000000010入口 出口 迷宫问题NJOI基本题 16NJOI12345678910100010012000010101310100011140011000005000010010找出一个从入口到出口的最短路径（八个方向）迷宫问题总行数：总行数：0m+1, 总列数：总列数： 0n+1 1111111111110100

14、0100111000010101111010001111100110000011000010010111111111111NJOI 在深搜过程中，记录搜索步数并与最小值进行比较，记录当前最佳方案，最后打印输出 能否改进？方案1NJOI 从步数的角度考虑问题，分别列举出一步能到达的结点、两步能到达的结点、发现的终点肯定是最优方案 如何记录方案？ 记录每个结点的来由方案28个方向表示可以用数组说明：个方向表示可以用数组说明：10121131041-150-16-1-17-108-11如何记录探索的踪迹？如何记录探索的踪迹？队列队列序号序号 123456X123332Y123144pre012233

15、基本NJOI如何防止重复探索：将迷宫中的如何防止重复探索：将迷宫中的0替换为替换为-1队列中入队、出队情况如下表：队列中入队、出队情况如下表：迷宫问题NJOI程序 1 2 3 4 5 6 7 8 91 0 1 0 0 0 1 0 0 12 0 0 0 0 1 0 1 0 13 1 0 1 0 0 0 1 1 14 0 0 1 1 0 0 0 0 05 0 0 0 0 1 0 0 1 0迷宫（用不同的颜色表示步数）NJOI 与深搜区别之一：搜索的方向不影响搜索规模 主要影响因素是什么？ 迷宫变形：起点在迷宫中心、几乎没有障碍结论*迷宫变形NJOI 在宽搜过程中，队列以几何数量级扩展，扩展层数越大

16、，对存储的威胁越大 如何对存储进行压缩？双向搜索结论NJOI现要找出一条从现要找出一条从A A到到B B经过城市最少的一条路线。经过城市最少的一条路线。广度优先遍历广度优先遍历: A 应用NJOIF,r,队列初始化；While f=r do 取队首； 宽搜基本框架NJOIsq1.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 do I:=x+zv.x ; j:= y+zv.y ; if mgI

17、,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 ; NJOI 设有数字设有数字2，3，5，7，13，运算符号：，运算符号：+,*, 且运算无优先级之分，如且运算无优先级之分，如2+3*5=25，3*5+2=17，编写一个程序，给出任意一个，编写一个程序，给出任意一个整数整数n，要求用以上的数和运算符，以最少，要求用以上的数和运算符，以最少的运算次数产生出的运算次数产生出

18、n。 例如：例如：n=7,7=7,（0次运算）次运算）n=93，93=13*7+2 （2次运算次运算 ）。）。 例 数值计算NJOI（1）数据的结构：参加运算的数据、参加运算）数据的结构：参加运算的数据、参加运算的符号的符号可以用常量数组可以用常量数组 data12，data23，参与运算数据、，参与运算数据、符号顺序符号顺序 （2）每步参加运算的数据及运算符号）每步参加运算的数据及运算符号 x, y , t：被加数、加数，结果（：被加数、加数，结果（x ），），t ：从：从哪一步计算到此。哪一步计算到此。 分析算法模式NJOI给出一个整数给出一个整数n(n1030)和和k个变换规则（个变换规则（k=R and 反面个数反面个数=5-R num=R and (10-num)=5-R num=R and num-R=5 0=num-R=5 R=05翻币问题NJOI 问题求解模式：状态问题求解模式：状态A-状态状态B且且AB同同质质 正向队列正向队列Q1（队列首为起始状态（队列首为起始状态A） 反向队列反向队列Q2（队列首为目标状态（队列首为目标状态B）双向搜索while (f1=r1) and (f2=r2) do data1=q1f1 for i=1 to 方案总数方案总数 计算得新状态计算得新状态temp1 if 为新状态为新状态 (在在q1内比对判重内比对判重) 入队入队