C++算法——回溯

回溯算法

实现思想

先看一个实例：

//暴力枚举的算法
int n = 5;
for (int a = 1; i <= n; i++)
{for (int b = 1; b <= n; b++){for (int c = 1; c <= n; c++){for (int d = 1; d <= n; d++){for (int e = 1; e <= n; e++){//判断 abcde 是否互补相同if (a != b && a != c && a != d && a != e && b != c && b != d && b != e && c != d && c != e && d != e){//输出一下cout << a << " " << b << " " << c << " " << d << " " << e << endl;}}}}}
}

这段代码应该很好理解
就是利用暴力枚举的方法来实现对1-5的全排列
我们可以加上数组的判断，这样就形成了回溯

//暴力枚举的算法
int n = 5;
bool mark[10];
for (int a = 1; i <= n; i++)
{mark[i] = true;for (int b = 1; b <= n; b++) if(!mark[b]){mark[b] = true;for (int c = 1; c <= n; c++) if(!mark[c]){mark[c] = true;for (int d = 1; d <= n; d++) if(!mark[d]){mark[d] = true;for (int e = 1; e <= n; e++) if(!mark[e]){cout << a << " " << b << " " << c << " " << d << " " << e << endl;}mark[d] = false;//回溯来了}mark[c] = false;//回溯来了}mark[b] = false;//回溯来了}mark[a] = false;//回溯来了
}

但是这道题如果这样写思路就太狭小了，我们可以合理利用递归来实现这种回溯

#include <bits/stdc++.h>
using namespace std;
int n, a[10000], mark[10000];
void dfs(int dep)
{if (dep == n + 1){for (int i = 0; i < n; i++){cout << a[i];}cout << "\n";return;}for (int i = 1; i <= n; i++){if (!mark[i]){mark[i] = 1;a[dep] = i;dfs(dep + 1);mark[i] = 0;//回溯来了[Doge不怀好意]}}
}
int main()
{cin >> n;dfs(1);return 0;
}

思路也很好想
dep其实就是枚举的第i层

只不过这种写法可以控制枚举的层数(没学过递归的时间复杂度估算，不知道这样写时间复杂度会不会增加，求大佬点评)

可爱(╹▽╹)的总结

我们可以发现
回溯的思路起始就是 回溯 这两个字本身的意思

所以我们就可以得出结论：
综合的代码：

mark[i] = 1;//我方发送核弹一枚
dfs(dep + 1);//发送中
mark[i] = 0;//撤回发送

大概得意思就是上面的注释（抽象了壹点，但是意思确实是如此）

思路就是反复的尝试，直到尝试出来正确的