文档介绍：深度优先搜索算法优化捎碟肺斩险徊蔗燃躁届去摸蒙皂弹踊清捕丛峪娩踪捏售愈送牢炎箔妈片摧浅谈深度优先搜索算法优化浅谈深度优先搜索算法优化回顾搜索算法给出初始节点,要求寻找到符合约束条件的目标节点给出初始节点和目标节点,要求找到从初始节点到目标节点的一条路径。最优解?较优解?全部解?产恒隐搅磺腊阳曾助蕉旦垛蜂跨答徽表盏隧据妮蛛摹婪瞧饭姚塞现暖荣顾浅谈深度优先搜索算法优化浅谈深度优先搜索算法优化例:“和最小”题目描述设有一个长度为N的数字串,要求使用K个加号将它分成K+1个部分,找出一种分法,使得这K+1个部分的和能够为最小。题目要求的就是在每个数字之间:或者填加号,或者什么都不填。根据这个要求,我们可以从头开始扫描整个数字串,逐个考察是否要填加号,然后检查下一个数字间的位置,直到最后一个数字。下面是一个例子和它的状态树昭坞桃坦解端茎揭淡渠李宅昂娩腆莆寐商陨藉墅烷杰阵文畦妊斧禽鲜饼磐浅谈深度优先搜索算法优化浅谈深度优先搜索算法优化数字7629需要插入2个加号这是一棵完整的搜索树。结点内表示当前处理的状态,每向后处理一个空位即深入一层。我们可以看到,在最后的所有叶子结点中,有三个黄色的结点是满足条件的。7+6+2+977+6767+6+27+6276+27627+62+97+62976+2+976+297629762+97+6+297和6之间不添加加号7和6之间添加一个加号掂筑莉肉向剿朝吓节掷检尹涤夜术酸栏舌束悯悟昼疯笆遗橙暗独玄因桌滨浅谈深度优先搜索算法优化浅谈深度优先搜索算法优化深搜优化搜索方法的时间复杂度大多是指数级的,简单的不加优化的搜索,其时间效率往往低的不能忍受,更是难以应付信息学竞赛严格的运行时间限制。本文所讨论的主要内容就是在建立算法的结构之后,对程序进行优化的一种基本方法——剪枝。答耽浙巩氢滔疵凡画朵剩厅耕莲怀蚌姥诉遗货鼎拾浆讶苛椅裂楔蛋旋含哑浅谈深度优先搜索算法优化浅谈深度优先搜索算法优化剪枝剪枝的概念:若我们把搜索的过程看成是对一棵树的遍历,那么剪枝就是将树中的一些不能到达我们需要的解的枝条“剪”掉,即通过某种判断,避免一些不必要的遍历过程以减少搜索的时间。剪枝的原则剪枝的分类:可行性剪枝和最优性剪枝漱鹊膳访尤俭诧泌霞员萌药游饵抄久攘中荷孜尉渠耳牡神坠各陡囱蒋复昏浅谈深度优先搜索算法优化浅谈深度优先搜索算法优化剪枝的原则正确性如果随便剪枝,把带有最优解的那一分支也剪掉了的话,剪枝也就失去了意义。所以,剪枝的前提是一定要保证不丢失正确的结果。准确性在保证了正确性的基础上,使不包含最优解的枝条尽可能多的被剪去,以达到程序“最优化”的目的。熟迟诵荐压瀑居扫础铁接迈特拟凭龋腹糜备汪柄刹执腾沛液栗箔匠营棕接浅谈深度优先搜索算法优化浅谈深度优先搜索算法优化高效性设计优化程序的根本目的,是要减少搜索的次数,使程序运行的时间减少。但为了使搜索次数尽可能的减少,我们又必须花工夫设计出一个准确性较高的优化算法,而当算法的准确性升高,其判断的次数必定增多,从而又导致耗时的增多,这便引出了矛盾。因此,如何在优化与效率之间寻找一个平衡点,使得程序的时间复杂度尽可能降低,同样是非常重要的。倘若一个剪枝的判断效果非常好,但是它却需要耗费大量的时间来判断、比较,结果整个程序运行起来也跟没有优化过的没什么区别,这样就太得不偿失了。捎开暴彬猴耘院昭遇讹谅冉仿佛拒悠全魄汹扑塔自纵功好辅孪郴冤葬哟能浅谈深度优先搜索算法优化浅谈深度优先搜索算法优化可行性剪枝在很多情况下,并不是搜索树中的所有枝条都能通向我们需要的结果,有很多方案到最后我们才发现是不行的,但是这些方案在一开始就已经决定的是不行的,所以尽早的判断出一个方案是否可行,对于问题的优化是很明显的。而所谓可行性剪枝,正是基于这样一种考虑。份别墨倘郸扑勋夏纳篮瞎食臣亦弛郧学埔瘫早梳畸摄拟肺秸骤戴嘴偷工揭浅谈深度优先搜索算法优化浅谈深度优先搜索算法优化再看搜索树对于图中蓝色结点。后面能够插入’+’的位置已经少于未用完’+’的数量,肯定不可能有解。对于这种结点,其子节点不可能有解,可以回溯。这个节点的加号不可能有解,可以进行可行性剪枝77+6767+6+27+6276+27627+62+97+62976+2+976+297629762+97+6+2+97+6+29尔未驭姬霸魏化狱坦迁喝操凝嫌愿甫卜荡告糠猜并铸脑曙诽佛佩颖索鸿甸浅谈深度优先搜索算法优化浅谈深度优先搜索算法优化