个人网站建设思路,如何优化基础建站,网络营销推广的研究方向,小制作手工废物利用目录 搜索剪枝常见方法与技巧
关键字 搜索方法,剪枝
摘要
正文 小结
程序
参考书目 搜索剪枝常见方法与技巧
关键字 搜索方法,剪枝
摘要
搜索是计算机解题中常用的方法#xff0c;它实质上是枚举法的应用。由于它相当于枚举法#xff0c;所以其效率是相当地的。因此…目录 搜索剪枝常见方法与技巧
关键字 搜索方法,剪枝
摘要
正文 小结
程序
参考书目 搜索剪枝常见方法与技巧
关键字 搜索方法,剪枝
摘要
搜索是计算机解题中常用的方法它实质上是枚举法的应用。由于它相当于枚举法所以其效率是相当地的。因此为了提高搜索的效率人们想出了很多剪枝的方法如分枝定界启发式搜索等等。在竞赛中我们不仅要熟练掌握这些方法而且要因地制宜地运用一些技巧以提高搜索的效率。
正文
搜索的效率是很低的即使剪枝再好也无法弥补其在时间复杂度上的缺陷。因此在解题中除非其他任何方法都行不通才可采用搜索。
既然采用了搜索剪枝就显得十分的必要即使就简简单单的设一个槛值或多加一两条判断就可对搜索的效率产生惊人的影响。例如后问题假如放完皇后再判断则仅仅只算到就开始有停顿到了就已经超过了秒而如果边放边判断就算到了也没有停顿的感觉。所以用搜索就一定要剪枝。
剪枝至少有两方面一是从方法上剪枝如采用分枝定界启发式搜索等适用范围比较广二是使用一些小技巧这类方法适用性虽不如第一类有时甚至只能适用一道题但也十分有效并且几乎每道题都存在一些这样那样的剪枝技巧只是每题有所不同而已。 问题一(最短编号序列)
表A和表B各含k(k20)个元素元素编号从1到k。两个表中的每个元素都是由0和1组成的字符串。不是空格字符串的长度20。例如下表的A和B两个表每个表都含3个元素k3。 元素编号 字符串 1 1 2 10111 3 10
表A 表B 元素编号 字符串 1 111 2 10 3 0 对于表A和表B存在一个元素编号的序列2113分别用表A中的字符串和表B 中的字符串去置换相应的元素编号可得相同的字符串序列101111110见下表。 元素编号序列 2 1 1 3 用表A的字符串替换 10111 1 1 10 用表B的字符串替换 10 111 111 0
对表A和表B具有上述性质的元素编号序列称之为S(AB)。对于上例S(AB)2113。
编写程序从文件中读入表A和表B的各个元素寻找一个长度最短的具有上述性质的元素编号序列S(AB)。若找不到长度100的编号序列则输出“No Answer”。 对于这道题因为表和表不确定所以不可能找到一种数学的方法。因为所求的是最优解而深度优先搜索很容易进入一条死胡同而浪费时间所以必须采用广度优先搜索的方法。但是广度优先搜索也有其缺陷。当表和表中的元素过多是扩展的结点也是相当多的搜索所耗费的时间也无法达到测试的要求。为了解决这个问题就必须对搜索的算法加以改进。分枝限界似乎不行因为无法确定代价。而且由于目标不确定也无法设定估价函数。但是因为此题的规则既可以正向使用又可以逆向使用于是便可以采用双向搜索。
在大方法确定后算法的框架就已经基本形成但即使如此算法也还有可改进的地方。
存储当前的串和串是很费空间的但因为串和串的大部分相同故只需记录不同部分并作个标记。再换成动态存储。为了保证两个方向扩展结点的速度相对平衡可以采取每次扩展结点数较少的方向而不是两方向轮流扩展。
如此一来搜索的效率就比单纯的广度优先搜索有了明显的提高。
附程序sab.pas 有时搜索也会有不同的搜索方法如多处理机调度问题也会产生不同的效率。 问题二任务安排
个城市若干城市间有道路相连一辆汽车在城市间运送货物总是从城市出发又回到城市。该车每次需完成若干个任务每个任务都是要求该车将货物从一个城市运送至另一个。例如若要完成任务6则该车一次旅程中必含有一条子路径。先到再到。
如下图所示如果要求的任务是则一条完成全部任务的路径是。 4 2 6 5 3 7 编程由文件读入道路分布的领接矩阵然后对要求完成的若干任务寻找一条旅行路线使得在完成任务最多的前提下经过的城市总次数最少。如上例中经过城市总次数为城市和各经过次均以次计起点不计60。 这道题因为很难找到数学规律便只有采用搜索的方法。
首先第一感觉便是从城市i出发便搜索所有相邻的城市再根据当前所处的城市确定任务的完成情况从中找到最优解。这种搜索的效率是极低的其最大原因就在于目标不明确。
根据题意我们只需到达需上货和下货的城市其它的城市仅作为中间过程而不应作为目标。因此首先必须确定可能和不可能完成的任务然后求出任意两城市间的最短路径。在搜索时就只需考虑有货要上的城市或者是要运到该城市的货全在车上其它不须考虑。同时还可以设定两个简单的槛值。如果当前费用还需达的城市当前最优解或当前费用返回城市1的费用当前最优解则不需继续往下搜索。
这种方法与第一感的方法有天壤之别。附程序travell.pas 问题三多处理机调度问题
设定有若干台相同的处理机P1,P2 Pn,和m个独立的作业J1,J2 jm,处理机以互不相关的方式处理作业现约定任何作业可以在任何一台处理机上运行但未完工之前不允许中断作业作业也不能拆分成更小的作业已知作业Ji需要处理机处理的时间为Tii1,2 m。编程完成以下两个任务
任务一假设有n台处理机和m个作业及其每一个作业所需处理的时间Ti存放在文件中求解一个最佳调度方案使得完成这m个作业的总工时最少并输出最少工时。
任务二假设给定作业时间表和限定完工时间于文件中求解在限定时间内完成这批作业所需要最少处理机台数和调度方案。 此题有两种搜索方法
方法一按顺序搜索每个作业。当搜索一个作业时将其放在每台处理机搜索一次。
方法二按顺序搜索每台处理机。当搜索一台处理机时将每个作业放在上面搜索一次。
对比上述两种方法可以发现方法二较方法一更容易剪枝。
下面是两中方法剪枝的对照
对于方法一只能根据目前已确定的需时最长的处理机的耗时与目前最佳解比较。
对于方法二可约定Time[1]Time[2]Time[3] Time[n]Time[i]表示第i台处理机的处理时间,从而可以设定槛值如当前处理机的处理时间目前最佳解或剩下的处理机台数×上一台处理机的处理时间剩余的作业需要的处理时间则回溯。因为在前面的约束条件下已经不可能有解。 因此从上面的比较来看第二种方法显然是比第一种要好的。下面就针对第二种方法更深一层的进行探讨。 对于任务一首先可以用贪心求出Time[1]的上界。然后还可以Time[1]的下界UP作业总时间/处理机台数。UP表示大于等于该小数的最小整数。搜索便从上界开始找到一个解后若等于下界即可停止搜索。
附程序jobs_1.pas) 对于任务二可采用深度可变下界。下界为UP作业总时间/限定时间即至少需要的处理机台数。并设定Time[1]的上界为T。
附程序jobs_2.pas 小结
搜索的使用相当广泛几乎每题都可以采用搜索的方法。虽然如此搜索也切不可滥用。只有当问题无规律可寻时才可用搜索。一旦确定了使用搜索就一定要想办法对其进行剪枝。无论是采用剪枝的常见方法还是用一些搜索的小技巧虽都无法降低搜索的时间复杂度却总还是大有裨益的。 程序
1. 最短编号序列sab.pas
program sab;
type aastring[100]; ltyperecord f:integer; {父指针} k,d,la,lb:shortint; {k--剩余串标志d--序列中元素的编号la,lb--AB两串的串长} st:^aa; {剩余串} end;
const maxn1300;
var t,h:array[0..1] of integer; {h--队首指针t--队尾指针0表示正向1表示逆向} p:array[0..1,1..maxn] of ltype; {p[0]--正向搜索表p[1]--逆向搜索表} strs:array[1..2,1..20] of string[20]; {strs[1]--表A元素strs[2]--表B元素} n:integer; {表A和表B的元素个数} procedure readp; {读入数据}
var f:text; st:string; i,j:integer;
begin write(File name:); readln(st); assign(f,st); reset(f); readln(f,n); for i:1 to n do readln(f,strs[1,i]); for i:1 to n do readln(f,strs[2,i]); close(f);
end; procedure print(q,k:integer); {从k出发输出沿q方向搜索的元素编号}
begin if k1 then begin if q1 then writeln(p[q,k].d); print(q,p[q,k].f); if q0 then writeln(p[q,k].d); end;
end; procedure check(q:shortint); {判断两方向是否重合q表示刚产生结点的方向的相反方向}
var i:integer;
begin for i:1 to t[1-q]-1 do if (p[q,t[q]].kp[1-q,i].k) and (p[q,t[q]].st^p[1-q,i].st^) and (p[q,t[q]].lap[1-q,i].la100) and (p[q,t[q]].lbp[1-q,i].lb100) then begin if q0 then begin print(0,t[q]); print(1,i); end else begin print(0,i); print(1,t[q]); end; halt; end;
end; procedure find(q:shortint); {沿q方向扩展一层结点}
var i:integer; sa,sb:aa;
begin for i:1 to n do if (p[q,h[q]].lalength(strs[1,i])100) and (p[q,h[q]].lblength(strs[2,i])100) then begin sa:;sb:; if p[q,h[q]].k1 then sa:p[q,h[q]].st^ else sb:p[q,h[q]].st^; if q0 then {沿不同方向将编号为i的元素加到序列中} begin sa:sastrs[1,i]; sb:sbstrs[2,i]; while (sa) and (sb) and (sa[1]sb[1]) do begin delete(sa,1,1); delete(sb,1,1); end end else begin sa:strs[1,i]sa;sb:strs[2,i]sb; while (sa) and (sb) and (sa[length(sa)]sb[length(sb)]) do begin delete(sa,length(sa),1); delete(sb,length(sb),1); end; end; if (sa) or (sb) then {生成一个新的结点} with p[q,t[q]] do begin f:h[q];d:i; la:p[q,h[q]].lalength(strs[1,i]); lb:p[q,h[q]].lblength(strs[2,i]); new(st); if sa then begin k:2;st^:sb end else begin k:1;st^:sa; end; check(q); inc(t[q]); end; end; inc(h[q]);
end; begin readp; h[0]:1;h[1]:1; t[0]:2;t[1]:2; new(p[0,1].st);p[0,1].st^:; new(p[1,1].st);p[1,1].st^:; {队列初始化} while (h[0]t[0]) and (h[1]t[1]) and (t[0]maxn) and (t[1]maxn) do if t[0]t[1] {比较两方向的节点数向结点数少的方向扩展} then find(0) else find(1); writeln(No answer!);
end. 任务安排:travell.pas
program travell;
var path, {path[i,j]--以i为起点第j个运输终点} next, {next[i,j]--从i到j的最短路径中,i顶点的下一个顶点} dist, {dist[i,j]--从i到j的最短路径长度} road:array[1..60,1..60] of integer; {道路的邻接矩阵} head, {head[i]--以i为起点的任务数}
tail, {tail[i]--0表示以i为终点无任务或已完成} {1表示以i为终点的任务的所有顶点都在完成任务路径中} {k1表示以i为终点的所有任务,还有k个顶点未到达} arrive:array[1..60] of integer; {arrive[i]--顶点i的经过次数} d, {完成任务路径} bestd:array[1..100] of integer; {当前最佳完成任务路径} left, {必经结点个数} cost, {当前代价} mincost, {最佳完成任务代价} s, {经过顶点数} bests, {最佳完成任务所经过的顶点数} m, {任务数} n:integer; {城市数} procedure findshortest; {求任意两点间的最短路径}
var i,j,k:integer;
begin for i:1 to n do for j:1 to n do if road[i,j]1 then begin dist[i,j]:1; next[i,j]:j end else dist[i,j]:100; for k:1 to n do for i:1 to n do for j:1 to n do if dist[i,k]dist[k,j]dist[i,j] then begin dist[i,j]:dist[i,k]dist[k,j]; next[i,j]:next[i,k]; end;
end; procedure init; {读入数据并初始化数据}
var i,j,k:integer; st:string; f:text;
begin write(File name:); readln(st); assign(f,st); reset(f); readln(f,n); for i:1 to n do for j:1 to n do read(f,road[i,j]); findshortest; readln(f,m); for i:1 to m do begin read(f,j,k); if (dist[1,j]100) and (dist[1,k]100) then begin inc(head[j]); inc(tail[k]); path[j,head[j]]:k; end; end; close(f); for i:1 to m do if tail[i]0 then inc(tail[i]); for i:1 to head[1] do dec(tail[path[1,i]]); head[1]:0;inc(s);d[s]:1;left:0; cost:0;mincost:maxint; for i:2 to n do if (head[i]0) or (tail[i]0) then inc(left);
end; procedure try; {搜索过程}
var i,j,k:integer; p:boolean;
begin if (costleftmincost) or (costdist[1,d[s]]mincost) then exit; if left0 then {是否完成了所有任务} begin mincost:costdist[1,d[s]]; bestd:d; bests:s; inc(bests);bestd[bests]:1; exit; end; for i:2 to n do if (head[i]0) or (tail[i]1) then {如果去i顶点有必要} begin inc(cost,dist[d[s],i]); inc(arrive[i]); inc(s); d[s]:i; if arrive[i]1 then
{如果i顶点第一次到达则所有以i为起点的任务的终点tail值减1} for j:1 to head[i] do dec(tail[path[i,j]]); k:head[i]; head[i]:0; if tail[i]1 then {如果完成了以i为终点的所有任务该点则不需再经过} begin p:true; dec(tail[i]); end else p:false; if tail[i]0 then dec(left); try; {恢复递归前的数据} if tail[i]0 then inc(left); if true then inc(tail[i]); head[i]:k; if arrive[i]1 then for j:1 to head[i] do inc(tail[path[i,j]]); dec(s); dec(arrive[i]); dec(cost,dist[d[s],i]); end;
end; procedure show(i,j:integer); {输出从i到j的最短路径}
begin while ij do begin write(--,next[i,j]);i:next[i,j]; end;
end; procedure print; {输出最佳任务安排方案}
var i:integer;
begin write(1); for i:1 to bests-1 do show(bestd[i],bestd[i1]); writeln; writeln(Min cost,mincost);
end; begin init; try; print;
end. 多处理机调度问题
任务一jobs_1.pas
program jobs_1;
const maxn100; {处理机的最多数目} maxm100; {作业的最多数目}
var t:array[1..maxm] of timeint; {t[i]--处理作业i需要的时间} time, {time[i]--第i台处理机的处理时间} l, {l[i]--第i台处理机处理作业的数目} l1:array[0..maxn] of timeint; {l1[i]--目前最优解中第i台处理机处理作业的数目} a, {a[i,j]--第i台处理机处理的第j个作业耗费的时间} a1:array[1..maxn,1..maxm] of integer; {a1[i,j]--目前最优解中第i台处理机处理的第j个作业耗费的时间} done:array[1..maxm] of boolean; {done[i]--true表示作业i已完成false表示未完成} least, {处理时间的下界} i,j,k,n,m, min, {目前最优解的处理时间} rest:integer; {剩余作业的总时间} procedure print; {输出最优解}
var i,j:integer;
begin for i:1 to n do begin write(i,:); for j:1 to l1[i] do write(a1[i,j]:4); writeln; end; writeln(T0,time[0]1);
end; procedure readp; {读入数据}
var f:text; st:string; i,j,k:integer;
begin write(File name:);readln(st); assign(f,st);reset(f); readln(f,n,m); for i:1 to m do begin read(f,t[i]);inc(rest,t[i]); end; close(f); least:(rest-1) div n1; {定下界} for i:1 to m-1 do {排序} for j:i1 to m do if t[j]t[i] then begin k:t[i];t[i]:t[j];t[j]:k end;
end; procedure try(p,q:integer); {从p--m中选取作业放到处理机q上}
var j:integer; z:boolean;
begin z:true; for j:p to m do if not done[j] and (time[q]t[j]time[q-1]) then {选择合适的作业} begin z:false;done[j]:true; inc(l[q]);a[q,l[q]]:t[j];inc(time[q],t[j]);dec(rest,t[j]); try(j1,q); dec(l[q]);dec(time[q],t[j]);inc(rest,t[j]);done[j]:false; if time[1]time[0] then exit; {找到解后退回处理机1需更新time[1],使之减小到time[0]} {2--n台处理机就不需再搜索} end; if z and ((n-q)*time[q]rest) then {如果处理机q已无法放任何作业} if rest0 then {找到一组解} begin a1:a;l1:l; time[0]:time[1]-1; if time[1]least then begin print;halt end; end else if qn then {继续搜索} try(1,q1);
end; begin readp; fillchar(time,sizeof(time),0); fillchar(a,sizeof(a),0); fillchar(l1,sizeof(l1),0); fillchar(l,sizeof(l),0); for i:1 to m do {贪心求上界} begin k:1; for j:2 to n do if time[j]time[k] then k:j; time[k]:time[k]t[i]; l1[k]:l1[k]1; a1[k,l1[k]]:t[i]; end; min:time[1];time[0]:min-1; for i:2 to n do if time[i]min then min:time[i]; if minleast then {如上下界相等} begin print; halt; end; fillchar(time,sizeof(time),0); time[0]:min-1; {将上界减1以找到更优的解} try(1,1); print;
end. 任务二jobs_2.pas
program jobs_2;
const maxn100; {处理机的最多数目} maxm100; {作业的最多数目}
var t:array[1..maxm] of timeint; {t[i]--处理作业i需要的时间} time, {time[i]--第i台处理机的处理时间} l, {l[i]--第i台处理机处理作业的数目} l1:array[0..maxn] of timeint; {l1[i]--目前最优解中第i台处理机处理作业的数目} a, {a[i,j]--第i台处理机处理的第j个作业耗费的时间} a1:array[1..maxn,1..maxm] of integer; {a1[i,j]--目前最优解中第i台处理机处理的第j个作业耗费的时间} done:array[1..maxm] of boolean; {done[i]--true表示作业i已完成false表示未完成} least, {处理时间的下界} i,j,k,tmax,m, min, {目前最优解的处理时间} rest:integer; {剩余作业的总时间} procedure print; {输出最优解}
var i,j:integer;
begin for i:1 to least do begin write(i,:); for j:1 to l1[i] do write(a1[i,j]:4); writeln; end; writeln(Min,least);
end; procedure readp; {读入数据}
var f:text; st:string; i,j,k:integer;
begin write(File name:);readln(st); assign(f,st);reset(f); readln(f,tmax,m); for i:1 to m do begin read(f,t[i]);inc(rest,t[i]); end; close(f); least:(rest-1) div tmax1; {确定下界} for i:1 to m-1 do {排序} for j:i1 to m do if t[j]t[i] then begin k:t[i];t[i]:t[j];t[j]:k end;
end; procedure try(p,q:integer); {从p--m中选取作业放到处理机q上}
var j:integer; z:boolean;
begin z:true; for j:p to m do if not done[j] and (time[q]t[j]time[q-1]) then {找到合适的作业} begin z:false;done[j]:true; inc(l[q]);a[q,l[q]]:t[j];inc(time[q],t[j]);dec(rest,t[j]); try(j1,q); dec(l[q]);dec(time[q],t[j]);inc(rest,t[j]);done[j]:false; end; if z and ((least-q)*time[q]rest) then {如果处理机q已无法放任何作业} if rest0 then {找到最优解} begin a1:a;l1:l; print;halt end else if qmin then {继续搜索} try(1,q1);
end; begin readp; for i:1 to m do {判断无解情况即某一任务所需时间超过规定时间} if t[i]tmax then begin writeln(No answer!);exit end; repeat fillchar(time,sizeof(time),0); fillchar(l,sizeof(l),0); fillchar(l1,sizeof(l1),0); for i:1 to m do {贪心求上界} begin k:1; for j:2 to least do if time[j]time[k] then k:j; time[k]:time[k]t[i]; l1[k]:l1[k]1; a1[k,l1[k]]:t[i]; end; min:time[1]; for i:2 to least do if time[i]min then min:time[i]; if minleast then {如果贪心得出了最优解} begin print;halt; end; fillchar(time,sizeof(time),0); time[0]:tmax; try(1,1); inc(least); {下界加一} until leastm; print;
end. 参考书目
《国际国内青少年信息学计算机奥林匹克竞赛试题解析1994-1995》吴文虎王建德主编清华大学出版社。《奥林匹克计算机信息学入门》江文哉主编上海交通大学出版社。
