文档章节

N皇后问题 各种优化

o
 osc_fmg49rzg
发布于 2019/03/21 21:45
字数 1909
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

0.问题引入

 N皇后问题是一个经典的问题,在一个N*N的棋盘上放置N个皇后,每行一个并使其不能互相攻击(同一行、同一列、同一斜线上的皇后都会自动攻击),问有多少种摆法。

题目链接:https://www.luogu.org/problemnew/show/P1219

1、普通回溯

回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。

算法思想:

1. 在第k(1≤k≤N)行选择一个位置,判断这个位置是否可以摆,可以摆就进入第 k+1 行,不可以就试下一个位置;

2. 如果一直试到本行最后一个都不行,说明前面k-1行有位置选得不恰当,回到第 k-1 行,试 k-1 行的下一个位置。

3. 反复执行1,2,到最后一行摆上棋子时,说明找到了一个解。

一个问题能用回溯法求解,它的解具有$N$元组的形式,我们使用用$N$元组$(x_1,x_2,...,x_n)$表示问题的解,其中$x_i$表示第$i$行的皇后所处的列号。

核心代码:

//row,col表示当前尝试摆放皇后的行号与列好
bool check(int row, int col) {
    for (int i = 1; i < row; i++) {
        if (x[i] == col)//列冲突
            return false;
        if (abs(row - i) == abs(col - x[i]))//对角线冲突
            return false;
    }
    return true;
}
void DFS(int k) {
    if (k == N + 1) {
        //获得了一个解
        cnt++;
        return;
    }
    for (int i = 1; i <= N; i++) {
        if (check(k, i)) {
            x[k] = i;//标注第k行上第i个位置摆上了皇后
            DFS(k + 1);
        }
    }
}

1.1 递归实现:

N=11,12的时就顶不住了,嗝屁了。

#include <iostream>
#include <math.h>
using namespace std;

int x[15];
int N, cnt;

bool check(int row, int col) {
    //回溯,不会受到后面行的影响
    for (int i = 1; i < row; i++) {
        if (x[i] == col)return false;
        if (abs(row - i) == abs(col - x[i]))return false;
    }
    return true;
}
void DFS(int k) {
    if (k == N + 1) {
        cnt++;
        if (cnt <= 3) {
            for (int i = 1; i <= N; i++) {
                cout << x[i] << " ";
            }
            cout << endl;
        }
        return;
    }
    for (int i = 1; i <= N; i++) {
        if (check(k, i)) {
            x[k] = i;
            DFS(k + 1);
        }
    }
}

int main() {
    cin >> N;
    DFS(1);
    cout << cnt << endl;
    return 0;
}
View Code

1.2 非递归实现:

算法优化一般不从这里考虑,因为非递归虽然是会快一点,但也只是那么一点而已,数据量小几乎没有区别,两个都跑不过去。

#include <iostream>
#include <math.h>
using namespace std;

int x[15];
int N, cnt;

bool check(int row, int col) {
    //回溯,不会受到后面行的影响
    for (int i = 1; i < row; i++) {
        if (x[i] == col)return false;
        if (abs(row - i) == abs(col - x[i]))return false;
    }
    return true;
}


void queen(){
    //i表示第几册,j表示在第i层搜索位置
    int i = 1, j = 1;
    while (i <= N){
        while (j <= N){
            //如果当前位置合法
            if (check(i, j)) {
                //把x[i]暂时赋值成j
                x[i] = j;
                j = 1;
                break;
            }
            else
                j++;
        }
        //第i行没有找到可以放置皇后的位置
        if (x[i] == 0){
            //如果回溯到了第0行,说明完成了         
            if (i == 1)
                break;
            //回溯
            else{
                i--;
                j = x[i] + 1;//j为上一行的皇后位置+1
                x[i] = 0;//上一行清零
                continue;
            }
        }
        //如果找到了第N层,输出出来
        if (i == N){
            cnt++;
            if (cnt <= 3) {
                for (int i = 1; i <= N; i++) {
                    cout << x[i] << " ";
                }
                cout << endl;
            }
            j = x[i] + 1; 
            x[i] = 0;     
            continue;
        }
        i++;              
    }
}
int main() {
    cin >> N;
    //DFS(1);
    queen();
    cout << cnt << endl;
    return 0;
}
View Code

 

2、减半优化

其实仔细看解就不难发现,每个结果总有另一个与之对称。我们可以利用棋盘的对称, 只用回溯一半 。效率能提升50%。

对于第一层,只下该行的前一半的位置即可。但是对于奇数的N,计算出来的结果会将第一行下在中间位置的解算了两遍。所以要单独处理一下。

效率提升不到50%(奇数的情况),并不算多,题目的测试数据只到13,勉强跑过了,但优化还没结束。

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

int x[15];
vector<int> v[3];
int N, cnt;
int flag, oddCnt;

bool check(int row, int col) {
    //回溯,不会受到后面行的影响
    for (int i = 1; i < row; i++) {
        if (x[i] == col)return false;
        if (abs(row - i) == abs(col - x[i]))return false;
    }
    return true;
}
void DFS(int k) {
    if (k == N + 1) {
        if (flag&&x[1] == (N + 1) / 2) {
            oddCnt++;
            if (oddCnt % 2 == 0)cnt++;
        }
        else
        cnt++;
        if (cnt <= 3) {
            for (int i = 1; i <= N; i++) {
                cout << x[i] << " ";
                v[cnt - 1].push_back(x[i]);
            }
            cout << endl;
        }
        return;
    }
    int len = (k == 1) ? (N + flag) / 2 : N;
    for (int i = 1; i <= len; i++) {
        if (check(k, i)) {
            x[k] = i;
            DFS(k + 1);
        }
    }
}

int main() {
    cin >> N;
    if (N & 1)flag = 1;
    DFS(1);
    for (int i = cnt, j = cnt - 1; i < 3 && j >= 0; i++, j--) {
            for (int k = N - 1; k >= 0; k--) {
                cout << v[j][k] << " ";
            }
            cout << endl;
        }
    
    cout << cnt*2 << endl;
    return 0;
}
View Code

 

3、优化判断

以本图为例:

每条橙色对角线的行列之差是相同的。

每条蓝色对角线的行列之和是相同的。

用两个bool数组用来记录行列之和为 i 的正斜线、行列之差为 i 的反斜线是否已经被占据。考虑到行列之差可能为负数,棋盘坐标 [x,y] 对应下标 [ x - y + n ]。

再用一个数组记录第 i 列是否有元素。

#include <iostream>
using namespace std;

int N, cnt,a[15];
//正对角线、副对角线、行
bool x1[31], x2[31], y[15];

void DFS(int k) {
    if (k == N + 1) {
        cnt++;
        if (cnt <= 3) {
            for (int i = 1; i <= N; i++) {
                cout << a[i] << " ";
            }
            cout << endl;
        }
        return;
    }
    for (int i = 1; i <= N; i++) {
        //这里x2下标不能用abs,那样是不对的
        if (!x1[i + k] && !x2[k - i + N] && !y[i]) {
            a[k] = i;
            x1[i + k] = 1;
            x2[k - i + N] = 1;
            y[i] = 1;
            DFS(k + 1);
            x1[i + k] = 0;
            x2[k - i + N] = 0;
            y[i] = 0;
        }
    }
}


int main() {
    cin >> N;
    DFS(1);
    cout << cnt << endl;
    return 0;
}
View Code

当N较大时,算法会耗费大量的次数在无用的回溯上,时间还是没有显著提高。

4、位运算优化

警告:以下代码可能引起不适,请60岁以下用户在家长陪同下阅读。

位运算是计算机最快的操作,我们可以用数的二进制位表示各纵列、对角线是否可以放置皇后。

看讲解的:https://blog.csdn.net/Hackbuteer1/article/details/6657109 博主讲的很清楚了。

#include <iostream>
#include <queue>
using namespace std;

int n, limit, cnt;
int x[15], k = 1;
//行,左对角线,右对角线
void DFS(int row,int left,int right) {
    if (row != limit) {
        //row|left|right表示这一行的所有禁止位置,取反再和limit按位与,得到的是该行可以放的几个位置        
        int pos = limit & ~(row | left | right);
        //每一个可以摆的位置,都要做一次
        while (pos) {
            //找到的可以放皇后的位置(pos二进制最右边的一个1)
            int p = pos & -pos;// pos & (~pos+1);
            //把这一位置0,表示不为空
            pos &= pos - 1;//pos=pos-p;
            //把p所在row,left,right的位都置1。
            //(left | p)<< 1 是因为这一行由左对角线造成的禁止位在下一行要右移一下;right同理
            DFS(row | p, (left | p) << 1, (right | p) >> 1);
        }
    }
    else {
        cnt++;
    }
}

int main() {
    cin >> n;
    limit = (1 << n) - 1;
    DFS(0, 0, 0);
    cout << cnt << endl;
    return 0;
}

 

#include <iostream>
#include <queue>
using namespace std;

int n, limit, cnt;
int x[15], k = 1;
//行,左对角线,右对角线
void DFS(int row,int left,int right) {
    if (row != limit) {
        int pos = limit & ~(row | left | right);
        while (pos) {
            //找到的可以放皇后的位置
            int p = pos & -pos;// pos & (~pos+1);
            pos &= pos - 1;
            if (cnt < 3) {
                int t = p, num = 1;
                while (t != 1) {
                    num++;
                    t >>= 1;
                }
                x[k++] = num;
            }
            DFS(row | p, (left | p) << 1, (right | p) >> 1);
            if (cnt < 3) k--;
        }
    }
    else {
        if (cnt < 3) {
            for (int i = 1; i <= n; i++) {
                cout << x[i] << " ";
            }
            cout << endl;
        }
        cnt++;
    }
}

int main() {
    cin >> n;
    limit = (1 << n) - 1;
    DFS(0, 0, 0);
    cout << cnt << endl;
    return 0;
}
View Code

果然名不虚传~

 

上一篇: 建模软件
下一篇: HTML简介
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
对八皇后的补充以及自己解决2n皇后问题代码

有了上次的八皇后的基础。这次准备解决2n皇后的问题,: //问题描述 //  给定一个n*n的棋盘,棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后,使任意的两个黑皇后都...

osc_nnp3dgfb
2019/02/15
2
0
回溯法/深度优先遍历的简单优化技巧

深度优先遍历配合回溯,是解决很多问题的好方法,比如八皇后问题。 皇后的排布规则:n个皇后放在n*n的矩阵里,要求一列只有一个,一行只有一个,任一斜线上只有一个(/和)。 通常,我们会把...

刘地
2012/11/17
1.3K
0
Java数据结构之递归(Recursion)

递归解决问题 各种数学问题如:8皇后问题,汉诺塔,阶乘问题,迷宫问题,球和篮子的问题(google编程大赛) 各种算法中也会使用到递归,比如快速排序,归并排序,二分查找,分治算法等 将用栈...

osc_869quh0r
2019/07/25
6
0
【八皇后问题】递归回溯法【原创】

八皇后问题 八皇后问题是一个古老的问题,于1848年由一位国际象棋棋手提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,如...

osc_pnw2apz4
2018/03/05
2
0
N皇后问题(回溯做法)

题目描述 相信大家都听过经典的“八皇后”问题吧?这个游戏要求在一个8×8的棋盘上放置8个皇后,使8个皇后互相不攻击(攻击的含义是有两个皇后在同一行或同一列或同一对角线上)。 桐桐对这个...

osc_xopfh3w8
2019/05/09
1
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Cloud开发人员如何解决服务冲突和实例乱窜?(IP实现方案)

点击上方“陶陶技术笔记”关注我 回复“资料”获取作者整理的大量学习资料! 一、背景 在我上一篇文章《Spring Cloud开发人员如何解决服务冲突和实例乱窜?》中提到使用服务的元数据来实现隔...

zlt2000
2019/09/06
0
0
Linux下diff命令用法详解

大家好,我是良许。 我们在平时工作的时候,经常要知道两个文件之间,以及同个文件不同版本之间有何异同点。在 Windows 下,有 beyond compare 这个好用的工具,而在 Linux 下,也有很多很强...

osc_th8jvcw7
19分钟前
7
0
万变不离其宗之UART要点总结

[导读] 单片机开发串口是应用最为广泛的通信接口,也是最为简单的通信接口之一,但是其中的一些要点你是否明了呢?来看看本人对串口的一些总结,当然这个总结并不能面面俱到,只是将个人认为...

osc_kyehmyzk
20分钟前
7
0
kafka的认识、安装与配置

认识Kafka 花费越少的精力在数据移动上,就能越专注于核心业务 --- 《Kafka:The Definitive Guide》 认识 Kafka 之前,先了解一下发布与订阅消息系统:消息的发送者不会直接把消息发送给接收...

osc_wy8nhxhn
22分钟前
0
0
使用pandas进行数据处理——DataFrame篇

  今天是pandas数据处理专题的第二篇文章,我们一起来聊聊pandas当中最重要的数据结构——DataFrame。   上一篇文章当中我们介绍了Series的用法,也提到了Series相当于一个一维的数组,只...

开源仔
22分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部