搜素加剪枝:剪枝是技巧,而不是方法,也就是说,可能一点实用的小技巧,让程序可以少判断一点,这就是剪枝,剪枝无处不在。搜索的进程可以看作是从树根出发,遍历一棵倒置的树—-搜索树的过程。而所谓的剪枝,顾名思义,就是通过某种判断,避免一些不必要的遍历过程,形象的说,就是减去了搜索树中的某些“枝条”,故称剪枝。(杭电课件上是这么说的:即剪去解答树上已被证明不可能存在可行解或最优解的子树.)既然采用了搜索,剪枝就显得十分的必要,即使就简简单单的设一个槛值,或多加一两条判断,就可对搜索的效率产生惊人的影响。例如N后问题,假如放完皇后再判断,则仅仅只算到7,就开始有停顿,到了8就已经超过了20秒,而如果边放边判断,就算到了10,也没有停顿的感觉。所以,用搜索一般都就要剪枝。剪枝至少有两方面,一是从方法上剪枝,如采用分枝定界,启发式搜索等,适用范围比较广;二是使用一些小技巧,这类方法适用性虽不如第一类,有时甚至只能适用一道题,但也十分有效,并且几乎每道题都存在一些这样那样的剪枝技巧,只是每题有所不同而已。剪枝的原则:1.正确性:必须保证不丢失正确的结果。2.准确性:能够尽可能多的减去不能通向正解的枝条3.高效性:在很多时候,为了加强优化的效果,我们会增加一些判断,这样对程序效率也带来了副作用,所以要考虑剪枝的高效性,否则得不偿失。最后说一下:剪枝在搜索中用的是非常的广泛的。变形课TimeLimit:2000/1000MS(Java/Others)MemoryLimit:131072/65536K(Java/Others)TotalSubmission(s):14003AcceptedSubmission(s):5171ProblemDescription呃......变形课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒语是以a开头b结尾的一个单词,那么它的作用就恰好是使A物体变成B物体.Harry已经将他所会的所有咒语都列成了一个表,他想让你帮忙计算一下他是否能完成老师的作业,将一个B(ball)变成一个M(Mouse),你知道,如果他自己不能完成的话,他就只好向Hermione请教,并且被迫听一大堆好好学习的道理.Input测试数据有多组。每组有多行,每行一个单词,仅包括小写字母,是Harry所会的所有咒语.数字0表示一组输入结束.Output如果Harry可以完成他的作业,就输出Yes.,否则就输出No.(不要忽略了句号)SampleInputsosoonrivergoesthemgotmoonbeginbig0SampleOutputYes.HintHintHarry可以念这个咒语:big-got-them.刚开始这个题目一直没看懂什么意思,趴在桌子上睡了个午觉,起来后,再看,还是迷糊。。。这个时候,突然间,图书馆外天空放晴,太阳光芒照耀大地,我也顿悟了。原来harry施展魔法,只需要几个词首位相同才能连接起来,并且整体的首位分别是’b'和’m’#includeiostreamusingnamespacestd;typedefstructWord{charbegin,end;boolvis;}Word;Wordwords[100];intn,flag;voidDFS(charch){inti;if(flag==1)return;if(ch=='m'){flag=1;return;}for(i=1;in;++i)if(words[i].begin==ch&&!words[i].vis){words[i].vis=1;DFS(words[i].end);words[i].vis=0;}}intmain(){inti;chartmp[30];while(scanf(%s,tmp)!=EOF){n=1;while(strcmp(tmp,0)){words[n].begin=tmp[0];i=0;while(tmp[i++]!='\0');words[n].end=tmp[i-2];words[n].vis=0;n++;scanf(%s,tmp);}flag=0;DFS('b');printf(flag==1?Yes.\n:No.\n);}return0;}话说MiYu喜欢走YD流的,不知道他在哪里看见了这么YD的AC代码:#includeiostreamusingnamespacestd;charss[10];intmain(){intflag=1;while(gets(ss)){if(strcmp(ss,0)==0){if(flag){printf(Yes.\n);flag=0;}elseprintf(No.\n);}}return0;}