深搜剪枝

[e-mail]深度优先搜索中的剪枝北京大学信息科学技术学院郭炜据说，少林寺的镇寺之宝，是救秦王李世民的十三棍僧留下的若干根一样长的棍子。在民国某年，少林寺被军阀炮轰，这些棍子被炸成N节长度各异的小木棒。战火过后，少林方丈想要用这些木棒拼回原来的棍子。可他记不得原来到底有几根棍子了，只知道古人比较矮，且为了携带方便，棍子一定比较短。他想知道这些棍子最短可能有多短。46361345361436241916棍子长度：95用程序解决：输入：N节木棒的长度。输出：能拼成的最小的棍子长度。尝试(枚举）什么？枚举所有可能的棍子长度。从最长的那根木棒的长度一直枚举到木棒长度总和的一半，对每个假设的棍子长度，试试看能否拼齐若干根棍子。真的要每个长度都试吗？对于不是木棒总长度的因子的长度，可以直接否定，不需尝试。假设了一个棍子长度的前提下，如何尝试去拼成若干根该长度的棍子？一根一根地拼棍子。如果拼好前i根棍子，结果发现第i+1根无论如何拼不成了，那么就要推翻第i根的拼法，重拼第i根…..直至有可能推翻第1根棍子的拼法。本题的“状态”是什么？状态可以是一个二元组(R,M)R:还没被用掉的木棒数目。M:当前正在拼的棍子还缺少的长度。初始状态和搜索的终止状态(解状态）是什么？假设共有N节木棒，假定的棍子长度是L:初始状态：(N,L)终止状态：(0,0)所谓“成功拼出若干根长度为L的棍子”，就是要在状态空间中找到一条从(N,L)到(0,0)的路径“状态”之间如何转移？(R,M)(R-1,M-S)拼接一节长度为S的木棒(R-1,M-S)(R,M)拆掉一节长度为S的木棒以N=10,L=57为例:（10节木棒，假设棍子长度是57)9,114636134536143624191610,57初始状态棍子长度=579,119,1236134536143624191610,5746初始状态棍子长度=57以N=10,L=57为例:（10节木棒，假设棍子长度是57)9,129,214636133614362419164510,57初始状态棍子长度=57以N=10,L=57为例:（10节木棒，假设棍子长度是57)9,2146134536143624168,210,57初始状态1936棍子长度=57以N=10,L=57为例:（10节木棒，假设棍子长度是57)9,21463613453614362419168,28,510,57初始状态棍子长度=57以N=10,L=57为例:（10节木棒，假设棍子长度是57)boolDfs(intR,intM)表示:当前有R根未用木棒，而且当前正在拼的那根棍子比假定的棍子长度还少M,求在这种情况下能全部否拼成功。Dfs的基本递推关系：boolDfs(intR,intM){if(R==0&&M==0)returntrue;//拼接任务完成如果能找到一根长度不超过M的木棒,假设长为S，拼在当前棍子上，然后returnDfs(R–1,M-S);如果找不到：returnfalse;}#includeiostream#includememory.h#includestdlib.h#includevector#includealgorithmusingnamespacestd;intT,N;intL;vectorintanLength;intanUsed[65];//是否用过的标记inti,j,k;intDfs(intR,intM);intmain(){while(1){cinN;if(N==0)break;intnTotalLen=0;anLength.clear();for(inti=0;iN;i++){intn;cinn;anLength.push_back(n);nTotalLen+=anLength[i];}sort(anLength.begin(),anLength.end(),greaterint());for(L=anLength[0];L=nTotalLen/2;L++){if(nTotalLen%L)continue;memset(anUsed,0,sizeof(anUsed));if(Dfs(S,L)){coutLendl;break;}}if(LnTotalLen/2)coutnTotalLenendl;}//whilereturn0;}intDfs(intR,intM){//M表示当前正在拼的棍子和L比还缺的长度if(R==0&&M==0)returntrue;if(M==0)//一根刚刚拼完M=L;//开始拼新的一根for(inti=0;iN;i++){if(!anUsed[i]&&anLength[i]=M){anUsed[i]=1;if(Dfs(R-1,M-anLength[i]))returntrue;elseanUsed[i]=0;//说明本次不能用第i根//第i根以后还有用}}returnfalse;}敢问施主，要多久，才能拼好呢？有100多节木棒呢！怎么也得…10000年吧咣当！！恳请施主稍快一点，让老衲在有生之年,看到少林神棍修复完工！！没问题！用“剪枝”可以解决！搜索题，要解决一个问题：如何剪枝。即尽可能快地发现没有希望的状态，避免从没希望的状态往下继续尝试。不要在同一个位置多次尝试相同长度的木棒。即：如果某次拼接选择长度为S的木棒，导致最终失败，则在同一位置尝试下一根木棒时，要跳过所有长度为S的木棒。第一种剪枝方案：第二种剪枝方案：如果由于以后的拼接失败，需要重新调整第i根棍子的拚法，则不会考虑替换第i根棍子中的第一根木棒（换了也没用）。如果在不替换第一根木棒的情况下怎么都无法成功，那么就要推翻第i-1根棍子的拚法。如果不存在第i-1根棍子，那么就推翻本次假设的棍子长度，尝试下一个长度。若棍子i如下拼法导致最后不能成功:可以考虑把木棒2,3换掉重拼棍子i,但是把2，3都去掉后，换1是没有意义的。木棒1木棒2木棒3为什么替换第i根棍子的第一根木棒是没用的？因为假设替换后能全部拼成功，那么这被换下来的第一根木棒，必然会出现在以后拼好的某根棍子k中。那么我们原先拼第i根棍子时,就可以用和棍子k同样的构成法来拼，照这种构成法拼好第i根棍子，继续下去最终也应该能够全部拼成功。棍子k棍子i第二种剪枝方案：木棒1木棒m木棒n木棒1木棒m木棒n以N=10,L=57为例:（10节木棒，假设棍子长度是57)9,114636134536143624191610,57初始状态棍子长度=579,119,1236134536143624191610,5746初始状态棍子长度=57以N=10,L=57为例:（10节木棒，假设棍子长度是57)9,129,214636133614362419164510,57初始状态棍子长度=57以N=10,L=57为例:（10节木棒，假设棍子长度是57)9,2146134536143624168,210,57初始状态1936棍子长度=57以N=10,L=57为例:（10节木棒，假设棍子长度是57)intDfs(intR,intM){//M表示当前正在拼的棍子和L比还缺的长度if(R==0&&M==0)returntrue;if(M==0)//一根刚刚拼完M=L;//开始拼新的一根for(inti=0;iN;i++){if(!anUsed[i]&&anLength[i]=M){if(i0){if(anUsed[i-1]==false&&anLength[i]==anLength[i-1])continue;//剪枝1}anUsed[i]=1;if(Dfs(R-1,M-anLength[i]))returntrue;else{anUsed[i]=0;//说明本次不能用第i根//第i根以后还有用if(M==L)returnfalse;//剪枝2}}}returnfalse;}演示=1011还没有其他剪枝办法?到提交程序，看看你速度如何！剪枝3：不要希望通过仅仅替换已拼好棍子的最后一根木棒就能够改变失败的局面。123假设由于后续拼接无法成功，导致准备拆除的某根棍子如下：将3拆掉，留下的空用其他短木棒来填，是徒劳的棍子i剪枝3：12假设替换3后最终能够成功，那么3必然出现在后面的某个棍子k里。将棍子k中的3和棍子i中用来替换3的几根木棒对调，结果当然一样是成功的。这就和i原来的拚法会导致不成功矛盾棍子i3棍子k剪枝4：拼每一根棍子的时候，应该确保已经拼好的部分，长度是从长到短排列的，即拼的过程中要排除类似下面这种情况：1未完成的棍子i23木棒3比木棒2长，这种情况的出现是一种浪费。因为要是这样往下能成功，那么2,3对调的拚法肯定也能成功。由于取木棒是从长到短的，所以能走到这一步，就意味着当初将3放在2的位置时，是不成功的剪枝4：排除办法：每次找一根木棒的时候，只要这不是一根棍子的第一条木棒，就不应该从下标为0的木棒开始找，而应该从刚刚(最近）接上去的那条木棒的下一条开始找。这样，就不会往2后面接更长的3了123为此，要设置一个全局变量nLastStickNo，记住最近拼上去的那条木棒的下标。intDfs(intnUnusedSticks,intnLeft)//nLeft表示当前正在拼的棍子和L比还缺的长度{if(nUnusedSticks==0&&nLeft==0)returntrue;if(nLeft==0)//一根刚刚拼完nLeft=L;//开始拼新的一根intnStartNo=0;if(nLeft!=L)//剪枝4nStartNo=nLastStickNo+1;for(inti=nStartNo;iS;i++){if(!anUsed[i]&&anLength[i]=nLeft){if(i0){if(anUsed[i-1]==false&&anLength[i]==anLength[i-1])continue;//剪枝1}anUsed[i]=1;nLastStickNo=i;if(Dfs(nUnusedSticks-1,nLeft-anLength[i]))returntrue;else{anUsed[i]=0;//说明本次不能用第i根//第i根以后还有用if(anLength[i]==nLeft||nLeft==L)returnfalse;//剪枝3、2}}}returnfalse;}关于搜索顺序的经验本题先尝试长的木棒，后尝试短的木棒。因为长的木棒能摆放的位置更少。由此可以总结一个结论：如果整个任务由p1,p2,…pn个步骤构成，这几个步骤先后次序无所谓，不同的步骤的可能得做法数目不同，则应该优先尝试可选方案少的步骤。例如：p1这个步骤有n1种可能的做法p2这个步骤有n2种可能的做法,且n2n1那么就应该先尝试p2这个步骤关于搜索顺序的经验例如七巧板问题。给定一个棋盘，以及多个形状、大小不同的棋子，问如何才能用这些棋子盖满整个棋盘，且棋子互不重叠。关于搜索顺序的经验搜索时应该先放不容易摆放的棋子。比如面积大的，最大长度长的，形状特殊的，等等，然后再放容易摆放的棋子。