(转载)菜鸟拼杀ZOJ心得:[ZZ]递归深度优先搜索

    技术2022-05-11  30

    这面这篇文章,转自

    http://aaskywalker.spaces.live.com/blog/cns!AC69B568074FB91D!537.entry

    觉得挺不错的.刚好最近也在学习搜索算法.

    对于广度优先搜索,还是比较好理解的,对于深度的,我一直都不想去接触他,这篇文章确定写得很生动,转过来跟大家一起共享下,呵呵

    搜索算法之深度优先搜索 By  jjiahe 发表于 2006-8-2 9:11:44  [算法分析]编程学到现在才真正到了戏肉部分,从这里往下学,你才知道什么叫做博大精深。今天我们要啃的这块硬骨头叫做深度优先搜索法。首先我们来想象一只老鼠,在一座不见天日的迷宫内,老鼠在入口处进去,要从出 口出来。那老鼠会怎么走?当然是这样的:老鼠如果遇到直路,就一直往前走,如果遇到分叉路口,就任意选 择其中的一个继续往下走,如果遇到死胡同,就退回到最近的一个分叉路口,选择另一条道路再走下去,如果 遇到了出口,老鼠的旅途就算结束了。深度优先搜索法的基本原则就是这样:按照某种条件往前试探搜索,如 果前进中遭到失败(正如老鼠遇到死胡同)则退回头另选通路继续搜索,直到找到条件的目标为止。 实现这一算法,我们要用到编程的另一大利器--递归。递归是一个很抽象的概念, 但是在日常生活中,我们还是能够看到的。拿两面镜子来,把他们面对着面,你会看到什么?你会看到镜子中 有无数个镜子?怎么回事?A镜子中有B镜子的象,B镜子中有A镜子的象,A镜子的象就是A镜子本身的真实写 照,也就是说A镜子的象包括了A镜子,还有B镜子在A镜子中的象………………好累啊,又烦又绕口,还不好理 解。换成计算机语言就是A调用B,而B又调用A,这样间接的,A就调用了A本身,这实现了一个重复的功能。再 举一个例子;从前有座山,山里有座庙,庙里有个老和尚,老和尚在讲故事,讲什么呢?讲:从前有座山,山 里有座庙,庙里有个老和尚,老和尚在讲故事,讲什么呢?讲:从前有座山,山里有座庙,庙里有个老和尚, 老和尚在讲故事,讲什么呢?讲:…………。好家伙,这样讲到世界末日还讲不玩,老和尚讲的故事实际上就 是前面的故事情节,这样不断地调用程序本身,就形成了递归。 万一这个故事中的某一个老和尚看这个故事不 顺眼,就把他要讲的故事换成:“你有完没完啊!”,这样,整个故事也就嘎然而止了。我们编程就要注意这 一点,在适当的时候,就必须要有一个这样的和尚挺身而出,把整个故事给停下来,或者使他不再往深一层次 搜索,要不,我们的递归就会因计算机存储容量的限制而被迫溢出,切记,切记。我们把递归思想运用到上面的迷宫中,记老鼠现在所在的位置是(x,y),那它现在有 前后左右4个方向可以走,分别是(x+1,y),(x-1,y),(x,y+1),(x,y-1),其中一个方向是它来时的路,我们先不 考虑,我们就分别尝试其他三个方向,如果某个方向是路而不是墙的话,老鼠就向那个方向迈出一步。在新的 位置上,我们又可以重复前面的步骤。老鼠走到了死胡同又是怎么回事?就是除了来时的路,其他3个方向都是 墙,这时这条路就走到了尽头,无法再向深一层发展,我们就应该沿来时的路回去,尝试另外的方向。例:八皇后问题:在标准国际象棋的棋盘上(8*8格)准备放置8只皇后,我们知 道,国际象棋中皇后的威力是最大的,她既可以横走竖走,还可以斜着走,遇到挡在她前进路线上的敌人,她 就可以吃掉对手。要求在棋盘上安放8只皇后,使她们彼此互相都不能吃到对方,求皇后的放法。这是一道很经典的题目了,我们先要明确一下思路,如何运用深度优先搜索法,完 成这道题目。我们先建立一个8*8格的棋盘,在棋盘的第一行的任意位置安放一只皇后。紧接着,我们就来放 第二行,第二行的安放就要受一些限制了,因为与第一行的皇后在同一竖行或同一对角线的位置上是不能安放 皇后的,接下来是第三行,……,或许我们会遇到这种情况,在摆到某一行的时候,无论皇后摆放在什么位 置,她都会被其他行的皇后吃掉,这说明什么呢?这说明,我们前面的摆放是失败的,也就是说,按照前面 的皇后的摆放方法,我们不可能得到正确的解。那这时怎么办?改啊,我们回到上一行,把原先我们摆好的 皇后换另外一个位置,接着再回过头摆这一行,如果这样还不行或者上一行的皇后只有一个位置可放,那怎 么办?我们回到上一行的上一行,这和老鼠碰了壁就回头是一个意思。就这样的不断的尝试,修正,尝试修 正,我们最终会得到正确的结论的。  


    最新回复(0)