Algorithm 版 (精华区)

发信人: GREnTOFEL (Crazy Plucking), 信区: Algorithm
标  题: 搜索算法之深度优先搜索(转载)
发信站: 哈工大紫丁香 (2002年07月06日21:52:13 星期六), 站内信件

【 以下文字转载自 Programming 讨论区 】
【 原文由 zjliu 所发表 】
发信人: violinist (巷战狙击手), 信区: Algorithm
标  题: 搜索算法之深度优先搜索
发信站: 日月光华 (Fri Jul  5 08:30:24 2002)

搜索算法之深度优先搜索
[算法分析]
     编程学到现在才真正到了戏肉部分，从这里往下学，你才知道什么叫做博大精深。今

天我们要啃的这块硬骨头叫做深度优先搜索法。
    首先我们来想象一只老鼠，在一座不见天日的迷宫内，老鼠在入口处进去，要从出 口

出来。那老鼠会怎么走？当然是这样的：老鼠如果遇到直路，就一直往前走，如果遇到分

叉路口，就任意选 择其中的一个继续往下走，如果遇到死胡同，就退回到最近的一个分叉

路口，选择另一条道路再走下去，如果 遇到了出口，老鼠的旅途就算结束了。深度优先搜

索法的基本原则就是这样：按照某种条件往前试探搜索，如 果前进中遭到失败（正如老鼠

遇到死胡同）则退回头另选通路继续搜索，直到找到条件的目标为止。
    实现这一算法，我们要用到编程的另一大利器--递归。递归是一个很抽象的概念， 但

是在日常生活中，我们还是能够看到的。拿两面镜子来，把他们面对着面，你会看到什么

？你会看到镜子中 有无数个镜子？怎么回事？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格的棋盘，在棋盘的第一行的任意位置安放一只皇后。紧接

着，我们就来放 第二行，第二行的安放就要受一些限制了，因为与第一行的皇后在同一竖

行或同一对角线的位置上是不能安放 皇后的，接下来是第三行，……，或许我们会遇到这

种情况，在摆到某一行的时候，无论皇后摆放在什么位 置，她都会被其他行的皇后吃掉，

这说明什么呢？这说明，我们前面的摆放是失败的，也就是说，按照前面 的皇后的摆放方

法，我们不可能得到正确的解。那这时怎么办？改啊，我们回到上一行，把原先我们摆好

的 皇后换另外一个位置，接着再回过头摆这一行，如果这样还不行或者上一行的皇后只有

一个位置可放，那怎 么办？我们回到上一行的上一行，这和老鼠碰了壁就回头是一个意思

。就这样的不断的尝试，修正，尝试修 正，我们最终会得到正确的结论的。

[参考程序]
program queen;{8皇后问题参考程序}
const n=8;
var a,b:array [1..n] of integer;{数组a存放解：a[i]表示第i个皇后放在第a[i]列；}


    c:array [1-n,n-1] of integer;
    d:array [2..n+n] of integer;{数组b，c，d表示棋盘的当前情况：b[k]为1表示第k

行已被占领为0表示为空；c、d表示对角线}
    k:integer;
procedure print;{打印结果}
var j:integer;
begin
          for j:=1 to n do write(a[j]:4);
          writeln;
end;
procedrue try(i:integer); {递归搜索解}
var j:integer;{每个皇后的可放置位置。注意：一定要在过程中定义；否则当递归时会覆

盖掉它的值，不能得到正确结果}
begin
     for j:=1 to n do
     begin
          if (b[j]=0) and (c[i-j]=0) and   (d[i+j]=0) then{检查位置是否合法}

          begin
               a[i]:=j;{置第i个皇后的位置是第j行}
               b[j]:=1;{宣布占领行、对角线}
               c[i-j]:=1;
               d[i+j]:=1;
               if i<n then try(i+1)  else print;{如果末达目标则放置下一皇后，否

则打印结果}
               b[j]:=0;{清空被占行、对角线，回溯}
               c[i-j]:=0;
               d[i+j]:=0;
          end;
     end;
end;
begin
          for k:=1 to n do b[k]:=0;{初始化数据}
          for k:=1-n to n-1 do c[k]:=0;
          for k:=2 to n+n do d[k]:=0;
          try(1);
end.

[习题]
1、完成上述老鼠走迷宫问题。



--

※ 来源:．日月光华 http://bbs.fudan.edu.cn [FROM: 10.11.12.201]




--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 202.118.229.86]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: 202.118.229.154]