递归法、回溯法、深度优先搜索算法（DFS）_dfs和 回溯 递归

分治法通常通过递归的手段来解决。
递归法需要关注两个问题：
①递归边界
②递归式
我们以全排列和N皇后问题来理解递归法。

回溯法和递归法区别：
一般来说，如果在到达递归边界前的某层，由于一些事实导致已经不需要任何一个子问题递归，就可以直接返回上一层。则称该种做法为回溯法。

回溯法和深度优先搜索算法异同：
相同点：回溯法在实现上也是遵循深度优先的，即一步一步往前探索。
不同点：
①深度优先遍历，目的是“遍历”，本质是无序的；回溯法，目的是“求解过程”，本质是有序的，也就是说必须每一步都是要求的次序。
②深度优先遍历，已经访问过的节点不再访问，所有点仅访问一次；回溯法，已经访问过的点可能再次访问，也可能存在没有被访问过的点。

以递归法实现全排列，代码如下：

//全排列，n=3时 
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 11;
//P为当前排列，hashTable记录整数x是否已经在P中
int n,P[maxn] = {false};
//当前处理排列的第index号位
void generateP(int index) 
{
	if(index == n+1)//递归边界，已经处理完排列的1~n位
	{
		for(int i=1;i<=n;i++)
		{
			printf("%d",P[i]);
		}
		printf("\n");
		return;
	}
	for(int x=1;x<=n;x++)
	{
		if(hashTable[x] == false)
		{
			P[index] = x;
			hashTable[x] = true;
			generateP(index+1);
			hashTable[x] = false;//已处理完P[index]为x的子问题，还原状态 
		}
	}
} 

int main()
{
	n=3;
	generateP(1);
	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

N皇后问题，当采用暴力求解时，代码如下：
基本思想：全组合考虑去除同行同列的情况，转化为全排列，然后判断合法性。

int count = 0;
void generatrP(int index)
{
	if(index == n+1)//递归边界，生成一个排列 
	{
		bool flag = true;//flag为true表示当前排列为一个合法方案
		for(int i=1;i<=n;i++)//任意遍历两个皇后
		for(int j=i+1;j<=n;j++)
		{
			if(abs(i-j) == abs(P[i]-P[j]))//两个皇后所在位置的行坐标之差，列坐标之差的绝对值，若相等，在说明两个皇后在同一条对角线上。
			{
				flag = false;
		    } 
		}
	}	
	if(flag)
		count++;
	return; 
} 
for(int x=1;x<=n;x++)
{
	if(hashTable[x] == false)
	{
		P[index] = x;
		hashTable[x] = true;
		generateP(index+1);
		hashTable[x] = false;
	}
}
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

N皇后问题，当采用回溯法求解时，代码如下：

void generateP(int index)
{
	if(index == n+1)
	{
		count++;
		return; 
	}
	for(int x=1;x<=n;x++)//第x行
	{
		if(hashTable[x] == false)//第x行还没有皇后
		{
			bool flag = true;//flag为true表示当前皇后不会和之前的皇后冲突
			for(int pre = 1;pre<index;pre++)//遍历之前的皇后 
			{//第index列皇后的行号为x，第pre列皇后的行号为P[pre] 
				if(abs(index - pre) == abs(x - P[pre]))
				{
					flag = false;//与之前的皇后在一条对角线，冲突
					break; 
				}
			}	
			if(flag)//如果可以把皇后放在第x行
			{
				P[index] = x;//令第index列皇后的行号为x
				hashTable[x] = true;//第x行已被占用
				generateP(index + 1);//递归处理第index+1行皇后
				hashTable[x] = false;//递归完毕，还原第x行为未占用 
			} 
		}	
	} 
}
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

附上个人觉得特别不错的N皇后问题的代码：

#include <stdio.h>
#include <stdlib.h>
#define max 4

int queen[max], sum = 0; //max为棋盘最大坐标

//此处输出的坐标，其实是每个行坐标对应下的列坐标
void show() // 输出所有皇后的坐标,i代表行数，queen[i]代表当前行元素所处的列数
{
    printf("(");
    for (int i = 0; i < max; i++)
    {
        printf(" %d", queen[i] + 1); //注意此处下标是从0开始的，故列坐标需要+1
    }
    printf(")\n");
    sum++; //符合条件的总个数
}

//此函数用于判断当前皇后是否可以放在此位置
int PLACE(int n) //检查当前列能否放置皇后
{
    //queen[i] == queen[n]用于保证元素不能再同一列
    //abs(queen[i] - queen[n]) == abs(n - i)用于约束元素不能再同一行且不能再同一条斜线上
    for (int i = 0; i < n; i++)
    {
        if (queen[i] == queen[n] || abs(queen[i] - queen[n]) == abs(n - i))
        {
            return 0;
        }
    }
    return 1;
}

//回溯法的思想
void NQUEENS(int n) //回溯尝试皇后位置,n为横坐标，同时，n+1也代表皇后的序数
{
    for (int i = 0; i < max; i++)
    {
        //第一次将皇后放在第0行0列的位置（将皇后放在第0列的位置），对于第一次来说是成立的
        queen[n] = i;
        if (PLACE(n))
        {
            if (n == max - 1)
            {
                show(); // 如果全部摆好，则输出所有皇后的坐标 
            }
            else
            {
                NQUEENS(n + 1); // 否则继续摆放下一个皇后 
            }
        }
    }
}

int main()
{
    NQUEENS(0); // 从横坐标为0开始依次尝试，同时，0也代表第一个皇后
    printf("\n");
    printf("总共的解法有%d种\n", sum);

    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
56
57
58
59
60
61
62

运行结果如下：

一个典型的通用的 DFS 模板如下所示：

const visited = {}
function dfs(i) {
    if (满足特定条件）{
        // 返回结果 or 退出搜索空间
    }

    visited[i] = true // 将当前状态标为已搜索
    for (根据i能到达的下个状态j) {
        if (!visited[j]) { // 如果状态j没有被搜索过
            dfs(j)
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13