《搜索剪枝常见方法与技巧.doc》由会员分享，可在线阅读，更多相关《搜索剪枝常见方法与技巧.doc（16页珍藏版）》请在金锄头文库上搜索。
1、 搜索剪枝常见方法与技巧关键字 搜索方法,剪枝摘要搜索是计算机解题中常用的方法，它实质上是枚举法的应用。由于它相当于枚举法，所以其效率是相当地的。因此，为了提高搜索的效率，人们想出了很多剪枝的方法，如分枝定界，启发式搜索等等。在竞赛中，我们不仅要熟练掌握这些方法，而且要因地制宜地运用一些技巧，以提高搜索的效率。正文搜索的效率是很低的，即使剪枝再好，也无法弥补其在时间复杂度上的缺陷。因此，在解题中，除非其他任何方法都行不通，才可采用搜索。既然采用了搜索，剪枝就显得十分的必要，即使就简简单单的设一个槛值，或多加一两条判断，就可对搜索的效率产生惊人的影响。例如后问题，假如放完皇后再判断，则仅仅只算到
2、，就开始有停顿，到了就已经超过了秒，而如果边放边判断，就算到了，也没有停顿的感觉。所以，用搜索就一定要剪枝。剪枝至少有两方面，一是从方法上剪枝，如采用分枝定界，启发式搜索等，适用范围比较广；二是使用一些小技巧，这类方法适用性虽不如第一类，有时甚至只能适用一道题，但也十分有效，并且几乎每道题都存在一些这样那样的剪枝技巧，只是每题有所不同而已。问题一：(最短编号序列)表A和表B各含k(k=20)个元素，元素编号从1到k。两个表中的每个元素都是由0和1组成的字符串。（不是空格）字符串的长度=20。例如下表的A和B两个表，每个表都含3个元素（k=3）。 元素编号 字符串 1 1 2 10111 3 1
3、0表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)。（若找不到长度6，则该车一次旅程中必含有一条子路径。先到，再到。如下图所示，如
4、果要求的任务是，则一条完成全部任务的路径是。 4 2 6 5 37 编程由文件读入道路分布的领接矩阵，然后对要求完成的若干任务，寻找一条旅行路线，使得在完成任务最多的前提下，经过的城市总次数最少。如上例中经过城市总次数为，城市和各经过次均以次计（起点不计），=当前最优解，或当前费用+返回城市1的费用=当前最优解，则不需继续往下搜索。这种方法与第一感的方法有天壤之别。（附程序travell.pas）问题三：（多处理机调度问题）设定有若干台相同的处理机P1,P2Pn,和m个独立的作业J1,J2jm,处理机以互不相关的方式处理作业，现约定任何作业可以在任何一台处理机上运行，但未完工之前不允许中断作业
5、，作业也不能拆分成更小的作业，已知作业Ji需要处理机处理的时间为Ti（i=1,2m）。编程完成以下两个任务：任务一：假设有n台处理机和m个作业及其每一个作业所需处理的时间Ti存放在文件中，求解一个最佳调度方案，使得完成这m个作业的总工时最少并输出最少工时。任务二：假设给定作业时间表和限定完工时间于文件中，求解在限定时间内完成这批作业所需要最少处理机台数和调度方案。此题有两种搜索方法：方法一：按顺序搜索每个作业。当搜索一个作业时，将其放在每台处理机搜索一次。方法二：按顺序搜索每台处理机。当搜索一台处理机时，将每个作业放在上面搜索一次。对比上述两种方法，可以发现：方法二较方法一更容易剪枝。下面是两
6、中方法剪枝的对照：对于方法一：只能根据目前已确定的需时最长的处理机的耗时与目前最佳解比较。对于方法二：可约定Time1Time2Time3 Timen（Timei表示第i台处理机的处理时间）,从而可以设定槛值：如当前处理机的处理时间=目前最佳解，或剩下的处理机台数上一台处理机的处理时间剩余的作业需要的处理时间，则回溯。因为在前面的约束条件下，已经不可能有解。 因此，从上面的比较来看，第二种方法显然是比第一种要好的。下面就针对第二种方法更深一层的进行探讨。 对于任务一，首先可以用贪心求出Time1的上界。然后，还可以Time1的下界，UP（作业总时间/处理机台数）。（UP表示大于等于该小数的最小
7、整数）。搜索便从上界开始，找到一个解后，若等于下界即可停止搜索。（附程序jobs_1.pas) 对于任务二，可采用深度+可变下界。下界为：UP（作业总时间/限定时间），即至少需要的处理机台数。并设定Time1的上界为T。（附程序jobs_2.pas） 小结搜索的使用相当广泛，几乎每题都可以采用搜索的方法。虽然如此，搜索也切不可滥用。只有当问题无规律可寻时，才可用搜索。一旦确定了使用搜索，就一定要想办法对其进行剪枝。无论是采用剪枝的常见方法，还是用一些搜索的小技巧，虽都无法降低搜索的时间复杂度，却总还是大有裨益的。程序1. 最短编号序列：sab.pasprogram sab;type aa=st
8、ring100; ltype=record f:integer; 父指针 k,d,la,lb:shortint; k-剩余串标志，d-序列中元素的编号，la,lb-A，B两串的串长 st:aa; 剩余串 end;const maxn=1300;var t,h:array0.1 of integer; h-队首指针，t-队尾指针，0表示正向，1表示逆向 p:array0.1,1.maxn of ltype; p0-正向搜索表，p1-逆向搜索表 strs:array1.2,1.20 of string20; strs1-表A元素，strs2-表B元素 n:integer; 表A和表B的元素个数pr
9、ocedure 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,strs1,i); for i:=1 to n do readln(f,strs2,i); close(f);end;procedure print(q,k:integer); 从k出发，输出沿q方向搜索的元素编号begin if k1 then begin if q=1 then writ
10、eln(pq,k.d); print(q,pq,k.f); if q=0 then writeln(pq,k.d); end;end;procedure check(q:shortint); 判断两方向是否重合，q表示刚产生结点的方向的相反方向var i:integer;begin for i:=1 to t1-q-1 do if (pq,tq.kp1-q,i.k) and (pq,tq.st=p1-q,i.st) and (pq,tq.la+p1-q,i.la=100) and (pq,tq.lb+p1-q,i.lb=100) then begin if q=0 then begin print(0,tq); print(1,i); end else begin
