7.1 N皇后问题
N皇后问题
1 N皇后问题-回溯法
问题描述
在N×N的棋盘中放置N个皇后，使得任何两个皇后之间不能相互攻击，试给出所有的放置方法。
问题分析
- 问题解向量：(x1, x2, … , xn)
- 显约束：xi=1,2, … ,n
- 隐约束：
- 不同列：xi不等于xj；
- 不处于同一正、反对角线：|i-j|不等于|xi-xj|
算法时间复杂度
（1）搜索1+n+n2+…+nn=(nn+1-1)/n-1≤2nn;
（2）每个节点判断是否符合规则，最多要判断3n个位置（列方向、主与副对角线方向是否有皇后）
故最坏情况下时间复杂度O(3n×2nn)=O(nn+1)
算法实现
1 | bool Queen::Place(int k) { |
2
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Estom的博客！
相关推荐
2021-03-12
6.1 二叉树
二叉树 树>二叉树 1 二叉树简介概念 二叉树是一种特殊类型的通用树，它的每个节点最多可以有两个子节点。 二叉树通常被划分为三个不相交的子集。 节点的根 左二叉树 右二叉树 性质 二叉树第 i 层上的结点数目最多为 2i-1 (i≥1)。 深度为 k 的二叉树至多有 2k-1 个结点(k≥1)。 包含 n 个结点的二叉树的高度至少为 log2(n+1)。 在任意一棵二叉树中，若终端结点的个数为 n0，度为 2 的结点数为 n2，则 n0=n2+1。 2 二叉树分类严格二叉树 在严格二叉树中，每个非叶节点包含非空的左和右子树。 换句话说，每个非叶节点的等级将始终为2。具有n个叶子的严格二叉树将具有(2n-1)个节点。 完全二叉树 如果所有叶子都位于相同的水平d，则称二元树是完全二叉树。完全二叉树是二叉树，在0级和d级之间的每个级别包含正好$2^d$个节点。 具有深度d的完全二叉树中的节点总数是$2^{(d+1)}-1$，其中叶节点是$2^d$,非叶节点是$2^d-1$。 3 二叉树的操作——遍历搜索遍历搜索方法 深度优先搜索（DFS） 在这个策...
2021-03-16
12 深搜与广搜
深度优先搜索与广度优先搜索 用来处理多分支结构 对于现行问题或单分支结构的问题。不适用深度搜索和广度搜索 1 深度搜索 深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。 深度优先搜索与回溯剪枝这两个思想有一个非常重要的优势。它是一条路经走到黑。如果这条路径合适的话，就可以直接返回。另外。当前所有的搜索选项中，只有一条路径在工作。也就是说只需要记录当前一条路径的状态。所以解决迷宫问题的时候，不需要复杂的状态记录方法。只需要记录当前这一个分支的路径状态即可。 2 广度搜索 广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成...
2021-04-29
10 Pysyft 概述
pysyft 对pytorch框架和TensorFlow框架的federated框架进行了研究。 tensorflow federated 框架只提供了本地的仿真。 pysyft 框架提供了websocket worker初步实现了基于websocket网络通信的多进程仿真，是当前最接近于实践的一种仿真方式，能够实现多个linux/python环境下的仿真与多个进程下的仿真。只在0.2.4中有，可以尝试在此基础进行改进和训练。 参考文献 A generic framework for privacy preserving deep learning FedAvg 的 Pytorch 实现 安全深度学习框架PySyft 1 论文阅读pysyft的特点PySyft是用于安全和隐私深度学习的Python库，它在主流深度学习框架（例如PyTorch和TensorFlow）中使用联邦学习，差分隐私和加密计算（例如多方计算（MPC）和同态加密（HE））将隐私数据与模型训练分离。 基于PyTorch，只支持深度学习建模，不支持LR、GBDT等传统方法？ 支持联邦学习...
2020-01-04
3.3 搜索算法-深度优先搜索
深度优先搜索1 概述定义 深度优先搜索（DFS：Depth-First Search）是一种图搜索策略，其将搜索限制到 2 种操作： 访问图中的一个节点； 访问该节点的子节点； 过程 在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续探测下去。当顶点 v 的所有边都已被探寻过后，搜索将回溯到发现顶点 v 有起始点的那些边。这一过程一直进行到已发现从源顶点可达的所有顶点为止。实际上深度优先搜索最初的探究也是为了解决迷宫问题。 对图的深度优先搜索与对树（Tree）的深度优先遍历（Depth First Traversal）是类似的，区别在于图中可能存在环，所以可能会遍历到已经遍历的节点。 例子 例如，下面的图中，从顶点 2 开始遍历，当遍历到顶点 0 时，子顶点为 1 和 2，而顶点 2 已经遍历过，如果不做标记，遍历过程将陷入死循环。所以，在 DFS 的算法实现中需要对顶点是否访问过做标记。 上图的 DFS 遍历结果为 2, 0, 1, 3。 实现 DFS 算法可以通过不同方式来实现： 递归方式 非递归方式：栈（Stack）数据结构...
2021-03-13
2.1 单链表
单链表1 简介概念 单链表是有序元素集的集合。元素的数量可以根据程序的需要而变化。 单链表中的节点由两部分组成：数据部分和链接部分。 节点的数据部分存储将由节点表示的实际信息，而节点的链接部分存储其直接后继的地址。 单向链或单链表可以仅在一个方向上遍历。也就是说每个节点只包含下一个节点的指针，因此不能反向遍历链表。 链表复杂度 操作 平均复杂度 最坏复杂度 访问 θ(n) θ(n) 搜索 θ(n) θ(n) 插入 θ(1) θ(1) 删除 θ(1) θ(1) 2 链表的存储和实现链表的存储 链表不需要连续存在于存储器中。节点可以是存储器中的任何位置并链接在一起以形成链表。这实现了空间的优化利用。 链表的实现 链表通过结构体和指针实现 1234567struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); ...
2021-04-05
5.4 并查集
并查集 参考文献 https://zhuanlan.zhihu.com/p/93647900/ https://blog.csdn.net/qq_41754350/article/details/81271567 1 概念定义并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作： 合并（Union）：把两个不相交的集合合并为一个集合。 查询（Find）：查询两个元素是否在同一个集合中。 2 并查集原理初始化 初始化所有的节点的根节点是自己。 假如有编号为1, 2, 3, …, n的n个元素，我们用一个数组fa[]来存储每个元素的父节点（因为每个元素有且只有一个父节点，所以这是可行的）。一开始，我们先将它们的父节点设为自己。 查询 我们用递归的写法实现对代表元素的查询：一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。 合并 合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的...
