搜索及其优化(提高组-吴建锋)

1、搜索（回溯）及其优化1一个简单的问题一个城市的公交车数量总是和总人口有着一定的联系，每辆公交车上肯定有一位售票员。对于某个城市，我们知道售票员人数最多不超过总人口的q%，最少不少于总人口的p%。现在让我们来求满足上述条件的该城市可能最少的总人口数。2问题分析1、在没法用数学方法的前提下，一般只能用穷举去解决。2、穷举首先要解决的是枚举的边界3、假定总人口为k，则k至少为1。4、枚举结束条件是什么呢？5、这也是搜索的核心约束条件（1）k*p%至少为1（2）k*q%必定大于k*p%（而且二者取整后不能相同3算法分析1、k依次从1开始枚举，每次增加12、每增加1，判断前面的约束条件是否满足3、可用递

2、归式穷举解决（一般搜索的结构），也可用循环解决。4主程序 readln(P,q); num:=0; repeat inc(num); until ok; writeln(num);5约束条件的判断function ok : boolean; var k2 : longint; begin k2 := trunc(num*q/100); if (num*p/1001)1e-4) then exit(true); exit(false); end;6比较典型的搜索有n个数（n17），让你分成两堆。使两堆和的差最小。 7问题分析1、诈看可能让人觉得感觉不舒服，因为枚举的对象是两个。2、实际枚举对象也

3、只有一个，因为？3、假定两堆的和分别是x和y，要求abs(x-y)最小，只要枚举x的和，然后判断abs(sum-2x)最小即可。（sum表示所有数的和）8算法分析1、如何枚举第一堆的和x？2、搜索的每一步是确定第一堆包含的一个数，所以递归程序中就是在所有数中任取一个，然后累加入x3、累加之后做什么？4、什么时候递归结束返回？以上两点是每个搜索算法都必须解决的问题。9算法描述1、先把第一个数加入x2、然后判断最优解3、再把下一个数加入x4、重复2和3步，直到？直到最后一个数已经尝试加入x之后就可以递归返回了。10数据结构和初始化1、用wi保存输入的每个数2、用sum保存所有数的和11主程序ini

4、t;dfs(w1,1);writeln(min);12递归子程序procedure dfs(total,v:longint); var i:integer; begin if abs(sum-2*total)min then min:=abs(sum-2*total); if v=n then exit; for i:=v+1 to n do dfs(total+wi,i); end;13显示图的搜索网络布线。输入n个点的坐标，计算最短的布线方案。分析：这里的阶段就是当前连接的点，状态就是已连接部分的线路长度和结点是否连接，方案就是下一阶段要连接的点。设计程序时，表示阶段号的变量I应该是加1递

5、增的，方案就是在递归子程序中用循环枚举的，而状态改变就是在方案确定后增加的线路长度。14搜索的原理Try(I:integer);第一次调用try(i)，for I循环Var j:integer;Begin if 所有点都连接过 then begin 比较最优；保存最优；end else begin for j:=1 to n do if I到j可连 then begin 记录痕迹；s:=s+aI,j；try(j); s:=s-aI,j; end;End;15简单的优化上述程序中一个可明显的优化措施是剪枝优化。即在中间连接了某个点后，把当前花费和前面最优花费比较，如果当前花费大于前面最优花费，则

6、取消继续深入。随着竞赛的发展，搜索的难度和复杂度也在增加，上述二个程序只是一维线性的搜索，问题模型容易建立，搜索优化也比较直观，但随着多维组合式搜索的出现，这些显性的特征就变得隐性，给我们的算法设计带来了困难。16多维组合式穷举邮票问题2。邮局发行一套有n种不同面值的邮票，如果限制每封信所贴的邮票张数不能超过m枚。存在整数R，使得用不超过m枚的邮票可以贴出一下连续序列：1，2，3，4，5，.,R。编程求出可以得到尽可能大的R值以及对应的n种邮票面值。 17算法描述本题的难点是需要通过二次搜索来解题，第一次搜索是穷举确定n枚邮票的面值，第二次搜索是根据前面确定的面值，穷举每种面值邮票贴的数量，最

7、后根据这二个穷举结果计算可以得到的最大的r值。 18主程序s1:=1;rmax:=0;f:=0;writeln;write(n,m=);readln(n,m);try(1); 首次调用过程，开始穷举邮票面值for o:=1 to n do write(go:4); 输出每种邮票的面值writeln;writeln(rmax=,rmax);19第一次搜索procedure try(i:integer);varj,temp,l:integer;beginfor j:=si-1+1 to m*si-1+1 do 穷举当前阶段可行的方案beginsi:=j; 保存状态改变if i=n then beg

8、in 所有面值都已经产生，递归结束f:=0;stamp:=;work_out_r(1,m);temp:=1; 二次分阶段决策结束，开始计算最大r值while temp in stamp do temp:=temp+1;if rmaxtemp-1 thenfor l:=1 to n do begin gl:=sl;rmax:=temp-1;end;endelse try(i+1); 还有没有确定面值的邮票，继续搜索面值end;end;20第二次搜索procedure work_out_r(i1,ej:integer);在面值确定前提下，搜索各种不同张贴方案vark:integer;beginfo

9、r k:=0 to ej do 当前邮票最少不贴，最多贴ej张beginf:=f+k*si1; 状态保存if i1=n then stamp:=stamp+f else work_out_r(i1+1,ej-k);f:=f-k*si1; 回溯时的状态恢复end;end;21又一个多维组合式穷举编写如下“一维优化线切割问题”的计算机程序。某下料车间要切割XX型号汽车的板簧60套，每套板簧分别为150cm、120cm、100cm、80cm、60cm、40cm、25cm的7根板条构成，可用的原材料钢板长度都为500cm.若不计切屑损失，请求出优化的原材料下料切割计划（每根料的剩余废料最少，或剩余料长

10、=Lj时，才有可能有解！2、当有多个wi满足条件时，取哪一个？Wi越小越好！因为若有wi1wi2，但实际采用wi2，则wi1对应的那种板簧肯定多取，必定不是最优解。所以我们取wi=minLj/PI,j24搜索的应用及优化3、和理论最优解的比较。如果当前找到的解等于理论上的最优解（比如，在这里是（15012010080604025）60/50069），那么不必再搜索了。25搜索的应用及优化【程序实现】1、穷举在一根原料上切割各种板簧的所有方案并保存。递归程序的二个关键：（1）什么时候结束搜索？（2）在每个递归中穷举什么？ if then for I:=? To ? Do if 试探可以 then

11、 begin 记录痕迹；try();现场恢复；end;26搜索的应用及优化（1）只有当所有规格板簧不能再切割时（剩余长度now小于等于20），才考虑切割下一种切割方案，若用AI表示当前切割方案中第I种板簧被产生的数量，则结构如下：If now=min then 保存方案并返回；For I:=d to n do if 当前板簧可切割（longI=now）then begin inc(aI) ;try(I,now-longI);dec(aI); end;过程名为try(d,now:integer),第一次调用是为try(1,L)。其中L为每根原料的长度。27搜索的应用及优化procedure Tr

12、y(D, Now : Integer);枚举产生所有可能的组合方式var I : Integer;begin if Now = Min then begin PL := PL + 1; PPL := A; PPL, 0 := Now; Exit; end; for I := D to N do if LongI = Tot) or (Waste MinWaste) or (D N + 1) then Exit; if D 1 then begin Finish := True; Z := D - 1; for I := 1 to N do if LeaveI 0 then begin Leav

13、eI := LeaveI - PBZ.C, I * BZ.W; if LeaveI 0 then Finish := False; end; if Finish then begin Tot := NowTot; Best := B; BestL := Z; MinWaste := Waste; if Tot = MinTot then Out else Exit; end; end; 30搜索的应用及优化for I := 1 to PL do begin BD.C := I; BD.W := MaxInt; for J := 1 to N do if (LeaveJ 0) and (PI,

14、J 0) then begin Z := LeaveJ div PI, J; if Z BD.W then BD.W := Z;在所有可行值中选取最小的 end; 每个阶段都进行这样的调整 if BD.W =tot）or (wasteminwaste) or (dn+1)（2）用BD.C表示当前规格板簧所属的方案号，BD.W表示当前规格板簧所属组合方案还所需的采用数量，用PI,0表示第I种组合切割方案所产生的余料，而穷举的对象是所有切割方案和7种规格板簧的组合，所以穷举部分的程序结构如下：32搜索的应用及优化For I:=1 to pl do beginsearch(d+1,nowtot+bd

15、.w,waste+pI,0*bd.w,leave)End;为了产生每根板簧对应的尽可能小的wi，并把这种剪枝的影响带入到下个阶段，我们还须在上面程序段中添加求最小wi的语句，完善后的程序段如下：33搜索的应用及优化for I := 1 to PL do begin BD.C := I; BD.W := MaxInt; for J := 1 to N do if (LeaveJ 0) and (PI, J 0) then begin Z := LeaveJ div PI, J; if Z BD.W then BD.W := Z;在所有可行值中选取最小的 end; 每个阶段都进行这样的调整 if

16、BD.W 0的，则要终止向下搜索的处理，当然中间若发现等于理论最优解，则输出结果并结束程序。具体的程序段如下：35搜索的应用及优化 if (NowTot = Tot) or (Waste MinWaste) or (D N + 1) then Exit; if D 1 then begin Finish := True; Z := D - 1; for I := 1 to N do if LeaveI 0 then begin LeaveI := LeaveI - PBZ.C, I * BZ.W; if LeaveI 0 then Finish := False; end; if Finish

17、 then begin Tot := NowTot; Best := B; BestL := Z; MinWaste := Waste; if Tot = MinTot then Out else Exit; end; end;36搜索的应用及优化优化的小结：1、中间解差于全局可能最优解的要剪枝2、先计算理论最优解，当可能最优解等于该值时，结束程序3、不可能有最终解的要剪枝。37搜索的应用及优化数字排队。一个2n位的正整数(n10)，具有如下性质：（1）含有两个数字“1”，两个数字“2”，两个数字“n”；（2）两个“1”之间有1个数字，两个“2”之间有2个数字， ，两个“n”之间有n个数字。要

18、求：（1）n由键盘输入；（2）输出所有符合上述性质的正整数及总个数。 38搜索的应用及优化算法分析：没有其他可以参考的算法，而且数据规模较小，所以可以采用搜索解决。算法处理步骤如下：1、主程序第一次调用时为try(1)；2、递归过程：proc try(i:byte); if i=n then 找到一组数，输出方案，计数器加1并exit; for j=1 to 2*n do if 将第一个i放在j位，将第二个i放在j+i+ 1 位可行 then 放好两个i；try(i+1);现场恢复 39搜索的应用及优化有优化的方法吗？40搜索的应用及优化【剪枝优化】由于我们穷举的是任何一个I的第一个位置，假设

19、这个位置号是j，而I的第二个位置是可以计算的，那就是j+I+1。但这个位置是不能超过2*n的，即j+I+1=2*n，移项之后就有j B1$A2$ - B2$规则的含义为：在 A中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ 。例如：A$abcdB$xyz变换规则为：abc-xuud-yy-yz则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：abcd-xud-xy-xyz共进行了三次变换，使得 A$ 变换为B$。42搜索的应用及优化输入:键盘输人文件名。文件格式如下：A$ B$A1$ B1$ A2$ B2$ |- 变换规则 . . /所有字符串长度的上限为 20。

20、输出:输出至屏幕。格式如下：若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出NO ANSWER!43搜索的应用及优化分析：该题是2002提高组复赛题，看起来是一个相对简单的试题，但我们通过对其的分析可以发现很多编程及优化的思想。这是一个隐式图的搜索问题，中间又涉及简单的字符串处理，我们先来建立图形。如果把每次变换得到的字符串作为一个结点，那么点之间的边就是变换关系，要求的是最少步骤（最少费用），所以一般我们总能马上想到宽度优先搜索法（因为费用和边数成正比），但为了研究回溯法的优化，我们这里来用dfs解决。递归结构的回溯法的关键是递归过程的设计，而递归

21、的关键又是设计好以下二个关键：是什么？。44搜索的应用及优化1、递归结束条件及此阶段的处理2、当前阶段的试探方案穷举。1、当经过若干次变换后字符串等于B$时，递归就该结束（不必再沿着此路搜索下去）。因为是求最优解，所以此时程序不应结束，而把当前解保存下来，以和其他途径的解进行最优性比较，然后返回上一个阶段。2、试探方案穷举。不要被样例数据迷惑，实际上每格中间阶段的字符串都可能有多种变换法则适合它，所以这里既要穷举所有的变换方案，又要穷举出当前字符串中和当前穷举出的方案匹配的子串（长度等于变换法则中的源串的长度），因此这里穷举结果就是二个穷举分量的所有组合。45搜索的应用及优化如果当前字符串是s

22、（由此可以想到递归过程必须有一个参数来传递当前字符串），并且这个串的长度是L，那么这部分穷举以及方案产生后继续搜索的程序段如下：For I:=1 to n do for j:=1 to L do if 方案可行 then search(.s,.);下面来细化和优化。条件是什么？应该是从j开始的分割出的子串在原始转换列表左边出现的，而且是第I种变换可以变换的。假设原始列表中保存在s1I中，那么条件就是：copy(s,j,length(s1I)=s1I，为了减少重复处理，可以在初始化时计算并让lenI:=length(s1I)。46搜索的应用及优化在search(s,)调用中，我们已经确定了一个参

23、数，还须另外参数吗？我们要记录当前试探的解，这里就是步数，也就是调用过程的次数，假设用depth表示，那么细化后就是：For I:=1 to n do for j:=1 to L do if copy(s,j,length(s1I)=s1I then search(depth+1,j之前子串转换后子串（j+lenI）后面的子串)作为优化的，内循环终值的L可以变为：L-lenI+147搜索的应用及优化如果用b表示目标，则递归结束条件是If s=b then answer:=depth;exit问：answer是全局还是局部变量？作为优化，可以在前面进行判断：If depth=answer the

24、n exit;这应该属于最优性剪枝的范畴。过程定义为：Procedure search(depth;integer,s:string);Var I,j,L:integer;第一次调用为：search(0,a);输入、初始化部分是。？48搜索的应用及优化Reads(a,b);i:=0;While (not seekeof） do begin inc(i);reads(s1i,s2i);leni:=length(s1i);End;Answer:=11;Search(0,a);If answer=11 then writeln(No answer!) else writeln(answer);49搜

25、索的应用及优化字符串处理过程：Procedure reads(var s1,s2:string);Var s:string;Begin readln(s); s1:=copy(s,1,pos( ,s)-1); s2:=copy(s,pos( ,s)+1,length(s)-pos( ,s);End;50搜索的应用及优化1、每种变换方案只能使用一次怎么办？2、求所有方案怎么办？51搜索的应用及优化在此基础上是否还有其他的优化措施？52搜索的应用及优化【剪枝优化】（重复性判断）由于搜索过程中试探方案采用顺序的不同，可能会导致不同排列方案（组合相同）产生相同的结点，这样就导致后续搜索的重复性。比如，

26、变换法则是：abc-u,d-e, abcd 1 2 ud abce 3 4 ue ue53搜索的应用及优化如果变换3和4的源串是有部分重叠的，那么这种重复就不会产生。按照这种想法，我们可以设计避免重复的措施，先来看不会重复的情形：54搜索的应用及优化当出现以下情形时，重复就会产生：所以，我们可以设计出避免重复的措施是：要求下一个变换的结束位置不早于上一个变换的开始位置（类似于给变换有个顺序，排序）。在程序实现时，就需要在方案穷举部分限制当前子串的开始位置（而不是原来的1），那么这个开始位置该如何表示？假设上次变换的开始位置是last。（由此在过程中要增加一个参数last）55搜索的应用及优化F

27、or I:=1 to n do for j:=(last-lenI+1) to (L-lenI+1) do 这样的设计正确吗？56搜索的应用及优化如果上次变换开始位置是1呢？循环初值不是变成负数了？所以需要进行判别。应该变为：For I:=1 to n do for j:=max(1,last-lenI+1) to L-LENI+1 DO【优化措施1】重复性剪枝（其他有可行性剪枝，最优性剪枝）下面考虑其他方式的组合优化57搜索的应用及优化【分枝定界法】概念：用问题解的上界或下界来限定方案穷举范围，以缩小搜索范围，剪去无用结点的方法。关于分枝定界法实现的方法有很多，核心就是在搜索前确定一个比实际

28、范围小的上界或下界，然后在此范围内搜索，下面介绍的方法是通过穷举可能的最优解，然后在这个范围内搜索。58搜索的应用及优化先假定一次都不变换，是否等于目标第二次假定变换一次，是否等于目标第三次假定变换2次，是否等于目标如果前面不可以，假定变换10次，行不行？如果还不行，则问题无解。上面的假定变换次数实际就是搜索的深度，因为当depth次变换还不等于目标时，须从头开始进行depth+1次的变换试探，所以过程中必须传递这个搜索深度参数，根据前面重复性剪枝的需要，当前阶段必须知道上次变换的开始位置，所以这个位置参数也必须传递，可以得到主程序调用语句为：59搜索的应用及优化For answer:=0 t

29、o 10 do search(answer,a,1);过程为：Procedure search(depth:integer,s:string,last:integer);Begin if depth=0 then begin if s=b then writeln(answer);halt; exit; end; L:=length(s);dec(depth); for I:=1 to n do for j:=max() to do if (copy(s,j,lenI)=s1I) then search(depth,?,?);60搜索的应用及优化你对这个程序的感觉是？61搜索的应用及优化实际上

30、就在进行宽度优先搜索，从哪里可以分析出这个结论？62搜索的应用及优化1、search是被for answer:=0 to 10 do调用的2、在search过程中，每当深入一个层次，depth都会减1，直到为0，此时，如果达到目标，则程序结束，否则返回上层调用处。从以上两点看出，引入分枝定界法后，实际的算法原理是宽度优先搜索。从这个程序我们也得到了一般宽度优先搜索可用剪枝优化。当然另外一个优化就是双向宽度优先搜索。63搜索的应用及优化【例8】矩形覆盖（存盘名PG4.exe）在平面上有 n 个点（n = 50），每个点用一对整数坐标表示。例如：当 n4 时，4个点的坐标分另为：p1（1，1），p2（2，2），p3（3，6），P4（0，7），见图一。 64搜索的应用及优化这些点可以用 k 个矩形（1=k=4）全部覆盖，矩形的边平行于坐标轴。当 k=2 时，可用如图二的两个矩形 sl，s2 覆盖，s1，s2 面积和为 4。问题是当 n 个点坐标和 k 给出后