搜索加剪枝

搜素加剪枝：剪枝是技巧，而不是方法，也就是说，可能一点实用的小技巧，让程序可以少判断一点，这就是剪枝，剪枝无处不在。搜索的进程可以看作是从树根出发，遍历一棵倒置的树—-搜索树的过程。而所谓的剪枝，顾名思义，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是减去了搜索树中的某些“枝条”，故称剪枝。(杭电课件上是这么说的：即剪去解答树上已被证明不可能存在可行解或最优解的子树.)既然采用了搜索，剪枝就显得十分的必要，即使就简简单单的设一个槛值，或多加一两条判断，就可对搜索的效率产生惊人的影响。例如Ｎ后问题，假如放完皇后再判断，则仅仅只算到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;}