回溯法与深度优先搜索（DFS）_回溯和深度优先搜索

一、回溯法与深度优先搜索的关系

  回溯搜索是深度优先搜索（DFS）的一种，回溯法通俗的将其采用的思想是“一直向下走，走不通就掉头”，类似于树的先序遍历。dfs和回溯法其主要的区别是：回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。
  为了减少存储空间，在深度优先搜索中，用标志的方法记录访问过的状态，这种处理方法使得深度优先搜索法与回溯法没什么区别了。
由于回溯法花费时间较长，所以对于没有明确的动态规划（DP）和递归解法的或问题要求满足某种性质（约束条件）的所有解或最优解时，才考虑使用回溯法。

  我们一般在求解八皇后问题的时候说使用的是回溯法，本质也是深搜。在求解有关树和图的问题时，习惯说成深度优先搜索。这里所说的回溯和深搜都是不做任何优化的方式实现，在全局解空间上寻找最优解，所花费的时间比较长，仅使用于数据规模较小的问题。

二、具体应用

  以2019蓝桥杯C/C++B组的两个题目为例，来进行说明回溯和深搜的应用和局限。

1、组队（回溯法）

作为篮球队教练，你需要从以下名单中选出 1 号位至 5 号位各一名球员，
组成球队的首发阵容。
每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1
号位至 5 号位的评分之和最大可能是多少？

C++递归：

#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;

int a[20][6] = {{1,97,90,0,0,0},
				{2,92,85,96,0,0},
				{3,0,0,0,0,93},
				{4,0,0,0,80,86},
				{5,89,83,97,0,0},
				{6,82,86,0,0,0},
				{7,0,0,0,87,90},
				{8,0,97,96,0,0},
				{9,0,0,89,0,0},
				{10,95,99,0,0,0},
				{11,0,0,96,97,0},
				{12,0,0,0,93,98},
				{13,94,91,0,0,0},
				{14,0,83,87,0,0},
				{15,0,0,98,97,98},
				{16,0,0,0,93,86},
				{17,98,83,99,98,81},
				{18,93,87,92,96,98},
				{19,0,0,0,89,92},
				{20,0,99,96,95,81}};
int vis[20]; //20个队员是否被访问过
int max_score = 0;

//index表明了递归的深度，也表明是哪个位置，sum是当前情况的总分
void DFS(int index, int sum)
{
	if(index == 6) //已经选了5个人，这是后可以记分了
	{
		max_score = max(max_score, sum);
		return;
	}
	for(int i=0; i<20; i++) //对于每一个队员，每一个位置都尝试一下
	{
		if(vis[i] == 0) //只有这个队员没有被安排的时候才访问它
		{
			vis[i] = 1;
			DFS(index+1, sum+a[i][index]); //此时将该队员的该位置的得分和已选择了的做比较
			vis[i] = 0; //重新尝试下一种情况
		}
	}
}

int main()
{
    DFS(1,0);
    cout<<max_score;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

我们可以分析一下，回溯的顺序

  首先1,2,3,4分别占据1,2,3,4位置，5号位置就可以依次让5-20占据；然后4号位给5号的话，又是一种新的情况，5号位可以依次给6-20号位占据；依次这样搜索，每个人都可以换个位置。
  其实就是一个排列组合问题，在20个人中选择五个人，依次排列，就是多种结果。所以本题的解空间规模就是2019181716=1,860,480，可以在较短时间内完成。

2、迷宫问题（深度优先搜索）
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可
以通行的地方。
010000
000100
001001
110000

迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这
个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，
一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。
对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，
其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中D<L<R<U。

  我们可以想象，在迷宫问题中，问题的解规模与迷宫的中有效路径成正比，在30行50列的迷宫之中，有效路径可以是特别特别多，还要求最短路径，那时间上伤不起。仅适用于找出一个可行解。

C++非递归：

#include<iostream>
#include<stack>
#include<algorithm>

using namespace std;

int maze[4][6] = {{0,1,0,0,0,0},
                  {0,0,0,1,0,0},
                  {0,0,1,0,0,1},
                  {1,1,0,0,0,0}};

struct node
{
	int x;
	int y;
	int dir;
};

int dir[][2] = {{-1,0},{0,1},{1,0},{0,-1}}; //控制上右下左方向

int main()
{
	stack<node* > sk;
	node* nd = new node();
	nd->x = 0;
	nd->y = 0;
	nd->dir = -1; //-1默认是还没有进行方向选择
	maze[0][0] = 1;
	sk.push(nd);
	while(!(sk.top()->x == 3 && sk.top()->y == 5))
	{
		nd = sk.top();
		if(nd->dir == 3)
		{
			maze[nd->x][nd->y] = 0;
			sk.pop();
			delete nd;
			continue;
		}
		for(int i= nd->dir; i<4;i++)  //根据栈顶结点的方向选择
		{
			int x = nd->x + dir[i][0];
			int y = nd->y + dir[i][1];
			if(x>=0 && x<=3 && y>=0 && y<=5 && maze[x][y] == 0) //没有越界才入栈
			{
				nd->dir = i;
				node* nd2 = new node();
				nd2->x = x;
				nd2->y = y;
				nd2->dir = -1;
				sk.push(nd2);
				maze[x][y] = 1;
				break;
			}
		}
	}

	string result = "";
	char dir_c[] = {'U','R', 'D', 'L'};
	sk.pop(); //去除最后一个点，因为其还没有下一步
	while(!sk.empty())
	{
		nd = sk.top();
		sk.pop();
		result += dir_c[nd->dir];
	}

	reverse(result.begin(),result.end());
	cout<<result;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71