LaneBlog

蝼蚁虽小,也有梦想

PHP Socket服务 | PHP微信开发框架 | 开源博客

算法六:深度优先搜索

Clicks: 3980 Date: 2014-11-09 23:19:54 Power By 李轩Lane

    

    什么是深度优先搜索?理解深度优先搜索的关键在于解决“当前如何做”,至于“下一步如何做”和“当前如何做是一样的做法”。深度优先搜索是Depth First Search, DFS。基本模型如下:

void dfs(int step){

    边界判断

    循环遍历去尝试每一种可能for(int i=0; i<n; i++){

        继续下一步dfs(step + 1);

    }

}

    下面看一个实例。我们有三个数字,1,2,3.求这三个数字的所有可能的搭配。那么,答案就是123,132,213,231,312,321共6种。我给出的答案顺序,也是深度优先搜索的顺序。

    假设我们有1,2,3的三张牌,地上有编号为一、二、三的三个纸箱。我们每次都把手中最小的牌放到箱子里,然后走到下一个箱子。

    第一步:在一号箱子面前,放入最小的手牌1,然后前进一步。此时手牌是2和3。判断边界(手牌是否为空)。

    第二步:在二号箱子面前,放入最小的手牌2,然后前进一步。此时手牌是3。判断边界(手牌是否为空)。

    第三步:在三号箱子面前,放入最小的手牌3,然后前进一步,此时手牌是空。判断边界(手牌是否为空)。

    第四步:手牌为空,触发边界条件。遍历打印箱子中的数字,结果是123。

    第五步:取出三号箱子的牌,后退一步。此时手牌是3。

    第六步:取出二号箱子的牌,此时手牌是2和3,2已经放过了,所以放3,然后前进一步。此时手牌是2。判断边界(手牌是否为空)。

    第七步:在三号箱子面前,放入最小手牌2,然后前进一步,此时手牌是空。判断边界(手牌是否为空)。

    第八步:手牌为空,触发边界条件。遍历打印箱子中的数字,结果是132。

    第九步:取出三号箱子的牌,后退一步。此时手牌是2。

    第十步:取出二号箱子的牌,此时手牌是2和3,2和3都已经放过了,所以再退一部。此时手牌是2。判断边界(手牌是否为空)。

    第十一步:取出一号箱子的牌,此时手牌是1,2和3,1以及放过了,所以放剩下的最小手牌,就是2,然后前进一步,此时手牌是1,3。判断边界(手牌是否为空)。

    第十二步:在二号箱子面前,放入最小的手牌1,然后前进一步。此时手牌是3。判断边界(手牌是否为空)。

    第十三步:在三号箱子面前,放入最小的手牌3,然后前进一步,此时手牌是空。判断边界(手牌是否为空)。

    第十四步:手牌为空,触发边界条件。遍历打印箱子中的数字,结果是213。

    ………………………………………………………………………………

    恩,就是这样子,直接上代码了。C版本的深度优先遍历的模型。

    Ps:本实例和代码均来自《啊哈!算法》一书。不过上面的过程是我自己手打原创哦^_^

#include <stdio.h>

void dfs(int step);

int a[10], book[10], n;

int main(){

    //1-9的整数

    scanf("%d", &n);

    //从第一个箱子开始。直接从下标1开始。0不要了。

    dfs(1);

}

void dfs(int step){

    int i;

    //已经到最后一个箱子了。

    if(step == n+1){

        for(i=1; i<=n; i++){

            printf("%d", a[i]);

        }

        printf("\n");

    }

    //在第step个箱子面前,按照1,2,3...n的顺序一一尝试

    for(i=1; i<=n; i++){

        //等于0就是i还没有使用,还在手里。

        if(book[i] == 0){

            //使用i

            a[step] = i;

            //标记i已经使用

            book[i] = 1;

            //前进一步

            dfs(step + 1);

            //回收step箱子里的牌

            book[i] = 0;

        }

    }

}

©2014 www.lanecn.com , All rights reserved. Power By Li Xuan.  京ICP备14005030号