用混合遗传算法求解N皇后问题 被引量：16

1

作者 刘娟 欧阳建权 陈良军 《湘潭大学自然科学学报》 CAS CSCD 北大核心 2007年第2期37-41,共5页

N皇后问题是NP难题,一般求解的方法为回溯法.当问题规模较小时用回溯法能有效求解,但当问题规模较大时其求解时间耗费非常巨大.该文提出用局部搜索与简单遗传算法(SGA)相结合的混合遗传算法(HGA)来求解N皇后问题,用N皇后的约束条件作为... N皇后问题是NP难题,一般求解的方法为回溯法.当问题规模较小时用回溯法能有效求解,但当问题规模较大时其求解时间耗费非常巨大.该文提出用局部搜索与简单遗传算法(SGA)相结合的混合遗传算法(HGA)来求解N皇后问题,用N皇后的约束条件作为遗传算法的适应值函数.设计了高效的染色体编码、初始化种群方法、遗传算子以及局部搜索算子,使它们符合求解问题的需要.通过与回溯法和相关的遗传算法比较,实验证实了用混合遗传算法求解N皇后的有效性. 展开更多

关键词 n皇后问题 适应值 遗传算法 局部搜索

在线阅读 下载PDF 职称材料

求解N皇后问题的片上多核并行混合遗传算法 被引量：5

2

作者 张步忠 程玉胜 王一宾 《计算机工程》 CAS CSCD 北大核心 2015年第7期199-203,共5页

遗传算法求解大规模皇后问题的耗时长、速度慢。为此,在分析现有N皇后问题求解方案和并行遗传算法的基础上,将动态规划引入到局部搜索策略中,在多核平台实现粗粒度并行遗传算法(CPGA)用于求解N皇后问题,避免传统的粗粒度并行种群迁移、... 遗传算法求解大规模皇后问题的耗时长、速度慢。为此,在分析现有N皇后问题求解方案和并行遗传算法的基础上,将动态规划引入到局部搜索策略中,在多核平台实现粗粒度并行遗传算法(CPGA)用于求解N皇后问题,避免传统的粗粒度并行种群迁移、通信等开销。针对并行化后多个子种群解趋同、迭代慢等问题,提出改进的面向遗传算子并行化的遗传算法(OOPGA)。实验结果表明,改进后的OOPGA算法在运行时间、加速比等方面均比CPGA算法好。 展开更多

关键词 片上多核 遗传算法 并行计算 粗粒度 n皇后问题 遗传算子并行化

在线阅读 下载PDF 职称材料

并行改进回溯算法实现N皇后问题的快速计数 被引量：6

3

作者 韩宇南 吕英华 黄小红 《计算机工程与应用》 CSCD 北大核心 2006年第36期1-3,共3页

通过对N皇后问题棋盘矩阵的旋转,改进了回溯算法,并通过计算机集群并行实现了N皇后的计数问题。考虑了棋盘矩阵顺时针旋转90°、180°和270°部分解存在重复的特性,改进了回溯方法,单机能够在15s内对16皇后问题进行计数。... 通过对N皇后问题棋盘矩阵的旋转,改进了回溯算法,并通过计算机集群并行实现了N皇后的计数问题。考虑了棋盘矩阵顺时针旋转90°、180°和270°部分解存在重复的特性,改进了回溯方法,单机能够在15s内对16皇后问题进行计数。改进回溯算法的运算效率是顺序回溯法的4.69倍。然后通过固定前三行皇后的位置,可以把N皇后问题分成多个任务,实现了并行计算。在7个节点28个CPU的计算机集群上进行了实验,能够在8min内实现对20皇后的计数,能够在1小时零8分钟内实现21皇后的计数。N皇后计数这个经典问题,通过实现程序的标准化,可以成为检验计算机集群运算性能的基准。 展开更多

关键词 n皇后计数问题 回溯算法 计算机集群

在线阅读 下载PDF 职称材料

改进的基于Erlang的N皇后问题算法 被引量：3

4

作者 向宏 孙黎明 桑军 《计算机工程与应用》 CSCD 2012年第10期64-67,共4页

基于Erlang语言平台解决N皇后问题,通过对原有基于Erlang的N皇后问题算法进行分析,提出了一种改进算法。该算法利用位运算操作,并且在每一行只搜索可以放置皇后的位置。理论分析与实验证明了该算法能明显提升N皇后问题算法效率。

关键词 ERLAnG n皇后问题 位运算

在线阅读 下载PDF 职称材料

基于自组装的N皇后问题DNA计算算法 被引量：5

5

作者 吴帆 李肯立 《电子学报》 EI CAS CSCD 北大核心 2013年第11期2174-2180,共7页

N皇后问题是理论计算机科学中一个经典的NP难问题.自Adleman首次运用DNA计算来解决NP问题以来,DNA计算已成为计算机科学的研究热点之一,现有N皇后问题的DNA计算机算法多基于粘贴和剪接模型,存在生化操作复杂度和实验误差较高等问题.本... N皇后问题是理论计算机科学中一个经典的NP难问题.自Adleman首次运用DNA计算来解决NP问题以来,DNA计算已成为计算机科学的研究热点之一,现有N皇后问题的DNA计算机算法多基于粘贴和剪接模型,存在生化操作复杂度和实验误差较高等问题.本文提出了一种基于DNA自组装模型来求解N皇后问题的DNA计算方法.算法通过减少实验操作步骤数,降低了生化解的错误率.算法使用的tiles分子块种类为O(n2),生化操作复杂性为O(1),其中n为皇后的个数.与求解N皇后问题的其它DNA算法的对比分析表明,本算法可提高生化解的准确性,降低算法生化实验的复杂度,具有良好的易操作性. 展开更多

关键词 DnA计算 自组装模型 n皇后问题 tile模型

在线阅读 下载PDF 职称材料

一个求解n皇后问题的演化策略 被引量：3

6

作者 吴兆福 潘清芳 《江汉石油学院学报》 CSCD 北大核心 2002年第3期111-112,共2页

基于郭涛算法多目标优化思想 ,采用分解多目标和二次演化的方法 ,对具有离散性的n皇后问题进行求解。测试表明 ,该算法对搜索空间不具有局域性的离散问题 。

关键词 求解 演化策略 郭涛算法 n皇后问题 多目标优化

在线阅读 下载PDF 职称材料

基于对称性计算N皇后问题的非递归算法 被引量：3

7

作者 孙国伟 买阿丽 《计算机与现代化》 2013年第1期19-21,24,共4页

利用回溯法,采用栈和队列实现计算N皇后解的一个新的非递归算法,并提出N皇后解的4个对称性质,重点分析5皇后的10个解之间的对称关系。然后利用对称性将搜索空间缩小为解空间的一半,给出计算N皇后问题的优化算法。理论分析和实验表明对... 利用回溯法,采用栈和队列实现计算N皇后解的一个新的非递归算法,并提出N皇后解的4个对称性质,重点分析5皇后的10个解之间的对称关系。然后利用对称性将搜索空间缩小为解空间的一半,给出计算N皇后问题的优化算法。理论分析和实验表明对称性可以明显提高N皇后问题的计算效率。 展开更多

关键词 栈 队列 非递归算法 n皇后问题 回溯法

在线阅读 下载PDF 职称材料

应用布尔遗传算子求解N皇后问题 被引量：1

8

作者 帅训波 马书南 《计算机工程与应用》 CSCD 北大核心 2011年第16期49-51,68,共4页

应用回溯法求解规模较大的N皇后问题时,时间开销巨大。从提出布尔遗传算子角度,增强遗传算法局部搜索性能,与具有良好全局搜索性能的矩阵遗传算子组合应用,对N皇后问题求解。采用自然数和二进制互换的编码方式,应用N皇后的约束条件构造... 应用回溯法求解规模较大的N皇后问题时,时间开销巨大。从提出布尔遗传算子角度,增强遗传算法局部搜索性能,与具有良好全局搜索性能的矩阵遗传算子组合应用,对N皇后问题求解。采用自然数和二进制互换的编码方式,应用N皇后的约束条件构造适应度函数,保证了算法的全局收敛性。通过与回溯法和相关遗传算法比较,实验证实了该方法应用于求解N皇后问题,具有良好的搜索效率和求解质量。 展开更多

关键词 n皇后问题 布尔遗传算子 适应度函数 遗传算法

在线阅读 下载PDF 职称材料

一种求解N皇后问题的优化组合遗传算法 被引量：1

9

作者 黄复贤 《昆明理工大学学报（自然科学版）》 CAS 北大核心 2011年第2期46-49,共4页

基于遗传算子优化组合思想,采用二进制编码方式,选择矩阵遗传算子和布尔遗传算子组合应用对N皇后问题求解,避免了常规遗传算法的杂交率和变异率选取.从N皇后问题的约束条件角度,构造适应度评价函数,保证了算法的全局收敛性.实验结果表明... 基于遗传算子优化组合思想,采用二进制编码方式,选择矩阵遗传算子和布尔遗传算子组合应用对N皇后问题求解,避免了常规遗传算法的杂交率和变异率选取.从N皇后问题的约束条件角度,构造适应度评价函数,保证了算法的全局收敛性.实验结果表明,本文算法具有良好的搜索效率和求解质量,运行一次在收敛代数内可以搜索到多个解,当皇后数N较大时,搜索到解的效率越明显好于常规遗传算法. 展开更多

关键词 n皇后问题 矩阵遗传算子 布尔遗传算子 优化组合

在线阅读 下载PDF 职称材料

基于群体智能求解N后问题

10

作者 王会颖 贾瑞玉 +1 位作者 章义刚 刘慧婷 《计算机工程与应用》 CSCD 北大核心 2007年第5期71-75,共5页

提出了一种求解N后问题的蚂蚁模型算法,它受群体智能的蚂蚁算法和多Agent系统的启发,并吸收了回溯算法的优点,是一种随机搜索算法,从根本上改变了回溯算法的系统地搜索机制,避免了大量的冗余搜索,又保证了必要的搜索。在求解N后问题的... 提出了一种求解N后问题的蚂蚁模型算法,它受群体智能的蚂蚁算法和多Agent系统的启发,并吸收了回溯算法的优点,是一种随机搜索算法,从根本上改变了回溯算法的系统地搜索机制,避免了大量的冗余搜索,又保证了必要的搜索。在求解N后问题的第一个解时,大大地减少了求解时间和求解步数,当N较大时,也可得到较好的求解效果。仿真实验结果证实了这一算法的有效性。 展开更多

关键词 蚂蚁模型算法 群体智能 蚂蚁算法 n后问题

在线阅读 下载PDF 职称材料

基于Erlang的多核并行计算N-皇后问题

11

作者 孙黎明 桑军 向宏 《计算机工程与应用》 CSCD 2012年第17期72-75,118,共5页

为了充分利用多核CPU的资源,利用并行计算来处理问题已逐渐成为主流。利用Erlang中的并行机制计算N-皇后问题,设计并实现了并行计算N-皇后问题的算法。实验结果表明,该算法有效地提升了多核计算机资源的利用率,提高了求解问题的效率。此... 为了充分利用多核CPU的资源,利用并行计算来处理问题已逐渐成为主流。利用Erlang中的并行机制计算N-皇后问题,设计并实现了并行计算N-皇后问题的算法。实验结果表明,该算法有效地提升了多核计算机资源的利用率,提高了求解问题的效率。此外,由于Erlang本身具有数据处理上限只受硬件处理能力限制的特性,算法可扩展性也比较强。 展开更多

关键词 ERLAnG 多核 并行计算 n-皇后问题

在线阅读 下载PDF 职称材料

类似筛法的N皇后问题求解算法

12

作者 程元斌 《计算机系统应用》 2013年第10期147-150,共4页

迄今为止,已有多种基于不同理论的八皇后问题算法.本文提出一种类似筛法的新算法:在棋盘某一格放上一个皇后的同时划去经过这一格的纵、横、及正负45度线上的所有格位,或者说筛去这些格位;后来的皇后只能放在未被占据或划去的格位上;若... 迄今为止,已有多种基于不同理论的八皇后问题算法.本文提出一种类似筛法的新算法:在棋盘某一格放上一个皇后的同时划去经过这一格的纵、横、及正负45度线上的所有格位,或者说筛去这些格位;后来的皇后只能放在未被占据或划去的格位上;若所有的皇后都能放入一个格位,则得到了一个布局或一个解.依据这种思路容易制定一个N皇后问题的简洁算法.实验结果表明,筛法算法的效率大大高于经典的回溯法. 展开更多

关键词 n皇后问题 筛法 回溯法

在线阅读 下载PDF 职称材料

N皇后问题独立解算法研究和仿真实现

13

作者 温录亮 柯振钦 邹俊飞 《电脑与电信》 2013年第5期44-46,共3页

根据N皇后可行解的七种对称关系,提出求N皇后问题独立解的算法,并验证算法的可行性和正确性。建立求解N皇后问题的仿真软件,验证N皇后问题全解和独立解个数约8:1的数学关系。

关键词 n皇后问题 独立解算法 仿真软件 数学关系

在线阅读 下载PDF 职称材料

N皇后问题的Java程序实现及分析

14

作者 吴红萍 《计算机与现代化》 2011年第3期15-16,20,共3页

利用一种简易的回溯算法,给出Java语言实现N皇后问题的完整程序,并在程序中准确地统计程序运行的时间开销。

关键词 n皇后问题 回溯算法 JAVA语言

在线阅读 下载PDF 职称材料

基于BIT位运算的N皇后问题解法 被引量：3

15

作者 杨凯 罗文俊 《贵州师范大学学报（自然科学版）》 CAS 2009年第2期96-98,共3页

皇后问题是一经典的回溯算法问题,本文使用B IT位运算对非递归的回溯算法进行优化,取得了较好的效果,对其他类似问题的算法的优化有一定指导意义。

关键词 n皇后 回溯算法 位运算

在线阅读 下载PDF 职称材料

基于Visual C++的N后问题的回溯算法设计

16

作者 冯慧玲 《电脑知识与技术（过刊）》 2010年第35期10024-10025,10027,共3页

N后问题是一个古典的问题,该文对N后问题的回溯算法进行了分析,用Visual c++实现该算法。

关键词 n后问题 回溯算法

在线阅读 下载PDF 职称材料

n皇后问题的一种解 被引量：1

17

作者 邬家邦 《华中理工大学学报》 CSCD 北大核心 1994年第1X期195-198,共4页

在ＦａｌｋｏｗｓｋｉＢＪ和ＳｃｈｍｉｔｚＬ的论文中，大于３的自然数被分成７部分，并对每部分中的ｎ给出了ｎ皇后问题的一个特解。本文改进了他们的方法，将大于３的自然数仅分成５部分，然后对每部分中的ｎ用统一方法给出ｎ皇后问... 在ＦａｌｋｏｗｓｋｉＢＪ和ＳｃｈｍｉｔｚＬ的论文中，大于３的自然数被分成７部分，并对每部分中的ｎ给出了ｎ皇后问题的一个特解。本文改进了他们的方法，将大于３的自然数仅分成５部分，然后对每部分中的ｎ用统一方法给出ｎ皇后问题的一种解，从而有效地简化了已有的结果。 展开更多

关键词 8皇后问题 回溯算法 n皇后问题

全文增补中

N皇后问题的启发式算法探讨 被引量：1

18

作者 杜勤 秦前付 樊永辉 《计算机与网络》 2010年第24期51-53,共3页

搜索策略的选择与设计是人工智能领域问题求解的核心问题之一,直接影响到问题求解过程中存储空间的占用和计算的复杂性,影响到问题求解的效率。在给出N皇后问题形式化描述和现有搜索算法的基础上,设计了3种解决N皇后问题的启发式算法,... 搜索策略的选择与设计是人工智能领域问题求解的核心问题之一,直接影响到问题求解过程中存储空间的占用和计算的复杂性,影响到问题求解的效率。在给出N皇后问题形式化描述和现有搜索算法的基础上,设计了3种解决N皇后问题的启发式算法,并将其与深度优先和宽度优先等搜索策略进行了分析和比较,得出了几点关于设计启发式算法的启示。 展开更多

关键词 n皇后问题 搜索策略 深度优先策略 启发式算法

在线阅读 下载PDF 职称材料

基于启发式的N皇后问题的快速算法及其实现 被引量：1

19

作者 王寅庆 《电脑知识与技术（过刊）》 2009年第8X期6418-6419,共2页

N皇后问题是一个比较传统的组合搜寻问题,也是人工智能领域的一个经典的搜寻实例。给出了对N皇后问题求全部解的基于启发式的和以空间换时间的快速算法思路及其实现,将之同一般的回溯算法进行了时间耗费的比较,证明了算法是较优的算法;... N皇后问题是一个比较传统的组合搜寻问题,也是人工智能领域的一个经典的搜寻实例。给出了对N皇后问题求全部解的基于启发式的和以空间换时间的快速算法思路及其实现,将之同一般的回溯算法进行了时间耗费的比较,证明了算法是较优的算法;并讨论了算法的时间和空间复杂性。在个人电脑上,求16皇后全部解只需12.2秒。 展开更多

关键词 n皇后问题 回溯 递归 本地搜索 人工智能

在线阅读 下载PDF 职称材料

N皇后问题回溯算法探讨 被引量：7

20

作者 张万军 《宜宾学院学报》 2006年第6期64-66,共3页

本文在分析N皇后问题解的结构的基础上,优化了利用回溯法求解N皇后问题的算法的循环结束条件,借助于矩阵改进了互不攻击的条件检测方法,避免了求解复杂的逻辑表达式,大大地减少了比较次数,使得算法的运行效率更高。

关键词 n元皇后问题 互不攻击的布局 回溯算法

在线阅读 下载PDF 职称材料