搜索剪枝常见方法与技巧

《搜索剪枝常见方法与技巧》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、搜索剪枝常见方法与技巧关键字搜索方法,剪枝摘要搜索是计算机解题中常用的方法，它实质上是枚举法的应用。由于它相当于枚举法，所以其效率是相当地的。因此，为了提高搜索的效率，人们想出了很多剪枝的方法，如分枝定界，启发式搜索等等。在竞赛中，我们不仅要熟练掌握这些方法，而且要因地制宜地运用一些技巧，以提高搜索的效率。正文搜索的效率是很低的，即使剪枝再好，也无法弥补其在时间复杂度上的缺陷。因此，在解题中，除非其他任何方法都行不通，才可采用搜索。既然采用了搜索，剪枝就显得十分的必要，即使就简简单单的设一个槛值，或多加一两条判

2、断，就可对搜索的效率产生惊人的影响。例如Ｎ后问题，假如放完皇后再判断，则仅仅只算到７，就开始有停顿，到了８就已经超过了２０秒，而如果边放边判断，就算到了１０，也没有停顿的感觉。所以，用搜索就一定要剪枝。剪枝至少有两方面，一是从方法上剪枝，如采用分枝定界，启发式搜索等，适用范围比较广；二是使用一些小技巧，这类方法适用性虽不如第一类，有时甚至只能适用一道题，但也十分有效，并且几乎每道题都存在一些这样那样的剪枝技巧，只是每题有所不同而已。问题一：(最短编号序列)表A和表B各含k(k<=20)个元素，元素编号从1到k。

3、两个表中的每个元素都是由0和1组成的字符串。（不是空格）字符串的长度<=20。例如下表的A和B两个表，每个表都含3个元素（k=3）。16元素编号字符串11210111310表A表B元素编号字符串111121030对于表A和表B，存在一个元素编号的序列2113，分别用表A中的字符串和表B中的字符串去置换相应的元素编号，可得相同的字符串序列101111110，见下表。元素编号序列2113用表A的字符串替换101111110用表B的字符串替换101111110对表A和表B，具有上述性质的元素编号序列称之为S(AB)。

4、对于上例S(AB)=2113。编写程序：从文件中读入表A和表B的各个元素，寻找一个长度最短的具有上述性质的元素编号序列S(AB)。（若找不到长度<=100的编号序列，则输出“NoAnswer”。对于这道题，因为表Ａ和表Ｂ不确定，所以不可能找到一种数学的方法。因为所求的是最优解，而深度优先搜索很容易进入一条死胡同而浪费时间，所以必须采用广度优先搜索的方法。但是，广度优先搜索也有其缺陷。当表Ａ和表Ｂ中的元素过多是，扩展的结点也是相当多的，搜索所耗费的时间也无法达到测试的要求。为了解决这个问题，就必须对搜索的算法加以

5、改进。分枝限界似乎不行，因为无法确定代价。而且，由于目标不确定，也无法设定估价函数。但是，因为此题的规则既可以正向使用，又可以逆向使用，于是便可以采用双向搜索。在大方法确定后，算法的框架就已经基本形成，但即使如此，算法也还有可改进的地方。1.存储当前的Ａ串和Ｂ串是很费空间的，但因为Ａ串和Ｂ串的大部分相同，故只需记录不同部分，并作个标记。再换成动态存储。2.为了保证两个方向扩展结点的速度相对平衡，可以采取每次扩展结点数较少的方向，而不是两方向轮流扩展。如此一来，搜索的效率就比单纯的广度优先搜索有了明显的提高。（附

6、程序sab.pas）有时，搜索也会有不同的搜索方法（如多处理机调度问题），也会产生不同的效率。问题二：（任务安排）16Ｎ个城市，若干城市间有道路相连，一辆汽车在城市间运送货物，总是从城市１出发，又回到城市１。该车每次需完成若干个任务，每个任务都是要求该车将货物从一个城市运送至另一个。例如若要完成任务２－>6，则该车一次旅程中必含有一条子路径。先到２，再到６。如下图所示，如果要求的任务是２－>３，２－>４，３－>１，２－>５，６－>４，则一条完成全部任务的路径是１－>２－>３－>１－>２－>５－>６－>４－>１。

7、　　　　　　4１　　2　　　　　　6　　　　　　　5　　3　　　　　7编程由文件读入道路分布的领接矩阵，然后对要求完成的若干任务，寻找一条旅行路线，使得在完成任务最多的前提下，经过的城市总次数最少。如上例中经过城市总次数为８，城市１和２各经过２次均以２次计（起点不计），Ｎ<60。这道题，因为很难找到数学规律，便只有采用搜索的方法。首先，第一感觉便是：从城市i出发，便搜索所有相邻的城市，再根据当前所处的城市，确定任务的完成情况，从中找到最优解。这种搜索的效率是极低的，其最大原因就在于：目标不明确。根据题意，我们只

8、需到达需上货和下货的城市，其它的城市仅作为中间过程，而不应作为目标。因此，首先必须确定可能和不可能完成的任务，然后求出任意两城市间的最短路径。在搜索时，就只需考虑有货要上的城市，或者是要运到该城市的货全在车上，其它不须考虑。同时，还可以设定两个简单的槛值。如果当前费用+还需达的城市>=当前最优解，或当前费用+返回城市1的费用>=当前最优解，则不需继续往下搜索。这种方法与第一感的方法有天