一种求解子集问题的基于图的蚂蚁系统

提出了一种求解子集问题的基于图的蚂蚁系统。针对子集问题,定义了构造图和等效路径,提出了基于等效路径增强的信息素更新策略,将问题的无序信息转化为对蚂蚁的有序影响,增加蚂蚁搜索路径的信息量。引入路径变异机制,通过路径的改良调节信息素分布,防止算法陷入停滞状态。将信息素更新分为三种情况:本次迭代最优更新、变异更新和本次迭代不更新,兼顾算法的收敛速度和搜索能力。对算法进行了描述并分析了算法复杂度。以多维背包问题为例,对该蚂蚁系统的性能进行了测试,验证了系统的有效性和优越性。

子集和问题的O（1．414^n）链数DNA计算机算法

随着DNA计算机研究的不断深入,如何克服DNA生物计算中穷举法的极限已成为DNA计算研究的重要内容之一.为设计可扩展的子集和问题DNA计算机算法,文中将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,通过设计DNA并行搜索器,提出一种求解子集和问题的DNA计算机模型和算法.与已有文献结论的对比分析表明:文中算法在保持多项式生物操作复杂性的条件下,将穷举算法中的DNA分子链数从O(2n)减少至O(1.414n),其中n为子集和问题的维数.因此,文中算法理论上在试管级生化反应条件下能将可破解子集和公钥的维数从60提高到120.

子集和问题的量子中间相遇搜索算法

子集和问题是NP完全问题,该问题是背包公钥的基础.现有最优的经典算法求解规模为n的子集和问题需要O(n2n/2)步运算.本文提出了基于时空折衷思想的量子中间相遇搜索算法,该算法可以在O(n2n/3)步求解规模为n的子集和问题,其存储复杂性为O(2n/3).由于NP完全问题可以在多项式时间内可相互归约,所以,在存储复杂性为O(2n/3)的条件下,量子中间相遇搜索算法使得NP完全问题的计算复杂性降为O(n2n/3).

子集和问题的分治求解

介绍了求解子集和问题的一个分治算法。设给定的n个正整数为A(1),A(2),…,A(n-1),A(n),给定的子集和为正整数M,算法的时间复杂性为O(nlog2(M+1)+1),空间复杂性为O(n)。当M较小时,算法复杂性优于二表算法的复杂性。

整数的带余除法在子集和问题中的应用

针对子集和问题,提出一种利用整数的带余除法和生日问题原理的快速算法。给出算法描述,证明算法的有限性和有解判定结果的正确性,分析判定的成功率。从运行时间、成功率等方面与近似算法作了对比随机实验。结果表明,该算法在时间效率上优于近似算法,且对大集合问题具有较高的成功率。

基于分治的子集积问题DNA计算机算法

如何减少DNA计算机在求解大型科学问题中以问题输入纯指数增长的DNA链数,已成为DNA计算机研究的重要内容。本文将分治策略应用于子集积问题的DNA分子计算中,提出一种求解子集积问题的新的DNA计算机算法。该算法由n位数据搜索器和其它五个子算法组成,其DNA链数可达到亚指数的O(2q/2),其中q为子集积问题的维数。与最近文献结论进行的对比分析表明:新算法将求解子集积问题所需的DNA链数从O(2q)减少至O(2q/2),最大链长度减少为原来的1/2。因此,利用新算法在试管级水平上能将可破解的子集积公钥的维数从60提高到120。

基于联立丢番图逼近的子集和问题启发式求解算法

子集和问题是计算机科学中的一个重要问题,也被应用于公钥密码和伪随机函数的设计.学界已提出多个求解一般子集和问题的通用求解算法及求解特定子集和问题的特殊求解算法.本文通过建立子集和问题和联立丢番图逼近问题之间的联系,提出一种新的子集和问题启发式求解算法.该算法由给定的子集和问题构造联立丢番图逼近问题,使用格归约算法寻找该联立丢番图逼近问题的解,由此构造与原始子集和问题线性无关的新的子集和问题,从而达到降低原始子集和问题维数的目的;最后,通过n-1个联立丢番图逼近问题的解来构造n—1个线性无关的子集和问题,并通过求解一个由n个变量和n个线性方程构成的方程组来求解原始子集和问题.基于联立丢番图逼近的子集和问题启发式求解算法为子集和问题研究提供了新的思路.

对一个集合子集问题的思考

这篇习作很好.它是王开同学在学习中勇于探索,勤于思考,善于研究取得的可喜成果.看到这样的习作,我们很高兴,借此向指导他的王扬老师致敬.原稿中还有“拓展3”,把原问题拓展到更一般的情形(因此解决起来也更复杂一些) .由于刊物的篇幅所限,我们只好忍痛割爱了.

求解子集和问题的快速算法

针对子集和问题,文中提出了一种快速算法。该算法设计运用了整数带余除法和生日问题的原理。理论分析表明该算法时间复杂度为O(n2),其正确率为1-(T-2/T-1)n2m。随机试验显示,该算法在时间效率上明显优于传统指数时间复杂度算法,且对大集合问题具有很高的正确率。

子集和问题的一个伪多项式时间算法

提出了一个求解子集和问题的伪多项式时间算法,该算法可有效地求解很大一类密度d(A)>1的子集和问题。

求解子集和问题的采样格归约算法

子集和问题是计算机科学中的重要问题,也是构建多种公钥密码体制的基础.提出了采样归约算法,使用随机采样方法降低问题维度,将原问题分解并归约为多个更小规模的格上最短向量,降低了构造格的半径,从而提高求解的效率,得到原问题的精确解或提高近似解的逼近程度.给出了理论上采样归约算法最差情况的成功率.更进一步地,在目标解重量较低的情况下,可以进行分段采样,对问题增加限定条件,提高解题效率.实验结果表明,对于高维度的子集和问题,与CJLOSS等已有的格归约子集和问题方法相比,该算法可以更高效地求解出问题的精确解,而且可以提高近似解的逼近程度,输出近似解的平均长度达到了CJLOSS算法的0.55倍、DR算法的0.64倍.

无向图中子集反馈顶点集问题的精确算法

子集反馈顶点集问题是一个经典的NP难问题,该问题是指在一个无向图中删除最少的顶点使得图中某些给定的顶点不在任何圈中.子集反馈顶点集问题包含了经典的最小反馈顶点集、多路割等重要特例问题,并且可应用于电路测试、操作系统解死锁等领域.子集反馈顶点集问题也是精确算法中的一个重要问题,该问题存在一个运行时间为O~*(2~n)的简单暴力搜索算法,其中n为图中顶点数.直到2011年Fomin等人给出一个运行时间为O~*(1.8638n)的算法,这个运行时间界才被打破.文中将该运行时间上界进一步改进到O~*(1.7743n).文中的算法是一个分支搜索算法,为了改进该问题的运行时间界,文中对问题的结构性质进行了深入的分析,挖掘出若干有效的规约和分支规则,再采用测量治之方法对算法的运行时间进行分析,最终将运行时间上界给予改进.

基于Goldwasser-Micali加密算法的安全子集计算

针对解决集合间安全子集问题的协议大多只能保护一个集合元素的隐私进行研究。在半诚实模型下,利用布隆过滤器及Goldwasser-Micali同态加密算法构建了一个安全子集计算协议,并使用安全多方计算中普遍采用的模拟范例证明方法证明了协议的安全性。利用布隆过滤器将拥有大量元素或大数域元素的数据集合映射为较小的数据集合,提升协议的效率及适用范围,同时,借助Goldwasser-Micali同态加密算法保证协议的安全性。相关研究大多是基于二次剩余等困难问题,不可抵抗量子攻击,可抵抗量子攻击的安全子集计算是进一步的研究方向。

面向多最优解组合优化问题的决策求解算法

针对具有固定物品总和、多最优解特征的组合优化问题,以固定总和实数子集问题和购买鸡翅问题为例,给出了这类多最优解组合优化问题的形式化表示。在分析枚举等经典算法基础上,提出了基于整数状态表示和实数状态表示的0-1决策递归搜索多最优解动态规划算法。针对该算法在最优解数量较大时,时间复杂度趋向O(m^(n))的问题,提出了基于相同决策路径合并和基于0-x决策的两种改进算法。实验中两种改进算法的计算时间基本符合与O(nb+nm)的正比关系,表明对于这类多最优解组合优化问题具有良好的求解性能。

子集和组的求解以及真分式背包体制的攻破

本文采用概率的方法，证明了整数格中短向量‖Ｘ‖~２≤ｎ／２的期望个数是１＋２^（１．５４７２５－β）ｎ，β＝∑ｌｏｎｇ_２（ｍａｘａ_ｊｉ）／ｎ。本文修改了计算格归约基的Ｌ~３算法，用于解决一般的子集和组问题。本文还进一步分析了真分式背包体制的性能，介绍了使用修改的Ｌ~３算法攻击它的方法。

一种求解最大团问题的蚁群算法

将最大团问题看作子集类问题,提出了基于子集类问题的特殊蚁群算法用于求解最大团问题。该算法将信息素和局部启发信息与图的顶点相关联,而不再与边相关联,从而提高算法的运行速度。仿真实验研究表明,该算法较传统求解最大团问题的蚁群算法有着更短的运行时间,较强的求解能力,更适合用于求解最大团问题。

基于剪枝策略的回溯算法优化——以子集和问题为例

回溯法的本质是穷举,其复杂度较高,但通过剪枝策略,可以显著增强算法的性能。本文以子集和问题为例,分别实现了无剪枝、约束条件剪枝、先验知识剪枝、约束条件剪枝加先验知识剪枝共四种算法策略,并通过实验进行性能对比,验证了各种剪枝策略在不同情境下的效果,并总结了剪枝策略对算法性能的实质性改进。研究结果表明,合理应用剪枝策略能够显著提升回溯算法在复杂组合优化问题中的解决效率和实用性,为相关领域的算法设计与应用提供了重要参考与指导。

整数上的全同态加密方案的改进

目前的全同态加密方案的效率还很低,与实际的应用还有很大的距离,提高全同态加密方案的效率和安全性是全同态加密技术研究的重点与难点。为了提高效率,在Dijk等人的全同态加密方案的基础上,将模2运算改为模4运算,并使用Gentry的全同态思想,提出了一种更快速的全同态加密方案,改进之后的方案一次可以加密2 bit的数据,且公钥尺寸降低到Ο珟(λ7),从而比Dijk等人的方案具有更高的效率和更小的公钥尺寸。新方案的安全性基于近似最大公因子问题和稀疏子集和问题。

一种短密钥高效全同态加密方案

针对Van Dijk等人在2010年欧密会上提出的基于整数的全同态加密方案进行了研究,此方案的主要优势在于概念上的简单性,将原来的基于理想格的同态加密体制替换为一个非常简单的整数描述的同态加密体制,但是它的公钥尺寸为O(λ^(10)),并且每次只能加密1 bit。在原始DGHV同态加密的基础上,通过改变整数的选取方式和模数,提出了一种一次可以加密k bit的同态加密方案,且公钥的尺寸降低至O(λ~7)。最后给出了安全性证明和效率分析,方案与原始方案基于相同的困难问题,且加/解密效率有所提高。

基于整数近似GCD的全同态加密方案

设计了基于整数近似GCD问题新的全同态加密方案。跟随Gentry设计模式,构造somewhat同态加密方案,并归约其安全性到整数近似GCD;引入稀疏子集和难度假设来压缩解密电路,使其具有自举性;最后转换somewhat同态加密方案到全同态加密方案。与文献[1]方案相比,提出的somewhat同态加密方案更接近于文献[2]中公钥加密方案。