【蓝桥杯】【啊哈！算法】深度优先搜索——全排列

【啊哈！算法】系列文章目录

目录

• • 【啊哈！算法】系列文章目录
  • • 需求介绍
    • 思路分析
    • C语言代码
    • 总结

需求介绍

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

思路分析

为了便于理解, 我们首先以一个具体的例子来说明问题. 比如, 假设我们有三张分别标号为1. 2. 3的扑克牌和三个同样标号为1. 2. 3的盒子. 接下来的任务是将这三张不同的扑克牌分配到这三个不同的盒子里, 并且每个盒子里只能放一张扑克牌. 那么总共有多少种不同的放置方式呢?

现在轮到小哼上场了。小哼手中持有三张不同的扑克牌，在前往一号箱子之前内心在纠结：到底是先放下号的扑克还是二号的？又或者是三号的呢？为了生成所有可能的排列组合，则必须尝试这三种不同的放置顺序。随后小哼宣布了一个统一的规则：每次来到一个箱子面前时都按照固定的顺序放置——首先是放入一号卡片随后才是二号最后才放置三号卡片就这样坚持着这个方法继续前进最终将第一张号码卡准确地放入了第一个箱子中

完成放置后他转至2号盒子前继续观察情况。原本按照约定的步骤应依次按照1、2、3号牌的顺序将物品放入对应的盒子里。但当前由于手头仅剩余着2和3两张牌因此他决定优先将第几张牌放在对应的盒子里即先将第几张放到第二个盒子里随后再处理其他物品。放置完毕后他再次向第3个盒子走去准备进行下一步操作

小哼目前正站在3号盒子前。按照事先约定的顺序，在手上的第一张至第三张扑克牌中依次应放置第一张至第三张相应的卡片。然而实际上小哼只持有第三张手牌因此只能将这张手上的第三张扑克牌放入对应的盒子中。放置完毕后小哼向前移动了一步来到第四号盒子前令人意外的是这里并不存在第四个对应的存放位置因为手中的卡片已经全部放置完毕。

注意到小哼走进第四个盒子时，我们意识到这里形成了一个排列结构。这个排列顺序恰好对应了前三个盒子的扑克牌编号，即1、2、3依次递增的顺序。

是否到这里就算结束呢？ 当然不是！ 接着小哼必须立即离开这种顺序。 此时小哼应后退一步重返3号盒子之前。

现在小哼已经回到了3号盒子前，并想要取出存放于该盒中的扑克牌以便尝试放置其他扑克牌以产生新的排列顺序。然而当他想要放置其他扑克牌时却发现自己手中只剩下这一张3号扑克牌而无法继续操作因此不得不退回至2号盒子

小哼返回至盒子里后收集了那里的卡片——具体来说是编号为" "的那张" "卡片（上一次收集的是编号为" "的那张）。随后他审视了一下手头所拥有的这两张卡片——分别编号为" "和" "——并决定按照既定程序执行下一步操作：将编号为" "的这张卡片放置于当前所在位置对应的存储容器中（上一个操作则是将编号为" "的这张卡片放置于该位置对应的存储容器中）。完成动作后他转身向下一个目标移动——再次回到了第四个存储容器前准备进行下一步操作。

小哼又一次走进了3号储物箱，在其中放上了最后剩下的2号扑克牌。随后他将这个决定告诉了自己的朋友，并且让他们一起检查是否正确。接着他走向4号储物箱前，请问你们是否已经准备好接收更多的物品？

接下来按照刚才的步骤去模拟， 便会依次生成所有排列。

说了半天, 这样复杂的过程如何用程序实现呢? 我们首先聚焦于最基础的问题: 如何将扑克牌放入小盒子里. 每个小盒子都有三种可能的选择: 1号、2号或3号扑克牌. 这可以通过系统地尝试每一种可能性来实现. 具体来说, 在程序中使用一个循环结构即可完成这一过程

    for (i=1; i<=n; i++)
    {
    	a[step] = i;	//将i号扑克牌放入到第step个盒子中
    }

数组a被用来表示各个小盒子。变量step代表当前处于哪个小盒子前面。将i号元素放置于step号盒子里即可完成操作a[step]=i的过程。这里存在一个问题：如果一张牌已经被放置在其他的小盒子里，则无法将其放入当前的盒子里因为此时手头已经没有这张牌可用。因此还需要一个数组book来记录哪些牌已经被使用过了。

完成最后一个'box'步骤后, 下一步就是继续执行下一步操作, 即继续处理下一个即将开始的操作. 具体来说, 在执行下一个步骤时, 我们会采用a similar approach来解决这个问题, 即将这些代码逻辑提取出来并将其封装成一个辅助函数, 我们可以将这一功能实现为一个名为 dfs 的辅助函数, 如下所示:

在这个过程中完成函数封装后, 刚才遇到的问题就迎刃而解了。在完成了第step个小盒子的具体处理之后, 紧接着依次完成第step+1个小盒子的相关操作, 而针对第step+1个小盒子的具体方法就是调用dfs(step+1)函数。请注意代码中对此处操作进行了重点强调。

上面代码中的 book[i]=0 这条指令非常重要。这段代码的作用是将当前小盒子里的扑克牌收集起来，在每一次摆放尝试完成并返回时如果没有将刚放入小盒子里的扑克牌收集起来就无法继续后续的操作。还有一个问题就是什么时候应该输出一个满足条件的结果序列呢？实际上当我们处理到第 n+1 个小盒子的时候（也就是当 step 等于 n+1 的时候），说明前 n 个小盒子里都已经放好了正确的扑克牌序列了这个时候就可以打印出 1~n 个小盒子里的所有扑克牌编号就可以了。注意！打印完毕后一定要立即 return 否则程序就会陷入无限循环无法正常退出其中原因是什么呢？

C语言代码

    #include <stdio.h>
    
    int data[10] = {1,2,3,4,5};
    int a[10], book[10], n=5; //此处特别说明一下： C语言的全局变量在没有赋值以前默认为0, 因此这里的book数组无需全部再次赋初始值0
    
    void dfs(int step) {  //step表示现在站在第几个盒子面前
    	int i;
    	if(step==n) {
    		//输出一种排列(l~n号盒子中的扑克牌编号）
    		for(i=0;i<n;i++) {
    			printf("%d ",a[i]);
    		}
    		printf("\n");
    		return;  //返回之前的一步（最近一次调用dfs函数的地方）
    	}
    	
    	
    	//此时站在第step个盒子面前， 应该放那张牌呢？
    	//按照1 、2 、3... n的顺序一一尝试
    	for(i=0;i<n;i++) {
    		//判断扑克牌i是否还在手上
    		if(book[i]==0) {  //book[i]等于0表示i号扑克牌在手上
    			//开始尝试使用扑克牌i
    			a[step] = data[i];  //将i号扑克牌放入到第step个盒子中
    			book[i] = 1;  //将book[i]设为1， 表示i号扑克牌已经不在手上
    			
    			dfs(step+1);  //第step个盒子已经放好扑克牌， 接下来需要走到下一个盒子面前
    			book[i] = 0;  //这是非常重要的一步，一定要将刚才尝试的扑克牌收回， 才能进行下一次尝试
    		}
    	}
    	return;
    } 
    
    
    int main() {
    	dfs(0);
    	return 0;
    }

总结

以这个简单的例子为例，在编写代码的过程中发现核心代码量在20行以内就可以体现深度优先搜索的核心模型。为了深入理解深度优先搜索算法的关键在于掌握在当前状态下如何做出选择这一问题。同样需要根据当前状态做出相应的决策才能完成整个搜索过程。具体来说，在dfs(step)函数的主要逻辑中我们主要关注的是当你处在第step个盒子时你所面临的状态应该如何进行处理。通常采用for循环进行遍历操作之后将问题逐步分解为更小规模的子问题即通过调用dfs(step+1)来完成下一步骤的处理过程。这种递归式的思考方式使得整个算法的设计更加简洁明了同时也能更好地体现深度优先搜索的核心思想。

    void dfs(int step)
    {
    	判断边界
    	尝试每一种可能 for(i=0; i<n; i++)
    	{
    		继续下一步 dfs(step+1);
    	}
    	返回
    }

每一次尝试都相当于一次"拓展"。每当面对一个封闭的系统时, 其实都蕴含着n种可能的拓展路径, 但并非所有的拓展都能真正实现。