共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
通过对N皇后问题棋盘矩阵的旋转,改进了回溯算法,并通过计算机集群并行实现了N皇后的计数问题。考虑了棋盘矩阵顺时针旋转90°、180°和270°部分解存在重复的特性,改进了回溯方法,单机能够在15s内对16皇后问题进行计数。改进回溯算法的运算效率是顺序回溯法的4.69倍。然后通过固定前三行皇后的位置,可以把N皇后问题分成多个任务,实现了并行计算。在7个节点28个CPU的计算机集群上进行了实验,能够在8min内实现对20皇后的计数,能够在1小时零8分钟内实现21皇后的计数。N皇后计数这个经典问题,通过实现程序的标准化,可以成为检验计算机集群运算性能的基准。 相似文献
3.
迄今为止,已有多种基于不同理论的八皇后问题算法.本文提出一种类似筛法的新算法:在棋盘某一格放上一个皇后的同时划去经过这一格的纵、横、及正负45度线上的所有格位,或者说筛去这些格位;后来的皇后只能放在未被占据或划去的格位上;若所有的皇后都能放入一个格位,则得到了一个布局或一个解.依据这种思路容易制定一个N皇后问题的简洁算法.实验结果表明,筛法算法的效率大大高于经典的回溯法. 相似文献
4.
秦丹 《数字社区&智能家居》2013,(26):5954-5957
N皇后问题是NP问题,以随机算法结合回溯求解该问题,能获得很好性能。算法性能与随机皇后数量的关系曲线呈U型。随机皇后数量须在宽度不大于20的特定范围内才能获得较好性能。100以内随n变大,最佳随机皇后数量从n-10到n-17缓慢变化。最佳随机皇后数量使算法能在常规时间内求解n>100的情况,远大于单纯回溯法求解规模30。由于回溯开销,提高随机算法性能的做法不能有效降低总用时。算法用时随n值递增的速度不断趋缓。 相似文献
5.
赵群英 《数字社区&智能家居》2011,(22):5436-5438
针对适于回溯算法求解的问题模型,给出了常规回溯算法及基于最小剩余值启发式的改进型回溯算法,以N皇后问题为例对二者进行了比较与分析. 相似文献
6.
吴丹 《电脑编程技巧与维护》2016,(19):33-34
N皇后问题是NP难题,一般求解的方法是回溯法。当问题规模较小时用回溯法能有效求解,但当问题规模较大时其求解时间消耗非常巨大。使用禁忌搜索算法来求解N皇后问题,用N皇后的冲突数为禁忌搜索算法的目标评价函数,通过实验得出结论:(1)使用禁忌搜索方法比使用回溯法更快速;(2)使用禁忌搜索方法更适合求解大规模棋盘的N皇后问题。同时提出了下一步需要完善和改进的地方。 相似文献
7.
利用一种简易的回溯算法,给出Java语言实现N皇后问题的完整程序,并在程序中准确地统计程序运行的时间开销。 相似文献
8.
8皇后问题是计算机算法设计领域里的经典问题。利用回溯算法和概率算法相结合的办法求解8皇后问题,通过实验分析第一次成功搜索到皇后位置的概率,以实验得出的数据为依据对现存的观点提出了质疑,并对实验数据进行了分析,肯定了本文数据的合理性。 相似文献
9.
利用位操作运算的快速性,将位运算应用到N皇后问题的解决中,并给出了位运算求解N皇后问题的算法。该算法较好地提高了问题求解的速度。通过VC++环境实现,该算法比普通的递归回溯算法的速度平均提高了40倍左右。 相似文献
10.
利用一种简易的递归回溯算法,给出C语言实现N皇后问题的伪代码和完整程序,并在程序中准确地显示出皇后的各种摆法.程序逻辑清晰,结构明了,便于理解掌握,对于学习C语言编程具有很好的帮助促进作用. 相似文献
11.
利用回溯法,采用栈和队列实现计算N皇后解的一个新的非递归算法,并提出N皇后解的4个对称性质,重点分析5皇后的10个解之间的对称关系。然后利用对称性将搜索空间缩小为解空间的一半,给出计算N皇后问题的优化算法。理论分析和实验表明对称性可以明显提高N皇后问题的计算效率。 相似文献
12.
13.
基于Erlang语言平台解决N皇后问题,通过对原有基于Erlang的N皇后问题算法进行分析,提出了一种改进算法。该算法利用位运算操作,并且在每一行只搜索可以放置皇后的位置。理论分析与实验证明了该算法能明显提升N皇后问题算法效率。 相似文献
14.
15.
王寅庆 《数字社区&智能家居》2009,(23)
N皇后问题是一个比较传统的组合搜寻问题,也是人工智能领域的一个经典的搜寻实例。给出了对N皇后问题求全部解的基于启发式的和以空间换时间的快速算法思路及其实现,将之同一般的回溯算法进行了时间耗费的比较,证明了算法是较优的算法;并讨论了算法的时间和空间复杂性。在个人电脑上,求16皇后全部解只需12.2秒。 相似文献
16.
曾艳丽 《计算机光盘软件与应用》2010,(11)
八皇后问题是计算机科学中一个较经典的题目.本文提出用回溯法来解决八皇后问题,并给出了逻辑结构清晰、可读性强的递归算法,用C语言加以实现,得到了八皇后问题的12个真正不同的解. 相似文献
17.
应用回溯法求解规模较大的N皇后问题时,时间开销巨大。从提出布尔遗传算子角度,增强遗传算法局部搜索性能,与具有良好全局搜索性能的矩阵遗传算子组合应用,对N皇后问题求解。采用自然数和二进制互换的编码方式,应用N皇后的约束条件构造适应度函数,保证了算法的全局收敛性。通过与回溯法和相关遗传算法比较,实验证实了该方法应用于求解N皇后问题,具有良好的搜索效率和求解质量。 相似文献
18.
宋阳秋 《数字社区&智能家居》2006,(36)
n皇后问题是非结构化的问题,人工智能中的搜索策略——回溯法是解决这类问题的有效方法。本文介绍了利用回溯法求解n皇后问题的基本思想以及实现方法,并对算法提出了优化的方法,使得算法的运行效率更高。 相似文献
19.
基于位运算的N皇后问题的解法 总被引:1,自引:0,他引:1
N皇后问题一般是用回溯法进行求解,常规的做法是用数组来模拟棋盘,但是运行效率却不高。基于位运算的N皇后问题的解法,将列冲突转化为行冲突,以整型数的二进制形式来模拟集合,用位运算来实现集合运算。通过编程测试,证明此种解法能够大大提高运行效率。 相似文献
20.