最短加法链的随机幂树方法

幂树法是求解最短加法链的一种简单近似方法,其计算效率高,一次可获得大量结果,但是精度偏低。随机幂树方法在扩展幂树时保持一层一层扩展,同时随机地扩展叶子结点,重复生成随机幂树并更新最优结果,在保持计算效率高的同时极大改善了计算精度。对于所有n<24924的数,通过9次重复生成随机幂树,准确率可达95%以上,平均达到97%,而且确保结果是次优结果。该方法在普通计算机上的求解规模可达155691199。

最短加法链算法

本文讨论了关于正整数 n的最短加法链问题 .利用已取得的关于正整数 n的最短加法链长度 l(n)的上、下界的理论成果 ,构造了在回溯法中对状态空间树进行剪枝的精细的剪枝函数 ,从而设计出产生任意正整数

最短路问题的通用算法——最短初等链法

最短初等链法是求解网络图最短路问题的通用算法,它突破了以往诸算法的局限性,适用范围广,具有广阔应用前景。

最短加法链的一种快速算法

针对可计算n的最短加法链问题,提出了一种快速算法,利用贪心算法思路,从1开始不断翻倍,当翻倍后大于n时,进行向前遍历,使得结果小于等于n,在此基础上利用深度优先搜索算法得到当前可行解及其深度d,深度超过d时对当前分支不再进行搜索以减少空间复杂度,但是当加法链扩散出去后时间复杂度上会呈指数增长,所以再结合一些剪枝函数,进行剪枝操作以减少时间复杂度,进而在一个有效时间内得到较好的解。针对7类挑战问题,利用Eclipse平台编写改进算法,给出具有最短加法链长度的数及其加法链表示;加法链能应用到模指数的幂运算中,而模指数的幂运算是公钥密码学中的核心运算之一,因此改进最短加法链的快速算法可以提高公钥密码体制的执行速度。

基于数据库的最短加法链设计与实现

研究了求解最短加法链的多叉树结构,使用SQL Server2000存储树,使用存储过程实现了多叉树的快速扩展,用C#+ADO.NET设计客户端程序实现对数据库的查询并输出节点的最短加法链。实验证明,在普通PC机上使用存储过程每秒可以产生约500个节点,而客户端查询时间平均小于5秒钟,最短加法链库的设计与实现对RSA中模幂快速算法有重要的实际意义。

基于最短加法链状态空间树的IAPWS-IF97快速计算方法

基于IAPWS-IF97水和水蒸汽物性的主要计算量是其中的大量二元、离散整指数幂值的计算。基于最短加法链状态空间树的二元、离散整指数幂值的快速计算方法,可提高使用IF97公式计算水和水蒸汽物性的速度。实例计算表明,其计算速度是直接调用计算机语言中的数学库幂函数计算的1.5~7倍,可以更好地满足对物性计算速度有高要求的热力计算分析任务的要求。提出的IAPWS-IF97快速算法软件实现复杂度低、可维护性高,算法的软件实现已经共享于Git Hub。

关于E_0的Steiner邮路问题

给定图G=(V,E,w),E_0E是一个指定通过的边子集,本文讨论了关于E_0的Steiner邮路问题的特殊情况,即由E_0导出的子图仅有两个连通分支。我们分别考虑了三种不同的情形,并给出了子闭迹消去算法和带限制的最短链算法,前者是一个基于整数规划的精确算法,而后者是一个近似算法。

RSA密码算法的一种新的快速软件实现方法

在介绍标准RSA密码系统的基础上，利用计算近似最短加法链算法给出了软件实现模幂运算的一种改进方法；基于求解孙子定理的混合基数计算算法（MRC）改进了RSA的解密方法；最后，结合快速有效的素数测试方法提出了一种能够快速软件实现RSA密码算法的新方法，并分析比较了各相关算法的计算效率。实验结果表明：利用该方法实现的RSA密码软件系统，可使加、解密运算速度平均提高6～10倍。

一种特殊图的几个简单性质

有一种特殊图,它是无向、无环、联接的,并且相连任意两点的最短链只有一条,不妨用符号表示图 G=(X,E),这里X表示G的顶集,E表示G的边集,本文针对这种图,讨论其简单性质,其中有两个明显的性质,不作详细论证,只把这两个性质简单提出来,因此集中讨论另外两个性质,并加以详尽而周密严谨地证明之。

基于SINR干扰模型的低延迟链路调度

文章基于SINR(Signal to Interference and Noise Ratio)干扰模型设计了最短链路调度算法L3S(Low Latency Link Scheduling),理论证明了L3S的正确性并给出了L3S的近似比。将网络区域划分为六边形的网格,如果通信链路位于相距较远的六边形中,他们可能会同时通信。为了简化SINR计算,L3S不考虑环境噪声。可以证明,当考虑环境噪声时,算法L3S得到的结果仍然是正确的,只需要提高链路的发送功率及SINR阈值β。