N皇后问题随机算法性能分析

N皇后问题是NP问题,以随机算法结合回溯求解该问题,能获得很好性能。算法性能与随机皇后数量的关系曲线呈U型。随机皇后数量须在宽度不大于20的特定范围内才能获得较好性能。100以内随n变大,最佳随机皇后数量从n-10到n-17缓慢变化。最佳随机皇后数量使算法能在常规时间内求解n>100的情况,远大于单纯回溯法求解规模30。由于回溯开销,提高随机算法性能的做法不能有效降低总用时。算法用时随n值递增的速度不断趋缓。     

改进的基于Erlang的N皇后问题算法

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

N皇后问题的回溯算法改进

回溯算法是解决N皇后问题的经典算法。在分析N皇后问题的解结构的基础上,优化了利用回溯法求解N皇后问题的解空间树,并改进了互不攻击的条件,大大地减少了比较次数和求解的复杂度,通过理论分析和实验证明了改进算法的可行性。     

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

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

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

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

基于位运算的N皇后问题的解法

N皇后问题一般是用回溯法进行求解,常规的做法是用数组来模拟棋盘,但是运行效率却不高。基于位运算的N皇后问题的解法,将列冲突转化为行冲突,以整型数的二进制形式来模拟集合,用位运算来实现集合运算。通过编程测试,证明此种解法能够大大提高运行效率。     

N皇后问题的启发式算法探讨

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

改进回溯算法实现N皇后问题求解

回溯算法是基本的算法之一,其重要的思想是不断地用限界函数去测试正在构造的部分解向量,看是否导致合法解,回溯算法通常具有较高的时间复杂度,但对于至今除了穷尽搜索仍未找到其他的方法的问题,回溯算法是较为有效的方法.介绍了回溯算法,以及以经典的N皇后问题为例,讲解了用回溯算法求解问题,并分析了其空间复杂度,介绍了求解N皇后问题的改进回溯算法.     

应用布尔遗传算子求解N皇后问题

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

N后问题的回溯法改进

回溯法是用于求解N后问题的常用算法。典型的回溯算法在N后问题的解空间中,用于判断合法子树的剪枝函数的时间效率较低。实际应用中,可以将位运算运用到回溯法的剪枝函数中。实验证明,使用位运算方法能够加速获得合法子树的效率,从而提高了使用回溯法求解N后问题的时间效率。     

Radix-8 Booth译码Montgomery模乘的RSA算法的设计和硬件实现

提出一种使用Radix-8 Booth译码的Montgomery模乘算法,进一步减少了模乘的中间乘积项个数,提高了模乘的速度.并给出基于该模乘算法的1024位RSA加密硬件的实现方案,其加密速度可达到采用普通Montgomery模乘的RSA加密方案的2倍.在设计方法上使用基于系统级算法的快速设计流程,在系统级设计阶段确定模乘和RSA整体算法的实现方案,并对其评估及优化,缩短了RTL阶段的设计时间,加快了设计思想到硬件实现的转化.实现方案在自行设计的FPGA开发板上通过验证,并进一步转换为ASIC设计综合.     

一种AVS-M运动搜索快速算法

针对AVS-M运动搜索算法的复杂性,根据其变换量化的特点,推导全零块判决准则,提出一种基于全零块检测的AVS-M运动搜索快速算法,在运动搜索的同时判决出全零块,从而节省运动搜索和变换量化的时间。实验数据显示,该算法节省的计算量最多可达77.4%,且比特率下降程度大于峰值信噪比下降程度。结果表明,在不降低编码性能的情况下,该算法能有效提高运动估计的编码速度。     

改进型遗传蚁群混合算法求解0/1背包问题

针对原有的遗传蚁群混合算法收敛速度慢、运行时间长等缺陷,提出了一种新混合算法,该算法从蚁群中选取部分优良个体采用遗传算法寻优,所选个体数目随迭代次数自适应变化,同时,对算法中的交叉、变异操作以及赋值等方面进行了一些改进。仿真结果表明,该算法在搜索能力、收敛速度以及程序运行时间方面都有明显的提高,由此证明了该算法的有效性。     

基于相对熵函数准则的BP算法

提出一种改进的BP算法,并对改进算法中的参数选择进行了讨论。改进后的算法用于XOR问题的学习及函数逼近问题。结果表明,改进后的BP算法可显著地提高网络的学习速度和逼近精度。     

基于分布式约束满足的多约束单路径路由问题求解

约束路由问题是IP网络的一个核心功能,由于求解多约束路由问题属于NP完全问题,所以大量的研究工作围绕此展开.基于分布式约束满足的思想,设计多约束单路径路由问题求解算法,分析表明该求解算法降低计算复杂度,提高算法的性能.在分布式条件下完成算法的实现,经实验表明,算法近似程度较好,求解速度快.     

一种改进的遗传聚类算法

给出了一种改进的基于遗传算法的聚类方法。传统的K-means算法局部搜索能力强,但是对初始化比较敏感,容易陷入局部最优值。基本的基于遗传算法的聚类算法是一种全局优化算法,但是其局部搜索能力较差,收敛速度慢。针对这两个方法所存在的问题,提出了一种改进的聚类算法。该方法结合了两个方法的优点,引入了K-means操作,再用遗传算法进行优化,并且在该方法中改进了遗传算法中的交叉算子,大大提高了基于遗传算法的聚类算法的局部搜索能力和收敛速度。     

模重复平方算法的rho改进算法

利用循环二进制方法给出了适合大指数模乘运算的模重复平方算法的rho改进算法,以提高模幂乘法的计算速度。新算法的实质是一种指数约减算法,可以有效减少模重复平方算法中的模乘运算。通过实例计算表明,新算法可以极大地提高运算速度。     

基于RSA算法的一种新的加密核设计

本文着重分析了RSA算法的核心-模幂运算,提出了有利于硬件实现的改进算法,并利用中国剩余定理加快了RSA的解密及数字签名的运算速度。在此基础上,最终提出并设计了一种结构简单,运算速度较快的加密核。通过VerilogHDL模型的仿真验证了此加密核设计的正确性及可行性。     

改进的RSA算法在数字签名中的应用

针对传统RSA密码算法运算效率较低的问题,在标准RSA密码算法的自身结构和具体运算操作两方面做出了相应的改进,提出了一种新的RSA密码优化算法,并将该算法运用到数字签名技术中。然后通过仿真实验,将其与传统RSA算法以及基于乘同余对称特性的SMM算法和指数2k进制化相结合的组合优化算法相比较,实验结果表明新的RSA密码优化算法在提升运算速度方面达到了较高的水平。     

一种新直线算法的探索

对传统直线算法进行了详细的分析，然后从传统直线算法的另外一个角度对直线生成算法做出了新的探索，改变了传统算法中直线像素点的查找方式，提出了一种新的查找最佳像素点的方法，与传统方法相比，新算法节点的查找方式的突出特点是按段进行的，为了提高算法的性能，对算法进行了增量优化。文章最后对两种算法进行速度比较发现，本算法在速度上优于传统直线生成算法。