用混合遗传算法求解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皇后问题的片上多核并行混合遗传算法 被引量：4

2

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

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

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

下载PDF 职称材料

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

3

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

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

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

下载PDF 职称材料

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

4

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

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

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

下载PDF 职称材料

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

5

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

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

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

下载PDF 职称材料

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

6

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

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

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

下载PDF 职称材料

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

7

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

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

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

下载PDF 职称材料

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

8

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

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

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

下载PDF 职称材料

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

9

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

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

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

下载PDF 职称材料

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

10

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

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

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

下载PDF 职称材料

一种基于TLA的解决N皇后问题的方法

11

作者 台亚非 龙士工 《贵州大学学报（自然科学版）》 2016年第1期86-88,共3页

行为时序逻辑语言(TLA+)是一种在模型检测范围内能够表达模型程序和逻辑规约的语言。N皇后问题是一个久远的问题,回溯法是解决该问题一种经典的方法。本文提出如何用行为时序逻辑语言TLA+去描述N皇后问题,然后使用Toolbox工具去检测n=5... 行为时序逻辑语言(TLA+)是一种在模型检测范围内能够表达模型程序和逻辑规约的语言。N皇后问题是一个久远的问题,回溯法是解决该问题一种经典的方法。本文提出如何用行为时序逻辑语言TLA+去描述N皇后问题,然后使用Toolbox工具去检测n=5时该问题的全部解。 展开更多

关键词 行为时序逻辑 模型检测 n皇后问题 TOOLBOX

下载PDF 职称材料

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

12

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

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

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

下载PDF 职称材料

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

13

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

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

关键词 n后问题 回溯算法

下载PDF 职称材料

一种具有个体学习能力的演化算法

14

作者 何峰 康立山 陈毓屏 《计算机科学》 CSCD 北大核心 2002年第10期64-66,共3页

1引言 70年代由美国学者John H.Holland提出的遗传算法是一种借鉴生物界自然选择思想和自然遗传机制的全局搜索算法[1].它把问题的每一个可能解看作一个个体,而个体的集合则形成种群.算法在整个种群空间内随机搜索,按一定的评价函效对... 1引言 70年代由美国学者John H.Holland提出的遗传算法是一种借鉴生物界自然选择思想和自然遗传机制的全局搜索算法[1].它把问题的每一个可能解看作一个个体,而个体的集合则形成种群.算法在整个种群空间内随机搜索,按一定的评价函效对当前种群中每一个个体进行评价,然后基于个体的评价值按优胜劣汰原则选择出父体,再用变异、杂交等遗传算子作用于父体以产生新的个体形成下一代种群,如此反复,使种群不断进化,直至产生最终的解.因为演化算法在解决大空间、非线性、全局寻优等复杂问题时具有传统方法所不具备的独特的优越性,所以它得到了广泛的研究和应用. 展开更多

关键词 遗传算法 全局搜索算法 演化算法 个体学习能力

下载PDF 职称材料

元皇后问题回溯算法改进

15

作者 钱卫 张钟澍 张奎良 《四川大学学报（自然科学版）》 CAS CSCD 北大核心 2009年第2期339-342,共4页

回溯算法是解决N元皇后问题最有效的算法之一。在传统回溯算法的基础上,采用动态规划的思想,对算法进行了改进,改进后的算法大大降低了求解的复杂度和比较次数。文章还给出了改进算法的实现并通过理论分析和实验数据证明了算法的可行性。

关键词 回溯算法 皇后问题 动态规划

原文传递

应用搜索原理解n皇后问题算法分析及优化

16

作者 宋阳秋 《电脑知识与技术》 2006年第12X期181-181,199,共2页

n皇后问题是非结构化的问题,人工智能中的搜索策略——回溯法是解决这类问题的有效方法。本文介绍了利用回溯法求解n皇后问题的基本思想以及实现方法,并对算法提出了优化的方法,使得算法的运行效率更高。

关键词 人工智能 n皇后问题 回溯法 算法优化

下载PDF 职称材料

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

17

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

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

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

下载PDF 职称材料

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

18

作者 韩宇南 吕英华 黄小红 《计算机工程与应用》 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 职称材料

一种采用整数编码的全局优化算法 被引量：3

19

作者 胡能发 康立山 《湖北大学学报（自然科学版）》 CAS 2002年第2期123-126,共4页

基于演化计算的群体搜索技术 ,采用整数编码构造遗传算子和自适应函数 ,对n皇后问题进行求解 ,实验结果表明 ,本算法具有快速、有效的特点 .

关键词 整数编码 全局优化算法 遗传算法 n皇后问题

下载PDF 职称材料

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

20

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

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

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

下载PDF 职称材料