P与NP问题研究

P与NP问题被列为七大世界数学难题之首,由于其相关概念抽象而复杂,许多该领域的学生学者,对其相关概念的理解存在谬误,不少已发表的研究论文都体现了这一谬误。用中文通俗讲解到底什么是P和NP问题以及它们的关系,透过抽象的定义揭示其本质。列举一些科研论文上常见的对P和NP问题理解上的谬误,通过分析揭示其错误实质。同时并对解决这一问题可能的研究方法作一综述,对研究前景做一展望,为在该方向上学习和研究的学生学者,提供有价值的参考。由于文中包括:对复杂抽象的概念进行通俗而深入的剖析,对已有的研究进展进行摘要概括,对未来可能的研究方法和研究路线进行综述和分析,故能对该领域的研究者在概念的正确把握、文献的查阅和研究方向的选择上提供助益。

基于遗传算法的烟草配送车路径优化问题

在建立烟草配送车路径优化问题模型的基础上,采用轮盘赌复制法、部分匹配交叉算法、和适应度函数自适应调整等技术,设计了基于自然数编码的遗传算法,最后以这种方法进行了实验计算,通过计算结果表明,用遗传算法进行烟草车配送路径优化,可以方便有效地求得问题的最优解或近似最优解。

基于NP问题的环网可靠性分析与计算方法

本文基于非确定性多项式(NP)问题求解思路,根据冗余环网的功能要求、拓扑结构,建立了网络可靠性的计算模型,提出了根据网络设备平均无故障工作时间(MTBF)数据和节点、路径数量,计算网络可靠性的近似计算公式。最后,就实际应用的环网实例进行了可靠性分析及计算,以说明本文提出的方法。

基于纵横交叉优化的可重构电池组环流抑制策略

退役电池之间巨大的特性差异会降低储能系统的有效容量和安全性,严重阻碍电池的梯次利用。可重构电池组能灵活切换电池之间的连接方式,是应对电池特性差异的有效方案。然而,电压差异导致的电池组内部环流,会降低电能效率和缩短电池寿命,并引发局部过热等安全问题。以构建最多并联路径和抑制环流为目标,提出了可重构电池组的路径组合优化策略。建立了优化模型,并根据模型特征设计了离散二进制纵横交叉优化算法,克服了路径组合优化面临的非确定性多项式难题。最后,通过仿真和实验验证,证明了所提出的路径组合优化策略能有效抑制环流。

一个高效的3SAT到Hamilton环转化方法

为了得到将三元可满足性问题(3-Satisfiability problem,3SAT)直接转化为哈密尔顿环(Hamilton cycle)的高效转化方法,该文以长年对哈密尔顿环研究计算所探索出的规律为基础进行研究。通过对各种可能实现转化的图形组合进行全面的比较分析,得出用无向图的两个节点模拟3SAT的一个变量,用无向图的13个节点模拟3SAT的一个子式的方法,实现了3SAT到哈密尔顿环的高效转化。研究结果表明:该转化所需要的节点数及其边数是最优的。

一种多中继协同网络吞吐量优化算法

考察了接收节点通过累积信息量完成解码的单源单宿多中继无线网络,提出了一种基于动态前向解码协议的中继节点选择及传输算法.首先,给出了在给定整个网络所需传输信息量的条件下最小化信息传输时间的数学模型,并证明了其是一个完全多项式非确定性问题,进而提出了一种分布式贪婪中继节点选择算法.该算法综合考虑了被选择节点的上行和下行链路的信道增益,不仅保证了被选中节点能够容易地解码信源信息,而且使得网络终端接收到较多的有效解码信息.仿真结果表明,该算法接近集中式最优中继节点选择机制的性能,并且其分布式实现减少了系统开销.

Niederreiter公钥密码方案的改进

针对现有Niederreiter公钥密码方案容易遭受区分攻击和信息集攻击(ISD)的现状,提出一种改进的Niederreiter公钥密码方案。首先,对Niederreiter公钥密码方案中的置换矩阵进行了改进,把原有的置换矩阵替换为随机矩阵;其次,对Niederreiter公钥密码方案中的错误向量进行了随机拆分,隐藏错误向量的汉明重量;最后,对Niederreiter公钥密码方案的加解密过程进行了改进,以提高方案的安全性。分析表明,改进方案可以抵抗区分攻击和ISD;改进方案的公钥量小于Baldi等提出的方案(BALDI M,BIANCHI M,CHIARALUCE F,et al.Enhanced public key security for the Mc Eliece cryptosystem.Journal of Cryptology,2016,29(1):1-27)的公钥量,在80比特的安全级下,改进方案的公钥量从原方案的28 408比特降低到4 800比特;在128比特的安全级下,改进方案的公钥量从原方案的57 368比特降低到12 240比特。作为抗量子密码方案之一,改进方案的生存力和竞争力增强。

基于改进参数协进化和声搜索算法的配电网重构

配电网重构是智能电网的关键技术之一,是非确定性多项式难题(NP-hard)。在确立了网损最小为配电网重构的优化目标后,提出一种改进的参数协进化和声搜索算法。首先,针对参数协进化和声搜索算法在局部寻优时反馈环较长的问题,提出一种辅助新和声的策略进行优化;其次,为克服和声搜索算法本身应用于整数规划的配电网重构时音调调节带宽难以确定的困难,使用并优化一种自适应新和声优化策略;最后,通过对T型节点的分析提出一种不可行解的处理方案,提升了算法的寻优性能。基于IEEE 69节点系统和某实际配电网的仿真对比测试表明,所提出算法与其他改进的和声搜索算法相比,具有更好的收敛性能和寻优性能。

基于Niederreiter编码的混合加密方案的改进

基于编码的密码方案具有抗量子的特性和较快的加解密速度,是当今抗量子密码方案的备用方案之一。现有基于编码的混合加密方案已经达到选择密文攻击不可区分(IND-CCA)安全,其缺点是加密收发双方共享秘密密钥的公钥尺寸较大。针对基于Niederreiter编码的混合加密方案公钥尺寸大的的问题,首先对Niederreiter编码方案的私钥进行随机拆分,然后对Niederreiter编码方案的明文进行随机拆分,最后对Niederreiter编码方案的加解密过程进行了改进。经过分析得出,改进方案的公钥尺寸小于Maurich方案的公钥尺寸,在80比特的安全级下,改进方案的公钥从原方案的4 801比特降低到240比特;在128比特的安全级下,改进方案的公钥从原方案的9 857比特降低到384比特。虽然改进后的方案比原方案过程复杂,但其存储代价和计算代价变小,方案的实用性增强。

McEliece编码签名方案的设计

针对现有Niederreiter编码签名方案存在安全性低、签名速度慢的缺点,设计了一种McEliece编码签名方案。首先,对McEliece密码方案的加解密过程进行改进,以提高方案的安全性;其次,利用改进后的McEliece密码方案设计了一种编码签名方案。分析结果表明,改进后的McEliece密码方案具有较高的安全性;设计的McEliece签名方案具有较高的安全性和较快的签名速度;在同等安全级下,Hash次数由Niederreiter编码签名方案的32 881次降低为25次,译码次数由Niederreiter编码签名方案的32 880次降低为24次。作为抗量子签名方案之一,设计的McEliece编码签名方案的生存力和竞争力较强。

格上困难问题求解的智能筛选算法及测试

在总结格密码困难问题发展和求解中关键理论与技术的基础上,从渐进最短向量问题(approx-SVP)入手,对比分析了经典格基约减算法的优缺点,重点研究了其求解推进过程中的关键技术和算法性能瓶颈,归纳了进行格基约减进而求解渐进最短向量问题的一般步骤。在经典的格向量假设基础上,提出了格向量智能筛选模型。通过优化向量选择的路径等方法,设计了基于最优路径分布的智能筛选算法、逆向求解智能验证算法和近似最短向量智能筛选算法三种求解最短向量问题(SVP)的算法,测试结果表明算法在求解格上困难问题上有效。

千禧年大奖难题与基础教育

2000年5月24日,美国克雷数学研究所公布了七个数学难题——“千禧年大奖难题”。它们分别是:霍奇猜想;庞加莱猜想;P=NP?,其含义是确定性多项式算法(P)是否在结果上等价于非确定性算法(NP);黎曼假设;杨-米尔斯规范场存在性和质量间隔假设;纳维叶-斯托克(Ns)方程解的存在性与光滑性;贝赫和斯维讷通-戴尔猜想。

模拟生态平衡机制的牵制平衡算法及其应用研究

为扩展仿生算法在求解工程设计优化问题方面的应用,模拟自然界的生态平衡机制,提出了一种新的仿生算法——牵制平衡算法.该算法以种群个数对应设计变量的维度,以种群规模对应设计变量的值,以物种间的牵制关系为优化驱动力,以系统达到稳态平衡为优化目标,构造了自成长函数、牵制函数和算法机制.通过对算法进行收敛性测试、不同基础资源测试和多物种求解测试,验证了算法的有效性.以三个工程设计问题为比对实验案例,实验结果表明:与现有算法相比,牵制平衡算法在这些问题中皆能获得优解,是一种具有实用性和竞争力的新算法.