c语言技巧之搜索剪枝

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

大概题意：

Farmer John想抓到一头牛，Farmer John在一个数轴的一个位子，牛在数轴的另一个位子。但Farmer John这个人在一个单位时间内可以有三种走的方式，一是走到数轴的下一格，或是前一格，或是他的数轴的两倍的格子上，为此人最快抓到牛的时间。

解题思想：

其实是上面的一个变形，棋子变成了一个人和一头牛，然后走的规则变了一下，问的步数变成了时间。所以模板还是基本和上面的一样。

参考代码：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

#include #include using namespace std; int digit[200001]; int start,end; int index; bool find;

vectorvc;

void deal(int x,int time) { if (x==end) { find=true; return; } if (x+1<=100000&&digit[x+1]==-1) { digit[x+1]=time+1; vc.push_back(x+1); } if (x-1>=0&&digit[x-1]==-1) { digit[x-1]=time+1; vc.push_back(x-1); } if (x*2<=200000&&digit[x*2]==-1) {

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

digit[x*2]=time+1; vc.push_back(x*2); } }

int main() { cin>>start>>end; memset(digit,-1,sizeof(digit)); vc.clear(); vc.push_back(start); digit[start]=0; index=0; find=false; while (index

专题3：剪枝问题

剪枝是一个非常有趣的课题，往往需要发挥自己的创造性与想象力，同时需要有敏感的观察力和一定的经验。

主要的剪枝思想有三种：极端法，调整法，数学方法。

极端法 极端法广泛地应用在各种搜索算法的剪枝中。它的基本思想是通过对当前结点进行理想式扩展，通过否认这样的“理想情况”来避免对当前结点的扩展。

调准法 调准法的基本思想是通过对子树的比较剪掉重复子树和明显不是最有“前途”的子树。

数学方法 上面的两种方法为一般方法，然而对于一些具体问题，也可以应用一些专门的知识进行剪枝。例如在图论中借助连通分量，数论中借助模方程的分析等。

极端法在上面的2248 Addition Chains有很好的体现，对于搜索中到达的数，如果按

照理想方式（即最少步数）到达所给定的数的总和比当前找到的最少的步数还大，那么就不需要扩展这个子树。

调准法举例：

1011 Sticks

Description

乔治拿来一组等长的木棒，将它们随机地裁断，使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。

Input

输入包含多组数据，每组数据包括两行。第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。第二行是截断以后，所得到的各节木棍的长度。在最后一组数据之后，是一个零。

Output

为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

Sample Input

9

5 2 1 5 2 1 5 2 1 4

1 2 3 4 0

Sample Output

6 5

解题思想：

此题是一个经典的深度优先搜索和剪枝的题目，对程序设计的技巧性要求非常大。一堆杂乱长度不等的木头，怎样才能把他们分组使得每一组长度之和相等呢？首先，每组的长度一定是所有木头长度和的约数，即所有木头长度之和能被每组木头长度之和整除。问题要我们找原始木头可能最小的长度，那么我们可以编制一个每组木头长度之和的循环，循环的初始值为木头中最大的长度，循环的边界是所有木头长度之和，这样就保证了得到可能最小长度的木头。当循环中的数不能整除所有木头的长度时我们就跳过，直至找到下一个可以整除的数。

当我们找到一个约数时，此时就需要尝试着去拼接了。我们把木头按大到小进行排序。这样做一是减少运行时间，二是方便于剪枝。我们编写这样一个函数 deal(int n,int m,int left,int len)

n是木头的数目，m是剩下还没有拼接的木头的数目，left是剩下的需要去找拼接的木头的长度，需要拼接的木头的长度，初始值为n,n,0,i。当找到一段木头时，m就减1。Left就减去找到的木头的长度，当left为0并且还有木头等待去找是就把left赋len。

显然只按上面去编写的程序效率仍然不是很高，程序中还执行一些不必要去做的工作，此时我们就需要剪枝了，怎么剪呢？可以找到两种可以剪去的枝。1：当我们按顺序找到一段刚好可以满足要求使得长度为要求的长度时，我们就没有必要再去拼接那些更小的长度的木头使得满足要求，即使找到，那么此种能拼接成的组合没有大木头更有希望获得可行解。所以当用大木头去填充而获不到可行解时，那么就没有必要去考虑更小的木头了。2：当我们拼接好一段木头时突然发现接下来以另一根最大的木头为底去拼接而不可行时，那么就没有必要再去考察后面小的木头做底去拼接了，因为所有木头都必须参与拼接，那个拼不了的最大的木头始终要参与拼接，所以最后还是会失败！考虑完了深搜和剪枝就可以编写程序了。

参考代码：

#include using namespace std; int start;

int stricks[64]; bool isuse[64];

int compare(const void *ele1,const void *ele2) { return *(int*)ele2-*(int*)ele1; }

bool deal(int n,int m,int left,int len) { int i; if(m==0&&left==0) return true; if(left==0) { i=0; left=len; } else { i=start+1; } for (;ileft) continue; isuse[i]=true; start=i; if(deal(n,m-1,left-stricks[i],len)) return true; else