DFS实现回溯算法

在算法学习的过程中深度优先搜索DFS和回溯算法可以说是每个程序员都必须掌握的经典内容。它们像是一对孪生兄弟经常一起出现解决各种组合、排列、搜索类问题。今天我们就来深入探讨如何用DFS实现回溯算法。一.什么是DFS深度优先搜索Depth-First Search是一种用于遍历或搜索树或图的算法。它的核心思想是从一个节点出发沿着一条路径走到底如果无法继续前进就回退到上一个节点尝试另一条路径。你可以把它想象成走迷宫遇到岔路就先选一条一条路走到底走不通了再退回来换另一条。二.什么是回溯回溯的意思是我们在搜索的过程中有可能会做出很多决策在做决策的时候有一些情况是不会对全局有影响的而有些题目的决策是会影响到全局的情况的回溯算法本质上是一种试错的思想。它尝试分步解决问题当发现当前选择无法得到正确解时就取消上一步甚至多步选择回溯到之前的状态尝试其他可能性。三.经典样例1——全排列信息学奥赛一本通1199给定一个由不同的小写字母组成的字符串输出这个字符串的所有全排列。思路假设我们先考虑第一位因为要保证字典序最小从小到大去枚举。假设只有abc那么先考虑第一位放a后面放什么先不考虑这样字典序肯定是从小到大的因为每个字母我们都只能使用一次而且我们每次决策都会在全局标记某个字母已经被使用过了假设我们考虑某一位置选择了字母c如果cur后面的情况搜索完了我们会继续考虑这个位置去选择别的字母实际上当我们搜索完回到cur这个位置的时候选择字母c的决策已经被撤销掉了所以我们选择字母c产生的影响全局标记c已经被访问必须一起撤销掉全局标记c为未被访问。代码实现#includeiostream #includestring using namespace std; int n; string str; char ans[10]; int vis[10]; void dfs(int cur) { //当cur超过输入的字符串长度时停止递归并输出 if (cur n 1) { for (int i 1;i n;i) { cout ans[i]; } cout endl; return; } //遍历进行搜索 for (int i 0;i n;i) { //搜索未被标记的字母 if (vis[i] 0) { //找到时需要做的事 //将该字母加入答案中 //标记已访问 //递归寻找下一位字母 //递归结束后要撤销之前的决策即将其重新标记为未被访问 ans[cur] str[i]; vis[i] 1; dfs(cur 1); vis[i] 0; } } } int main() { cin str; n str.size(); dfs(1); return 0; }三.经典样例2——组合首先我们要明白组合和排列的区别排列是指从若干数字中有顺序的取出若干个数字组合是指从若干数字中一次性取出多少个数字比如{123}{231}因为顺序不同是两种排列但是如果不关注顺序因为组成数字都相同所以这是同一种组合信息学奥赛一本通1317排列与组合是常用的数学方法其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)我们可以简单地将n个元素理解为自然数12…n从中任取r个数。输出所有组合思路这题要我们求组合不能和上一题排列一样搜索假设当前在选择第i个元素是谁只需要保证i选择的位置一定在第i-1个数字之后即可代码实现#includeiostream using namespace std; int n, r; int ans[25]; int vis[25]; void dfs(int cur,int id) { //如果搜索完后就输出结果 if (cur r 1) { for (int i 1;i r;i) { cout ans[i]; } cout endl; return; } //遍历进行递归 for (int i id;i n;i) { //每次递归做的事 //将当前位上填充相应的数字 //递归进行下一位并且必须是下一位数字 //这样可以保证第i位选择的数字一定在第i-1位的数字之后 ans[cur] i; dfs(cur 1, i 1); } } int main() { cin n r; dfs(1, 1); return 0; }四.经典题目——路径之谜题目小明冒充X星球的骑士进入了一个奇怪的城堡。城堡地面是 n×n 个方格。骑士要从西北角左上角走到东南角右下角。移动规则可以横向或纵向移动不能斜着走每走到一个新方格就要向正北方和正西方各射一箭同一个方格只允许经过一次不必走完所有的方格城堡的西墙和北墙内各有 n 个靶子。题目会给出每个靶子上的箭的数目要求推断出骑士的行走路线。题目理解这题是蓝桥杯国赛中的一道经典回溯题目这道题的关键在于理解“射箭”的含义骑士每到达一个格子(x, y)x表示行y表示列就会向正北方射一箭 → 影响第 y 列北墙靶子同时向正西方射一箭 → 影响第 x 行西墙靶子换句话说北墙第 y 个靶子上的箭数 骑士访问过的所有列坐标为 y 的格子数量西墙第 x 个靶子上的箭数 骑士访问过的所有行坐标为 x 的格子数量最终所有靶子上的箭数必须刚好用完全部归零且骑士到达终点。思路我们可以使用回溯算法从入口开始尝试四个方向移动。每走一格就判断是否满足条件不能越界每个方格只允许经过一次每移动到一个新方格就记录下对箭靶的影响。如果移动到的方格是出口且箭靶上的箭数与给出的一致则找到了一条可行的路线否则就要回溯到上一步尝试其他方向对箭靶的影响需要恢复代码实现#includebits/stdc.h using namespace std; //方向数组 int dx[] { 1,-1,0,0 }; int dy[] { 0,0,1,-1 }; int n; int mp[15][15]; int a[15], b[15];//记录箭靶上箭的数量 int k1, k2;//记录一个方向上箭的总数 int vis[15][15];//判断是否到达过该点 int s[600];//记录最终路径 int num;//记录步数 bool flag false;//判断是否找到一条可行路径 void dfs(int x, int y, int cnt) { //判断是否越界 if (x1 || xn || y1 || yn) { return; } //判断是否已经找到一条路径 //或者当前路径是否已经无法继续走下去即箭靶上的箭已经为0 if (flag || a[y] 0 || b[x] 0) { return; } //记录路径 s[cnt] (x - 1) * n (y - 1); //判断是否到达终点 //注意因为我们是在后面的处理中才将箭的数量-1 //当我们到终点时这一步的两根箭还没减去 //所以应该还有一根箭才对 if (x n y nk11k21) { flag true; num cnt;//记录总步数 return; } //尝试四个方向 for (int i 0;i 4;i) { int nxtx x dx[i]; int nxty y dy[i]; if (vis[nxtx][nxty] 0) { //将相应的数据减去 a[nxty]--; b[nxtx]--; k1--; k2--; vis[nxtx][nxty] 1; dfs(nxtx, nxty, cnt 1); //回溯将相应的数据重新加上 a[nxty]; b[nxtx]; k1; k2; vis[nxtx][nxty] 0; } } } int main() { cin n; //记录西和北两个方向上的每个箭靶的箭数和箭的总数 for (int i 1;i n;i) { cin a[i]; k1 a[i]; } for (int i 1;i n;i) { cin b[i]; k2 b[i]; } //将起点两根箭减去并将起点标记为已到达 a[1]--; b[1]--; vis[1][1] 1; dfs(1, 1, 1); //输出结果数组 for (int i 1;i num;i) { cout s[i] ; } return 0; }五.常见回溯问题分类类型典型题目核心要点排列问题全排列、字符串排列顺序有关需要used数组组合问题组合总和、子集顺序无关通常用start参数分割问题分割回文串、IP地址复原在字符串上切分棋盘问题N皇后、解数独二维网格 合法性判断路径问题迷宫、单词搜索方向数组 边界判断六.复杂度分析时间复杂度通常为 O(选择数 ^ 深度) 级别但剪枝会大幅降低实际运行时间空间复杂度O(深度)主要是递归栈的开销以全排列为例时间复杂度 O(n × n!)空间复杂度 O(n)七.总结1.做选择 → 递归 → 撤销选择这是回溯的骨架2.剪枝思想能提前判断的不要等到最后3.撤销选择这一步最容易遗漏不要忘记