【数据结构与算法】—— * 深度优先搜索入门 *

简介: 【数据结构与算法】—— * 深度优先搜索入门 *

问题引入

输入一个数n,输出1~n的全排列


问题解析

假设有编号为1,2,3的3张扑克牌和编号为1,2,3的3个盒子。需要将这3张扑克牌分别放到3个盒子里面,并且每个盒子有且只能放一张扑克牌。问一共有多少种放法?

1.png

首先,我们按照正常的顺序来进行放置,顺序为——“1-2-3”

2.png然后我们走到了第四个盒子前,这时候已经没有扑克牌可以放置了,现在我们要重新回到3号盒子前,需要取回之前放在3号盒子里的扑克牌,再去尝试看看能不能放别的扑克牌,从而产生一个新的排列。于是我们取回3号扑克牌。

但这时候我们发现手中仍然只有3号扑克牌,没有别的选择,我们不得不回到2号盒子前收回2号扑克。现在我们手里有2张扑克牌,分别是2,3.按照之前约定的顺序(每次到一个盒子前,先放1号,再放2号,最后放3号)我们需要往2号盒子里面放3号扑克牌(上一次放的是2号扑克牌)。放好后来到三号盒子前,将手中仅剩的2号扑克牌放入3号盒子中,又来到了4号盒子面前(不存在),这时候产生了新的排列——“1.3.2”

3.png

按照这样的步骤去模拟,我们便会产生所有的排列

4.png


问题解决

最基本的问题:放入扑克牌

for(i = 1;i <= n;i++)
{
if(book[i] == 0)
    {
a[step] = i;    //book[i] 等于0表示第i号扑克还在手上
book[i] = 1;    //表明book[i]已经不在手上
    }
}

使用book数组来标记哪些数组已经使用了

将这串代码封装成一个函数,用同样的方式去处理step+1个盒子

voiddfs(intstep)   //step表示现在站在第几个盒子前面
{
  //处理第step个小盒子
for (i = 1; i <= n; i++)
  {
if (book[i] == 0)  //book[i] 等于0表示第i号扑克还在手上
    {
a[step] = i;  //将第i号扑克放入第step个盒子中
book[i] = 1;  //表明book[i]已经不在手上
    }
  }
return;
}

处理第step+1个小盒子的方法就是dfs(step+1)

voiddfs(intstep)   //step表示现在站在第几个盒子前面
{
  //处理第step个小盒子
for (i = 1; i <= n; i++)
  {
if (book[i] == 0)  //book[i] 等于0表示第i号扑克还在手上
    {
a[step] = i;  //将第i号扑克放入第step个盒子中
book[i] = 1;  //表明book[i]已经不在手上
dfs(step + 1);  //这里用函数递归的调用来实现(自己调用自己)
book[i] = 0;  //这是非常重要的一步,一定要将刚才尝试的扑克牌收回,才能进行下一步尝试
      //如果不把刚才放入小盒子的扑克牌收回,那将无法再进行下一步的摆放
      //当step = n + 1时,表明前n个盒子都已经放好扑克了
    }
  }
return;
}

上面代码中的 book[i] = 0 这条语句非常重要,这句话的作用是将小盒子中的扑克牌收回,因为在一次摆放尝试结束返回的时候,如果不把刚才放入小盒子中的扑克牌收回,那将无法进行下一次摆放。

当我们处理到第n+1个盒子的时候,证明我们前n个已经排序完毕,将他们打印出来即可。

打印完毕一定要return,否则会无休止地运行下去。

完整代码

//深度优先搜索
inta[10], book[10], n;
//C语言的全局变量在没有赋值以前默认为0//因此这里的book数组无需再全部赋值初始值0//将放牌封装成一个函数
voiddfs(intstep)   //step表示现在站在第几个盒子前面
{
inti;
if (step == n + 1)    //如果站在第n+1个盒子前,表明前n个盒子都已经完成了放置
  {
    //输出一种排列
for (i = 1; i <= n; i++)
printf("%d", a[i]); 
printf("\n");
return;   //返回之前最近的一步(最近一次调用dfs的地方)
    //打印完要立即return,否则会无限循环下去
  }
  //处理第step个小盒子
for (i = 1; i <= n; i++)
  {
if (book[i] == 0)  //book[i] 等于0表示第i号扑克还在手上
    {
a[step] = i;  //将第i号扑克放入第step个盒子中
book[i] = 1;  //表明book[i]已经不在手上
dfs(step + 1);  //这里用函数递归的调用来实现(自己调用自己)
book[i] = 0;  //这是非常重要的一步,一定要将刚才尝试的扑克牌收回,才能进行下一步尝试
      //如果不把刚才放入小盒子的扑克牌收回,那将无法再进行下一步的摆放
      //当step = n + 1时,表明前n个盒子都已经放好扑克了
    }
  }
return;
}
intmain()
{
scanf("%d", &n);  //输入时要注意为1-9之间的整数
dfs(1); //首先站在1号小盒面前
return0;
}

总结

深度优先搜索(Depth First Search,DFS)

理解深度优先搜索的关键在于解决“当下该如何做”。至于“下一步该如何做”,则与“当下该如何做”是一样的。

基本模型

voiddfs(intstep)
{
    判断边界
    尝试每一种可能
for(i = 1;i <= n;i++)
    {
    继续下一步的尝试 dfsstep+1    }
    返回
}

每一种尝试就是一种“扩展”。每次站在一个盒子前面的时候,都有n种扩展方法,但不是每一种方法都能够成功扩展。


这就是今天的全部内容啦,如果觉得有帮助,请

目录
相关文章
|
2月前
|
算法 测试技术 定位技术
数据结构与算法——DFS(深度优先搜索)
数据结构与算法——DFS(深度优先搜索)
|
3月前
|
机器学习/深度学习 人工智能 算法
深度学习入门:理解神经网络与反向传播算法
【9月更文挑战第20天】本文将深入浅出地介绍深度学习中的基石—神经网络,以及背后的魔法—反向传播算法。我们将通过直观的例子和简单的数学公式,带你领略这一技术的魅力。无论你是编程新手,还是有一定基础的开发者,这篇文章都将为你打开深度学习的大门,让你对神经网络的工作原理有一个清晰的认识。
|
2月前
|
机器学习/深度学习 算法
机器学习入门(三):K近邻算法原理 | KNN算法原理
机器学习入门(三):K近邻算法原理 | KNN算法原理
|
2月前
|
机器学习/深度学习 算法 大数据
机器学习入门:梯度下降算法(下)
机器学习入门:梯度下降算法(下)
|
2月前
|
机器学习/深度学习 算法 API
机器学习入门(五):KNN概述 | K 近邻算法 API,K值选择问题
机器学习入门(五):KNN概述 | K 近邻算法 API,K值选择问题
|
2月前
|
存储 机器学习/深度学习 算法
探索数据结构:入门及复杂度的解锁
探索数据结构:入门及复杂度的解锁
|
2月前
|
存储 缓存 应用服务中间件
Nginx入门 -- 基本数据结构中之ngx_hash_t
Nginx入门 -- 基本数据结构中之ngx_hash_t
36 0
|
2月前
|
存储 缓存 应用服务中间件
Nginx入门 -- 基本数据结构中之ngx_list_t,ngx_queue_t
Nginx入门 -- 基本数据结构中之ngx_list_t,ngx_queue_t
28 0
|
2月前
|
存储 应用服务中间件 nginx
Nginx入门 -- 基本数据结构中之ngx_str_t,ngx_array_t
Nginx入门 -- 基本数据结构中之ngx_str_t,ngx_array_t
71 0
|
2月前
|
机器学习/深度学习 算法
机器学习入门:梯度下降算法(上)
机器学习入门:梯度下降算法(上)