DFS基础与回溯

标签：dep -- 基础 DFS int B1 B2 回溯 C2

回溯法简介

回溯法一般使用DFS（深度优先搜索(递归)）实现，DFS是一种遍历或搜索图，树或图像等数据结构的算法。上述数据结构不保存下来就是回溯法。
常见的是搜索树，排列型搜索树（节点数一般为n!）与子集型搜索树（节点数一般为2ⁿ）。

DFS从起始点开始，沿着一条路尽可能深入，直到无法继续回溯到上一节点为止，继续搜索，直到遍历完整个树或图。DFS使用栈与递归管理节点，一般使用递归。

排列树

graph TB A((A)) B1((B1)) C1((C1)) B2((B2)) C2((C2)) A-->B1 A-->B2 B1-->C1 B2-->C2

子集树

graph TB A((A)) B1((B1)) C1((C1)) C2((C2)) B2((B2)) D1((D1)) D2((D2)) A-->B1 A-->B2 B1-->C1 B1-->C2 B2-->D1 B2-->D2

2ⁿ(n=2)即4种方案。

回溯法模板

graph TB A((1)) B1((2)) C1((3)) B2((3)) C2((2)) A-->B1 A-->B2 B1-->C1 B2-->C2 D[图例为1~3的全排列，后略] D

//求1~n的全排列
int a[N];
bool vis[N];//表示数字i（或某个元素）是否使用过

void dfs(int dep) {

    //当dep深度等于n+1时说明n层都已经算完了，直接输出结果
    if (dep == n + 1) {
        for (int i = 1; i <= n; i++)cout << a[i] << ' ';
        cout << '\n';
        return;
    }
	//以上为递归出口

	//向下搜索，枚举范围
    for (int i = 1; i <= n; i++) {
        //排除不合法路径，如果i使用过了了就不能用了
        if (vis[i])continue;

        //修改状态，我们选上了，i现在已经被我们用了
        vis[i] = true;
        a[dep] = i;

        //向下一层递归，形成一个搜索树
        dfs(dep + 1);

        //恢复现场，只有恢复了现场我们才能不受干扰地向下一个分支进行递归
        vis[i] = false;
    }
}

例题

N皇后问题

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 15;
int n, ans;

int vis[N][N];//表示被多少个皇后占用了，等于0表示可以放皇后

void dfs(int dep) {
	if (dep == n + 1) {
		ans++;
		return;//递归出口
	}

	//遍历棋盘上的这一层
	for (int i = 1; i <= n; i++) {
		if (vis[dep][i])continue;//不为0，这个位置不能放，找下一个位置

		//修改状态
		for (int _i = 1; _i <= n; ++_i)vis[_i][i]++;//列加1，因为我们是一行行枚举的，所以行可以不用加1
		//四个方向的米字，_i是横轴，_j是纵轴
		for (int _i = dep, _j = i; _i >= 1 && _j >= 1; --_i, --_j)vis[_i][_j]++;
		for (int _i = dep, _j = i; _i <= n && _j >= 1; ++_i, --_j)vis[_i][_j]++;
		for (int _i = dep, _j = i; _i >= 1 && _j <= n; --_i, ++_j)vis[_i][_j]++;
		for (int _i = dep, _j = i; _i <= n && _j <= n; ++_i, ++_j)vis[_i][_j]++;

		dfs(dep + 1);//向下一层递归，一直递归到递归出口，答案加一，退出递归，准备恢复现场（会形成一个树形结构）

		//恢复现场，准备下一次搜索
		for (int _i = 1; _i <= n; ++_i)vis[_i][i]--;
		for (int _i = dep, _j = i; _i >= 1 && _j >= 1; --_i, --_j)vis[_i][_j]--;
		for (int _i = dep, _j = i; _i <= n && _j >= 1; ++_i, --_j)vis[_i][_j]--;
		for (int _i = dep, _j = i; _i >= 1 && _j <= n; --_i, ++_j)vis[_i][_j]--;
		for (int _i = dep, _j = i; _i <= n && _j <= n; ++_i, ++_j)vis[_i][_j]--;
	}
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//每一层必定只有一个皇后，可通过枚举每一层皇后的位置来搜索所有可能解
	//层数到n+1时表示找到了一个可行解，不可行的解都到不了n+1层

	cin >> n;
	dfs(1);
	cout << ans << '\n';
	return 0;
}

标签：dep,--,基础,DFS,int,B1,B2,回溯,C2
From： https://www.cnblogs.com/breadcheese/p/18014803