深度搜索算法(DFS)

转载自Hello, it works!

深度优先搜索

深度优先搜索算法(Depth First Search),是图论中的经典算法。
深度优先搜索算法是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当结点所有子结点那一层都被搜索过,再回溯返回到当前结点的邻结点,继续搜索,直到遍历完整棵树。一般采用的是前序遍历,先根然后再左右结点的方式进行。
一些经典的问题,比如八皇后、马走日、迷宫等,都可以通过深度优先搜索算法来解决。
为了方便描述,下文用DFS来做为深度优先搜索算法的简称。

我对DFS的认识

对于DFS,我相信很多人第一次接触很难设计出相应的算法,即便是有不错的编程经验。我第一次几乎没办法设计出解决八皇后的算法,即便是想了很久。最后没办法只好参照别人写的递归式的DFS。之后,虽然对这个算法有一点了解,但由于了解不够深度,过了几天就记不得了,下次又完全不知道怎么入手。然后需要再到网上搜下代码,看一遍后大概才双知道。而且发现每次写代码的时候心里总觉得不踏实,一开始总有错误的地方,并且每次写的代码都有些不同。总之,写过很多次后,依然是停留到了解的阶段,没办法进一步提升,特别是非递归式的DFS一直都停留到靠脑力记忆而不是理解的阶段。

今天周末有点时间,觉得有必要解决这些问题,试着花时间去归纳总结DFS的本质,看能否做到一劳永逸。
我设定的目标是:

  1. 不仅停留到理解阶段,而是要知道这个算法每一步的实现
  2. 捉住其中的本质,给出这个算法的设计框架。
  3. 在1与2的基础中,可以熟练写出递归与非递归两种实现方式 。

经过一个下午的研究,我发现任何DFS只需要通过下面几步就可以实现,无论是递归还是非递归方式。我给这几步分别做了一个命名,分别是find、forward、done、back。
如下:

  1. find(right):在树的当前层,横向遍历,尝试找到ok的节点。(这一步通常被叫做剪枝,只留下ok的。)
  2. forward(down):若在当前层找到ok的结点,并且当前层不是最后一层:把ok的节点放到当前层;进入下一层第一个结点。跳到find
  3. done(right):若在当前层找到ok的结点,并且当前层是最后一层:打印出结果;进入当前层的下一个结点。跳到find
  4. back(up):在当前层没有找到ok的节点:返回上一层当前结点的下一个兄弟节点。跳到find。

其实最重要的是find。然后后面的forward、done、back只是用来控制搜索走向。这四步可以进一步总结成两步。
为了了解算法,我想最好的切入方式是从一些实例开始。下面分别从八皇后以及马走日等问题做为切入点来分析DFS

问题举例

用DFS解八皇后

1、问题描述
八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?
也就是说,使得棋盘中每个横向、纵向、左上至右下斜向、右上至左下斜向均只有一枚皇后。
八皇后有92组解,下面给出其中一种解的图例:

2、 问题分析

规则是每一个皇后与前面的所有皇后不能在同一行、同一列、同一对角线。我们可以从第0行,第0列开始摆放,然后按照深度优先的原则,按照规则往更下面的行摆放皇后,直到摆放完8行。因为解不只一个,当某一行(包括最后一行跟最后一行之前的所有行)的所有列都被尝试过,再回溯返回到上一行,继续深度优先,直到遍历完整个棋盘的所有情况。得出所有的解。
八皇后问题可以看成是在深度为8的8叉树中,找出所有的解。

3、代码实现

递归算法:

#include <stdio.h>
#include <math.h>
 
/*八皇后问题是在8*8的棋盘上放置8枚皇后,使得棋盘中每个横向、纵向、左上至右下斜向、右上至左下斜向均只有一枚皇后。
求解出所有摆法,一共有92种摆法*/
 
const int N = 8; //棋盘行数
int a[N] = {0}; //表示棋盘,若a[2]=2,则表示在第3行第2列放一个皇后,因为同一行不能放两个皇后,所以只需要1维数组就可以表示一个棋盘。
 
int solution = 0;//解的个数
 
//row行,col列, 是否可以摆皇后
bool IsOK(int row, int col)
{
    for (int i = 0; i < row; i++)
    {
        if (a[i] == col || (abs(a[i] - col) == row - i))
        {
            return false;
        }
    }
    return true;
}
 
void Display()
{
    printf("第%d种解:\n",++solution);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (a[i] == j)
            {
                printf("%d", i);
            }
            else
            {
                printf("#");
            }
        }
        printf("\n");
    }
 
    printf("-----------------\n");
}
 
void DSF(int row)
{
    for (int col = 0; col < N; col++)
    {
        //find
        if (IsOK(row, col))
        {
            a[row] = col;
            //forward
            if (row != N -1)
            {
                DSF(row + 1);
            }
            else
            {
                //done
                Display();
            }
            
        }
    }
    //back
}
 
int main()
{
    DSF(0);
    return 0;
}

非递归算法:

#include <stdio.h>
#include <math.h>
#include <stack>
using namespace std;
/*八皇后问题是在8*8的棋盘上放置8枚皇后,使得棋盘中每个横向、纵向、左上至右下斜向、右上至左下斜向均只有一枚皇后*/
 
const int N = 8; //棋盘行数
int a[N] = {0}; //表示棋盘,若a[2]=2,则表示在第3行第2列放一个皇后,因为同一行不能放两个皇后,所以只需要1维数组就可以表示一个棋盘。
 
int solution = 0;//解的个数
 
struct Node
{
    int row;
    int col;
};
 
//row行,col列, 是否可以摆皇后
bool IsOK(Node node)
{
    for (int i = 0; i < node.row; i++)
    {
        if (a[i] == node.col || (abs(a[i] - node.col) == node.row - i))
        {
            return false;
        }
    }
    return true;
}
 
//打印出所有解
void Print()
{
    printf("第%d种解:\n", ++solution);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (a[i] == j)
            {
                printf("%d", i);
            }
            else
            {
                printf("#");
            }
        }
        printf("\n");
    }
 
    printf("-----------------\n");
}
 
void DSF()
{
    Node node;
    stack stack;
    node.row = 0;
    node.col = 0;
    stack.push(node);
    while(stack.size() >= 1)
    {
        //--find
        node = stack.top();
        while (node.col < N && !IsOK(node))
        {
            node.col++;
        }
        if (node.col < N)
        {
            //--forward
            if (node.row < N-1)
            {
                //把ok的节点放到当前层
                a[node.row] = node.col;
                stack.pop();
                stack.push(node);
                
                //进入下一层的第一个节点
                node.row++;
                node.col = 0;
                stack.push(node);
            }
            else
            {
                //--done
                a[node.row] = node.col;
                Print();
                
                //进入当前层的下一个结点
                //node = stack.top();
                node.col++;
                stack.pop();
                stack.push(node);
            }
        }
        else
        {
            //--back
            stack.pop();
            
            if (stack.size() == 0)
            {
                return;
            }
            node = stack.top();
            node.col++;
            stack.pop();
            stack.push(node);
        }
    }
}
int main()
{
    DSF();
    return 0;
}

马走日

1、问题描述
在nn的棋盘中,马只能走"日"字。马从位置(0,0)出发,把棋盘的每一格都走一次且只走一次。找出所有路径。 55的棋盘上,有304种解。
下面是其中一种路径的图例:

2、问题分析
搜索过程是从(0,0)出发,按照深度优先的原则,从8个方向中尝试一个可以走的点,直到尝试过所有的方向,走完棋盘上的所有点,得出所有的解。
马走日问题可以看成是在层数为n*n的8叉树中,找出所有的解。

3、代码实现
同样的,也可以把上面的算法框架,套用于马走日的身上。
递归算法:

#include <stdio.h>
 
/*马走日*/
 
const int N = 5; //棋盘行数跟列数
int matrix[N][N] = {0}; //表示棋盘
int solution = 0;//解的个数
int count = 0; //第几步
int move[8][2]={{-1,-2},{-2,-1}, {-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};//八个方向
 
//在棋盘范围内,而且可放棋
bool IsOK(int x, int y)
{
    if(( x <= N-1 ) && (x >=0 )
        && (y <= N-1 ) && (y >=0 )
        && (matrix[x ][y ]==0 ))
    {
        return true;
    }
    else
    {
        return false;
    }
}
 
 
//打印出所有解
void Display()
{
    printf("第%d种解:\n",++solution);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            
            printf("%3d",matrix[i][j]);
        }
        printf("\n");
    }
    
    printf("-----------------\n");
}
void DFS(int x, int y)
{
    int nextX, nextY;
 
 
    for (int i = 0; i < 8; i++)
    {
        nextX = x + move[i][0];
        nextY = y + move[i][1];
        //--find
        if (IsOK(nextX, nextY))
        {
            
            if (count != N*N -1 )
            {
                //--forward
                count++;
                matrix[nextX][nextY] = count;
                
                DFS(nextX, nextY);
                matrix[nextX][nextY] = 0;
                count--;
            }
            else 
            {
                //--done
                Display();
            }
        }
    }
    //--back
}
 
int main()
{
    matrix[0][0] = 1;
    count = 1;
    DFS(0, 0);
    return 0;
}

非递归算法:

#include <stdio.h>
#include <stack>
using namespace std;
 
/*马走日*/
 
const int N = 5; //棋盘行数跟列数
int matrix[N][N] = {0}; //表示棋盘
int solution = 0;//解的个数
int count = 0; //第几步
int move[8][2]={{-1,-2},{-2,-1}, {-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};//八个方向
 
//注意find这一步当前层的的结点,结点的坐标不是x与y,而通过Node中的x与y与direction三者计算后得到当前层的结点
struct Node
{
    int x;
    int y;
    int direction;
};
 
//在棋盘范围内,而且可放棋
bool IsOk(Node node)
{
    int x, y;
    x = node.x + move[node.direction][0];
    y = node.y + move[node.direction][1];
    if(( x <= N-1 ) && (x >=0 )
        && (y <= N-1 ) && (y >=0 )
        && (matrix[x][y]==0 ))
    {
        return true;
    }
    else
    {
        return false;
    }
}
 
//打印
void Print()
{
    printf("第%d种解:\n",++solution);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            
            printf("%3d",matrix[i][j]);
        }
        printf("\n");
    }
    
    printf("-----------------\n");
}
 
 
void DFS()
{
    Node node;
    stack stack;
    int x, y;
    count = 1;
    node.x = 0;
    node.y = 0;
    node.direction = 0;
    matrix[0][0] = count++;
    stack.push(node);
    node.direction = 0;
    stack.push(node);
    
    while(stack.size() >= 2)
    {
        //--find
        node = stack.top();
        while (node.direction < 8 && !IsOk(node))
        {
            node.direction++;
        }
        if (node.direction < 8)
        {
            //--forward
            if (count < N * N)
            {
                //把ok的节点放到当前层
                stack.pop();
                stack.push(node);
                x = node.x + move[node.direction][0];
                y = node.y + move[node.direction][1];
                matrix[x][y] = count++;
                
                //进入下一层的第一个节点
                node.x = x;
                node.y = y;
                node.direction = 0;
                stack.push(node);
            }
            else
            {
                //--done
                //打印出结果;
                x = node.x + move[node.direction][0];
                y = node.y + move[node.direction][1];
                matrix[x][y] = count++;
                Print();
                //注意先清除当前结点的数据
                matrix[x][y] = 0;
                count--;
                //进入当前层的下一个结点;
                node.direction++;
                stack.pop();
                stack.push(node);
            }
        }
        else
        {
            //----back
            //返回上一层当前结点的下一个节点
            stack.pop();
            if (stack.size() == 1)
            {
                return;
            }
            node = stack.top();
            //注意先清除当前结点的数据
            x = node.x + move[node.direction][0];
            y = node.y + move[node.direction][1];
            matrix[x][y] = 0;
            count--;
            node.direction++;
            stack.pop();
            stack.push(node);
            
        }
    }
}
int main()
{
    DFS();
    return 0;
}

其他

DFS有更多的变种,但都可以通过上面所说的四个步骤云解决。未完,待续。。。。

代码:github/dfs

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 218,607评论 6 507
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,239评论 3 395
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 164,960评论 0 355
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,750评论 1 294
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,764评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,604评论 1 305
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,347评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,253评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,702评论 1 315
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,893评论 3 336
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,015评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,734评论 5 346
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,352评论 3 330
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,934评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,052评论 1 270
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,216评论 3 371
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,969评论 2 355

推荐阅读更多精彩内容

  • 原文链接:http://helloitworks.com/678.html?utm_source=tuicool&...
    难以置信的优雅阅读 2,121评论 0 1
  • 因为之前就复习完数据结构了,所以为了保持记忆,整理了一份复习纲要,复习的时候可以看着纲要想具体内容。 树 树的基本...
    牛富贵儿阅读 6,879评论 3 10
  • 课程介绍 先修课:概率统计,程序设计实习,集合论与图论 后续课:算法分析与设计,编译原理,操作系统,数据库概论,人...
    ShellyWhen阅读 2,290评论 0 3
  • 组长在催交作业了,我呢?在家里干的精疲力尽,看看时间再不写就来不及了,还是停下来先把作业交了吧! 上回,家里才整理...
    一棵樹阅读 384评论 0 0
  • 中国古代神话里有极多半人半兽的怪物,人面蛇身、虎身、马身甚至猪身。这中间有一种半人半鱼的,叫鱼妇,更是奇怪之极。 ...
    桃乐丝的孙悟空阅读 2,068评论 0 1