ACM-DFS-BFS汇总教学讲解课件

搜索

DFS+BFS

剪枝预备知识——树的遍历树的遍历主要有如下四种方法：1.先根/序遍历2.中根/序遍历3.后根/序遍历4.层次遍历分别有什么特点呢？工大ACM团队（1）先根遍历对树的访问次序是:1.先访问根结点2.再访问左子树3.最后访问右子树4.对于左右子树的访问也要满足以上规则示例如下：工大ACM团队以上二叉树的先根遍历序列是：？？21357461、2、4、5、3、6、7工大ACM团队（2）中根遍历对树的访问次序是:1.先访问左子树2.再访问根结点3.最后访问右子树4.对于左右子树的访问也要满足以上规则示例如下：工大ACM团队以上二叉树的中根遍历序列是：？？21357464、2、5、1、6、3、7工大ACM团队（3）后根遍历对树的访问次序是:1.先访问左子树2.再访问右子树3.最后访问根结点4.对于左右子树的访问也要满足以上规则示例如下：工大ACM团队以上二叉树的后根遍历序列是：？？21357464、5、2、6、7、3、1工大ACM团队（4）层次遍历对树的访问次序是:1.先访问根结点2.再访问根结点的子节点（即第二层节点）3.再访问第三层节点4.……示例如下：工大ACM团队以上二叉树的层次遍历序列是：？？21357461、2、3、4、5、6、7工大ACM团队几个基本概念：初始状态：略目标状态：略状态空间：由于求解问题的过程中分枝有很多（主要是求解过程中求解条件的不确定性、不完备性造成的），使得求解的路径很多，这就构成了一个图，我们说这个图就是状态空间。状态空间搜索：就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一条解题的过程，可以从求解的开始到问题的结果。工大ACM团队DFS+BFS深度优先搜索深度优先搜索（DepthFirstSearch）类似于树的先根遍历深搜例子：走迷宫，你没有办法用分身术来站在每个走过的位置。不撞南山不回头。广度优先搜索（BreadthFirstSearch）类似于树的按层次遍历的过程广搜例子:你的眼镜掉在地上以后，你趴在地板上找。你总是先摸最接近你的地方，如果没有，再摸远一点的地方……工大ACM团队深度优先搜索基本思想从初始状态S开始，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态G，若未出现，以此状态利用规则生成再下一层任一个结点，再检查是否为目标节点G，若未出现，继续以上操作过程，一直进行到叶节点（即不能再生成新状态节点），当它仍不是目标状态G时，回溯到上一层结果，取另一可能扩展搜索的分支。生成新状态节点。若仍不是目标状态，就按该分支一直扩展到叶节点，若仍不是目标，采用相同的回溯办法回退到上层节点，扩展可能的分支生成新状态，…，一直进行下去，直到找到目标状态G为止。工大ACM团队搜索过程如下：HALIFBCDEJGKS深度优先搜索示意图工大ACM团队广度优先搜索基本思想从初始状态S开始，利用规则，生成所有可能的状态。构成树的下一层节点，检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别顺序利用规则。生成再下一层的所有状态节点，对这一层的所有状态节点检查是否出现G，若未出现，继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。工大ACM团队搜索过程如下：OPLWVUTRQABCDGEFS广度优先搜索示意图工大ACM团队

BFS、DFS算法比较DFS：使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。

BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进、出队列。工大ACM团队8123456781234567入口出口迷宫问题-DFS寻找一条从入口到出口的通路工大ACM团队东南迷宫问题(续)北(上)西(左)前进方向：上(北)、下(南)、左(西)、右(东)首先从下方开始，按照逆时针方向搜索下一步可能前进的位置工大ACM团队迷宫问题(续)入口出口在迷宫周围加墙，避免判断是否出界81234567812345679090工大ACM团队8123456781234567迷宫问题(续)9090在寻找出口的过程中，每前进一步，当前位置入栈；每回退一步，栈顶元素出栈栈(1,1)工大ACM团队i8123456781234567迷宫问题(续)9090栈(1,1)(2,1)向下方前进一步工大ACM团队i迷宫问题(续)81234567812345679090栈(1,1)(2,1)i(3,1)向下方前进一步工大ACM团队ii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(4,1)(3,1)i向下方前进一步break工大ACM团队iiii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(5,1)(3,1)(4,1)向下方前进一步break工大ACM团队iiiii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(6,1)(3,1)(4,1)(5,1)向下方前进一步break工大ACM团队iiiiii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)向下方前进一步break工大ACM团队iiiiii@迷宫问题(续)81234567812345679090向下方、右方、左方均不能前进，上方是来路，则后退栈(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)break工大ACM团队iiiii@@迷宫问题(续)81234567812345679090栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)向右方、左方均不能前进，下方路不通，上方是来路，则后退break工大ACM团队iiiii@@81234567迷宫问题(续)0981234567812345679090栈(1,1)(2,1)(3,1)(4,1)(5,1)(5,2)向右方前进一步break工大ACM团队iiiiii@@迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(5,3)(5,2)break工大ACM团队iiiiiii@@81234567迷宫问题(续)0981234567812345679090向下方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)(5,2)(5,3)break工大ACM团队iiiiiii@@迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,4)(5,2)(5,3)(6,3)ibreak工大ACM团队iiiiiii@ii@迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,5)(5,2)(5,3)(6,3)(6,4)break工大ACM团队iiiiiii@iii@81234567迷宫问题(续)0981234567812345679090向下方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(7,5)(5,2)(5,3)(6,3)(6,4)(6,5)break工大ACM团队iiiiiii@iii@i迷宫问题(续)81234567812345679090向下方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(8,5)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)break工大ACM团队iiiiiii@iii@ii迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(8,6)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)break工大ACM团队iiiiiii@iii@iii迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(8,7)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)break工大ACM团队iiiiiii@iii@ii迷宫问题(续)81234567812345679090下方路不通，向右方前进一步，到达出口栈(1,1)(2,1)(3,1)(4,1)(5,1)(8,8)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)ii(8,7)break工大ACM团队iiiiiii@iii@iiii81234567迷宫问题(续)981234567090用栈保存了路径栈(1,1)(2,1)(3,1)(4,1)(5,1)(8,8)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)(8,7)工大ACM团队迷宫问题(最短路径)-BFS入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队11迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队1122迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队112233迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队11223434迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队11223453455迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队11262345345656迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队17126723453456576迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队17812678234534565786迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队1789126782345345657896迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队178912678234510310456105789610迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队1789126782345101131110114561011578961011迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队17891267812234510113111011124561011125789610121112迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队1789131267812234510113111011124561011121357896101312111213迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队1789131267812234510113111011124561011121357896101312111213迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队小结 广度和深度优先搜索有一个很大的缺陷,就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。

所以，在这里再次强调“剪枝”！剪枝：通过某种判断，避免一些不必要的遍历过程，形象的说剪去了搜索树中的某些“枝条”。工大ACM团队HDOJ_1010TempteroftheBone

ProblemDescriptionThedoggiefoundaboneinanancientmaze,whichfascinatedhimalot.However,whenhepickeditup,themazebegantoshake,andthedoggiecouldfeelthegroundsinking.Herealizedthatthebonewasatrap,andhetrieddesperatelytogetoutofthismaze.

ThemazewasarectanglewithsizesNbyM.Therewasadoorinthemaze.Atthebeginning,thedoorwasclosedanditwouldopenattheT-thsecondforashortperiodoftime(lessthan1second).ThereforethedoggiehadtoarriveatthedooronexactlytheT-thsecond.Ineverysecond,hecouldmoveoneblocktooneoftheupper,lower,leftandrightneighboringblocks.Onceheenteredablock,thegroundofthisblockwouldstarttosinkanddisappearinthenextsecond.Hecouldnotstayatoneblockformorethanonesecond,norcouldhemoveintoavisitedblock.Canthepoordoggiesurvive?Pleasehelphim工大ACM团队HDOJ_1010TempteroftheBone

InputTheinputconsistsofmultipletestcases.ThefirstlineofeachtestcasecontainsthreeintegersN,M,andT(1<N,M<7;0<T<50),whichdenotethesizesofthemazeandthetimeatwhichthedoorwillopen,respectively.ThenextNlinesgivethemazelayout,witheachlinecontainingMcharacters.Acharacterisoneofthefollowing:

'X':ablockofwall,whichthedoggiecannotenter;

'S':thestartpointofthedoggie;

'D':theDoor;or

'.':anemptyblock.

Theinputisterminatedwiththree0's.Thistestcaseisnottobeprocessed工大ACM团队HDOJ_1010TempteroftheBone

OutputForeachtestcase,printinoneline"YES"ifthedoggiecansurvive,or"NO"otherwise.工大ACM团队HDOJ_1010TempteroftheBone

SampleInput445S.X...X...XD....345S.X...X....D000工大ACM团队HDOJ_1010TempteroftheBone

SampleOutputNOYES工大ACM团队要点分析：典型的迷宫搜索，做出该题将具有里程碑式的意义！能不能枚举出所有抵达方案，再在通过检查时间时间是否吻合，得到结果，用DFS进行搜索。DFS搜索完成后，发现超时，得剪枝才行。工大ACM团队想到了什么剪枝条件？每个block只能走一次要求恰好某个给定的时间到达出口如果可走的block的总数小于时间，将会产生什么情况？还想到什么剪枝？工大ACM团队奇偶性剪枝可以把map看成这样：010101101010010101101010010101从为0的格子走一步，必然走向为1的格子从为1的格子走一步，必然走向为0的格子即：

0->1或1->0必然是奇数步

0->0走1->1必然是偶数步所以当遇到从0走向0但是要求时间是奇数的，或者，从1走向0但是要求时间是偶数的都可以直接判断不可达！结论：工大ACM团队奇偶性剪枝那么设所在位置(x,y)与目标位置(dx,dy)如果abs(dx-x)+abs(dy-y)为偶数，则说明abs(dx-x)+和abs(dy-y)的奇偶性相同，需要走偶数步如果abs(dx-x)+abs(dy-y)为奇数，那么说明abs(dx-x)和abs(dy-y)的奇偶性不同，需要走奇数步解为abs(dx-sx)+abs(dy-sy)的奇偶性就确定了所需要的步数的奇偶性！！而(ti-setp)表示剩下还需要走的步数，由于题目要求要在ti时恰好到达，那么(ti-step)与abs(x-y)+abs(dx-dy)的奇偶性必须相同因此temp=ti-step-abs(dx-x)-abs(dy-y)必然为偶数！工大ACM团队核心代码voidDfsSerch(int

x,int

y,intstep){

inttemp;temp=ti-step-