目录
搜索剪枝常见方法与技巧
关键字 搜索方法,剪枝
摘要
正文
小结
程序
参考书目
搜索剪枝常见方法与技巧
关键字 搜索方法,剪枝
摘要
搜索是计算机解题中常用的方法，它实质上是枚举法的应用。由于它相当于枚举法，所以其效率是相当地的。因此，为了提高搜索的效率，人们想出了很多剪枝的方法，如分枝定界，启发式搜索等等。在竞赛中，我们不仅要熟练掌握这些方法，而且要因地制宜地运用一些技巧，以提高搜索的效率。
正文
搜索的效率是很低的，即使剪枝再好，也无法弥补其在时间复杂度上的缺陷。因此，在解题中，除非其他任何方法都行不通，才可采用搜索。
既然采用了搜索，剪枝就显得十分的必要，即使就简简单单的设一个槛值，或多加一两条判断，就可对搜索的效率产生惊人的影响。例如Ｎ后问题，假如放完皇后再判断，则仅仅只算到７，就开始有停顿，到了８就已经超过了２０秒，而如果边放边判断，就算到了１０，也没有停顿的感觉。所以，用搜索就一定要剪枝。
剪枝至少有两方面，一是从方法上剪枝，如采用分枝定界，启发式搜索等，适用范围比较广；二是使用一些小技巧，这类方法适用性虽不如第一类，有时甚至只能适用一道题，但也十分有效，并且几乎每道题都存在一些这样那样的剪枝技巧，只是每题有所不同而已。
问题一：(最短编号序列)
表A和表B各含k(k<=20)个元素，元素编号从1到k。两个表中的每个元素都是由0和1组成的字符串。（不是空格）字符串的长度<=20。例如下表的A和B两个表，每个表都含3个元素（k=3）。
| 元素编号 | 字符串 |
| 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需要处理机处理的时间为Ti（i=1,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 aa=string[100];
ltype=record
f:integer; {父指针}
k,d,la,lb:shortint;
{k--剩余串标志，d--序列中元素的编号，la,lb--A，B两串的串长}
st:^aa; {剩余串}
end;
const maxn=1300;
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 k<>1 then begin
if q=1 then
writeln(p[q,k].d);
print(q,p[q,k].f);
if q=0 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]].k<>p[1-q,i].k) and (p[q,t[q]].st^=p[1-q,i].st^) and
(p[q,t[q]].la+p[1-q,i].la<=100) and (p[q,t[q]].lb+p[1-q,i].lb<=100)
then begin
if q=0 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]].la+length(strs[1,i])<=100) and
(p[q,h[q]].lb+length(strs[2,i])<=100) then
begin
sa:='';sb:='';
if p[q,h[q]].k=1
then sa:=p[q,h[q]].st^
else sb:=p[q,h[q]].st^;
if q=0 then {沿不同方向将编号为i的元素加到序列中}
begin
sa:=sa+strs[1,i];
sb:=sb+strs[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]].la+length(strs[1,i]);
lb:=p[q,h[q]].lb+length(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为终点的任务的所有顶点都在完成任务路径中}
{k+1表示以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 (cost+left>=mincost) or (cost+dist[1,d[s]]>=mincost) then exit;
if left=0 then {是否完成了所有任务}
begin
mincost:=cost+dist[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 i<>j 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[i+1]);
writeln;
writeln('Min cost=',mincost);
end;
begin
init;
try;
print;
end.
- 多处理机调度问题：
任务一：jobs_1.pas
program jobs_1;
const maxn=100; {处理机的最多数目}
maxm=100; {作业的最多数目}
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 n+1; {定下界}
for i:=1 to m-1 do {排序}
for j:=i+1 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(j+1,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 rest=0 then {找到一组解}
begin
a1:=a;l1:=l;
time[0]:=time[1]-1;
if time[1]=least then
begin print;halt end;
end
else if q<n then {继续搜索}
try(1,q+1);
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 min=least 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 maxn=100; {处理机的最多数目}
maxm=100; {作业的最多数目}
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 tmax+1; {确定下界}
for i:=1 to m-1 do {排序}
for j:=i+1 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(j+1,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 rest=0 then {找到最优解}
begin
a1:=a;l1:=l;
print;halt
end
else if q<min then {继续搜索}
try(1,q+1);
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 min=least then {如果贪心得出了最优解}
begin
print;halt;
end;
fillchar(time,sizeof(time),0);
time[0]:=tmax;
try(1,1);
inc(least); {下界加一}
until least>m;
print;
end.
参考书目
- 《国际国内青少年信息学（计算机）奥林匹克竞赛试题解析（1994-1995》，吴文虎，王建德主编，清华大学出版社。
- 《奥林匹克计算机（信息学）入门》，江文哉主编，上海交通大学出版社。
