【八皇后】C++经典深度搜索题目（理解回溯）

八皇后可以说是非常经典的深搜题目，可以自行尝试一下
我们都知道八皇后无非就是检查+递归，实际上呢检查的过程就是回溯的过程。

普通版八皇后代码如下

#include 

using namespace std;
int col[15],n,sum,vis[15];
bool check(int l,int r)
{
    for(int i=1;in)
    {
        sum++;
        if(sum>3)
        return;
        for(int i=1;i<=n;i++)
            cout<>n;
    DFS(1);
    cout< 
其中的回溯部分就是check函数
 
可能有人会说：回溯不都是类似于这种形式吗
 
            col[now_r]=i;
            a[i]=1;
            b[i+now_r]=1;
            c[now_r-i+n]=1;
            DFS(now_r+1);
            a[i]=0;
            b[i+now_r]=0;
            c[now_r-i+n]=0;
 
这种DFS下一层前标记，然后在DFS后面归零
 
或者是这种形式
 
vis[i]++
DFS(i+1)
vis[i]--;
 
每一次搜索都标记一层，然在DFS后取消一层
 
其实这个代码里的CHECK函数也是一种回溯，回溯的目的就是去利用这条DFS路径上的条件来决定下一步的行动，那么check函数回溯了前面所有行的情况也就是前面DFS路径的情况，所以check也是一种回溯
 
但是不难看出这个CHECK作为回溯有个硬伤那就是耗时太高！
 回溯改良版
 
我们这次用了正常的回溯，虽然牺牲了一点空间但是换来了将近2倍的速率
 
#include 
using namespace std;
int col[15],n,sum,a[100],b[100],c[100];
void DFS(int r)
{
    if(r>n)
    {
        if(++sum>3) return;
        for(int i=1;i<=n;i++)
            cout<>n;
    DFS(1);
    cout< 
小结
 深搜主要就是递归
 但是当问题复杂化了之后 我们还需为了避免TLE或者MLE而设计剪枝和回溯，大多数问题缺少了剪枝和回溯都会出错，即便不错也会超时和超内存限制，如果没超，，那么数据应该是有问题的或者是题目过于简单已经只是递归了。
 
回溯最常见的问题就是要用DFS探索多个路径，而且当前这条探索路径中当前路径走过的点会影响到下一步的行动，但不会影响到下一条探索路径的任何行动。而回溯设计的过程中通常使用辅助数组的方式
 
剪枝则是在DFS中判断何时可以不用触底就停止递归，if(++sum>3) return 这一句也算是半个剪枝了，说是半个因为他实际上没有起到防止触底的作用，但是也阻止了DFS程序的一部分执行。下一次会拿出一道非常凸显剪枝重要性的题目。
 
可以自己去体会一下没有回溯和剪枝的DFS。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5520646.html